Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Администрирование *NIX систем > Оброботка огормного файла

Автор: Dmi 13.5.2007, 14:58

Вообщем такая вот задача:  Есть текстовый файл. В нем в столбик находятся слова или словосочетания. Слова повторяются. Задача:  Нужно найти все словосочетания которые повторяются больше 100 раз и вывести в порядке возврастания. word1 : 2342 раз ... word 2 : 1014 раз Есть готовый скрипт на перле, который быстро обрабатывает файлы по 100- 200 метров Проблема, в том что файл размером ~ 3gb. Перл естественно не справляется Так как вот, можно как то это средствами оси сделать? Разбивать файл нельзя, требуется статистика по всему файлу. Конфиг сервака: P4 2.4|512 ram|Fedora В какую сторону капать ?

Автор: ZeeLax 13.5.2007, 20:10

Цитата(Dmi @  13.5.2007,  17:58 ) Так как вот, можно как то это средствами оси сделать? Что значит средствами оси? ;) Цитата(Dmi @  13.5.2007,  17:58 ) В какую сторону капать ? А копать надо в сторону алгоритмов и не в этом разделе.

Автор: bilbobagginz 13.5.2007, 21:27

можно даже сказать, что копать нужно в сторону параллельных и распределенных алгоритмов. есссно при ограниченной скорости доступа к памяти/диску  Цитата Перл естественно не справляется вполне возможно, что писан этот перл ногами... если задача заставляет обрабатывать весь файл в памяти, вам нужно добавить памяти и свопу. 0.5ГБ - очень мало.

Автор: ToshaCh 14.5.2007, 02:00

Вообще интерестная задача - (меня зацепило ), но не для этого раздела: двинуть её в алгоритмы надо.

Автор: Dmi 14.5.2007, 07:07

Да вы правы, Перл скрипт может не очень грамотный (много памяти ест). Тут конечно нужен алгоритм хороший. А пока, так как мне было нужно срочно, решил с помощью sort, uniq (вот почему в этот раздел запостил) Код sort f > f.s uniq -d -c f.s > f.u sort -nr f.u > f.us Не быстро конечно, но дело свое скрипт сделал, может кому пригодится.

Автор: Ch0bits 14.5.2007, 09:11

Надо загонять все слова из файла в B-tree со счётчиком наложений, если комбинаций не очень много и памяти хватает, то можно в обычное AVL-tree. Счётчик тоже индексировать деревом, а потом использовать как очередь с приоритетами. Из этой очереди вытаскиваем слова в порядке возрастания количества наложений. (я не спец в алгоритмах, но поступил бы так) Только как это написать на perl'е?    Добавлено через 3 минуты и 26 секунд Dmi, гы-гы, а про сортировку то я не подумал!    Ещё есть один извращенский способ! Загнать все слова в БД и вытаскивать через SQL.

Автор: MAKCim 14.5.2007, 09:34

Dmi,  а что, каналы запрещено использовать?    Код sort f | uniq -d | sort -nr > f.us это уж точно быстрее записи на диск, даже если 50% кэшируется

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)