ведь всего-то 300 метров

← →
tippa © (2010-06-19 10:21) [0]

Подскажите пожалуйта.
Имеется файл размером 300 мегабайт, состоящий из 30 миллионов строк, при попытке его загрузки в StringList выскакивает ошибка, мол нехватает памяти. Оперативы 1 гигабайт. Это нормально?
Как можно провести сортировку строк в таком файле?

← →
Дмитрий Белькевич (2010-06-19 10:42) [1]

О сколько нам открытий чудных...

Это нормально. Не стрингрдом единым жив сортировщик.

← →
Дмитрий Белькевич (2010-06-19 10:46) [2]

ээээ.... не стринглистом конечно же :) Когда же уже будет редактирование на форуме :)

← →
Anatoly Podgoretsky © (2010-06-19 11:18) [3]

> tippa (19.06.2010 10:21:00) [0]

300 мб ерунда, а вот 30 000 000 строк это много, ведь даже для строки из
одного символа надо от 13 до 17 байт, кроме того память выделятся кратными
блоками. Но тебе не нужен StringList для сортировки. Примеры быстрой
сортировки поставляются вместе с Дельфи.

← →
Игорь Шевченко © (2010-06-19 11:32) [4]

> Как можно провести сортировку строк в таком файле?

sort infile >outfile

← →
Palladin © (2010-06-19 16:34) [5]

> Как можно провести сортировку строк в таком файле?

а тебе его весь обязательно в память читать? а вообще надо ли его сортировать? а вообще может уже сортированным формировать? а может вообще СУБД какую нибудь попользовать? как-бэ 30 миллионов это тебе не хухры мухры

← →
[true]TRIx © (2010-06-19 16:56) [6]

Даже 100 мб загруженной в программу может тратить 2 гига оперативы, если ты работаешь с этими строками. Тут не важно сколько у тебя памяти, вся память будет занята.

← →
tippa © (2010-06-19 17:17) [7]

задача - сделать статистический анализ этого файла, а именно подсчитать сколько раз каждое слово встречается в файле. Вот я и думал сначала отсортировать, а потом в один проход подсчитать число вхождений для каждого слова.

← →
RWolf © (2010-06-19 17:46) [8]

а чтобы подсчитать число вхождений каждого слова в один проход, обязательно сортировать строки?
кстати, это будет уже второй проход.

← →
Anatoly Podgoretsky © (2010-06-19 17:58) [9]

> задача - сделать статистический анализ этого файла, а именно
> подсчитать сколько раз каждое слово встречается в файле.
> Вот я и думал сначала отсортировать, а потом в один проход
> подсчитать число вхождений для каждого слова.

Тут уже получится на 30 000 000 строк, а много больше, поскольку по данному алгоритму строку придется делить на слова, Тут уже сразу можно вешаться. Это задача не для файла, а для базы

← →
RWolf © (2010-06-19 18:28) [10]

> Anatoly Podgoretsky © (19.06.10 17:58) [9]
> строку придется делить на слова

судя по соотношению «размер файла — число строк», автор забыл уточнить, что на одну строку приходится только одно слово.

← →
[true]trix © (2010-06-19 18:46) [11]

tippa, это уже реализовано почти. исправь код. работает оч быстро.

Алгоритм составления словаря всех уникальных слов встречающихся в текстовом файле.
По результатам тестирования: обработка файла объемом 3 Мб (уникальных слов ~63 тысячи)
занимает около 3 секунд. (Можно, конечно, и еще ускорить, но уж лениво сильно ;)

Размер архива: 4 073 байт
http://rouse.drkb.ru/files/dict.zip

← →
tippa © (2010-06-19 18:57) [12]

да, одна строка - одно слово. На выходе должно получиться что-то вроде
1слово-n 2слово-m 3слово-k ...
где m, n и k - число вхождений.
Ну а если без сортировки и без Stringlista. Читаю весь файл в строку. Затем создаю два стинглиста, один для уникальных слов, второй - для числа вхождений. Начинаю перебирать слова, каждое новое слово добавляю в первый стринглист, а если оно там уже есть - увеличиваю соответствующий счетчик во втором стринглисте. Но в итоге эти два стринглиста опять не влезут в память. А если вместо стринглистов использовать 2 массива, или массивы так же как и стринглисты будут всю память занимать?

← →
RWolf © (2010-06-19 19:03) [13]

> tippa © (19.06.10 18:57) [12]
> Но в итоге эти два стринглиста опять не влезут в память.

я так думаю, слов в тексте не сто миллионов, отчего же не влезут.

← →
RWolf © (2010-06-19 19:12) [14]

но вообще, для быстрого поиска надо использовать специально предназначенные для этого структуры, а именно — хэш-таблицы.

← →
Anatoly Podgoretsky © (2010-06-19 19:12) [15]

> RWolf (19.06.2010 18:28:10) [10]

Ну тогда немного легче, хоть и некрасиво с его стороны, но все равно я бы
загнал БД и сразу бы получил ответ по каждому слову.

← →
Anatoly Podgoretsky © (2010-06-19 19:14) [16]

> [true]trix (19.06.2010 18:46:11) [11]

Даже при линейной зависимости как минимум в 100 раз больше, минимум 5 минут,
но вряд ли зависимость линейная.

← →
Anatoly Podgoretsky © (2010-06-19 19:15) [17]

> tippa (19.06.2010 18:57:12) [12]

Даже если и влезет, то работать будет много часов, может дней.

← →
tippa © (2010-06-19 19:28) [18]

Вот счас думаю найду готовую програмку. Фига с два. Нагуглил одну- единственную - Wordstat называется(http://dubinsky.ru/wordstat.htm), запехнул в неё свой файлик - програмка подумала и вылетела. Больше ничего подобного не нашел. Ковыряемся дальше)

← →
RWolf © (2010-06-19 19:34) [19]

да тут дел на 5 минут, и ещё 5, чтобы прикрутить какой-нибудь прогресс-бар для наглядности, что там гуглить?

← →
tippa © (2010-06-19 19:40) [20]

RWolf, будь хорошим человеком - объясни мне бестолковому в двух словах.

← →
RWolf © (2010-06-19 19:44) [21]

> tippa © (19.06.10 19:40) [20]

завести пустой список пар «строка-число» пока не прочитаны все слова из файла: прочитать слово если слово есть в списке - увеличить число, иначе добавить в список пару «слово - число 1»

← →
RWolf © (2010-06-19 19:50) [22]

[21]
самая затратная по времени операция — это как раз «есть ли слово в списке», поэтому контейнер для пар нужно выбрать с минимальным временем поиска. Для хэш-таблицы оно составляет О(1).

← →
tippa © (2010-06-19 19:52) [23]

спасибо

← →
Anatoly Podgoretsky © (2010-06-19 20:25) [24]

> RWolf (19.06.2010 19:50:22) [22]

Слово в списке, само по себе является хешем, нет нужды тратить время на
генерацию хеша.

> Anatoly Podgoretsky © (19.06.10 20:25) [24]
> Слово в списке, само по себе является хешем,
> нет нужды тратить время на генерацию хеша

Есть такая нужда.
Поместить слово в хеш можно гораздо бычтрее, чем в список.

> Sha (20.06.2010 10:31:25) [25]

Список, типа TList?

> Anatoly Podgoretsky © (20.06.10 10:54) [26]

Да. Хоть TList, хоть array of, хоть связный.
Все равно придется вести массив указателей для быстрого поиска.

Хеш-таблица фактически разбивает этот массив
на несколько массивов меньшего размера (обычно разера 1)
и быстро определяет, какой из них надо использовать.

> Sha (20.06.2010 11:07:27) [27]

Хеш список точно также надо сортировать

string --> List
string --> hash --> List

При несортированом списке аналогично

При правильном использовании хеш-таблиц,
число коллизий для одного ключа, как правило, равно нулю.
Т.е. размер списка равен 1. Там ничего не надо сортировать.

Например, в задаче автора, достаточно выбрать размер таблицы
100K, если слова без различных словоформ.

В моем алгоритме (ссылку на который привели) как раз в качестве хэша используется уникальный индекс слова в накопительном буффере. Т.е. сами слова добавляются в накопительный буффер и более не трогаются, сортируются только их индексы в TList-е

← →
WWW (2010-07-20 13:27) [31]

Если 30 млн строк, то это одно, если же 30 млн слов, то это совсем другое. В русском языке впринципе не может быть 30 млн, слов, так что если повторяющиеся слова не нужны, то рекомендую поудалять повторяющиеся слова

> WWW (20.07.10 13:27) [31]
>
> Если 30 млн строк, то это одно, если же 30 млн слов, то
> это совсем другое. В русском языке впринципе не может быть
> 30 млн, слов, так что если повторяющиеся слова не нужны,
> то рекомендую поудалять повторяющиеся слова

Ты полагаешь, что произнес мантру ? Может быть, но между звуком и делом обычно лежит пропасть.

← →
_Юрий (2010-07-20 20:49) [33]

В общем, сортированный THashedStringList с duplicates = dupIgnore и счетчиками в Objects
один проход.

а шо, аФФтар ещё здеся?

ведь всего-то 300 метров Найти похожие ветки