|
Freebasic, скорость обработки текста
|
|
| WQ | Дата: Пятница, 22.08.2014, 15:34 | Сообщение # 1 |
|
Полковник
Группа: Проверенные
Сообщений: 215
Статус: Offline
| На одном форуме нужно было решить задачу по работе с текстом.
Условия, если кратко:
дано 2 текстовых файла
В 1 - список из 5000 слов(словарь)
В 2 - просто 26 мегабайт текста(около 200 000 строк, 4 000 000 слов)
Необходимо получить из 2 файла все строки, в которых встречаются слова из 1 файла(допустим, для простоты записать эти строки в 3 файл).
Ограничение - не тратить слишком много памяти и не более 2 ядер процессора
Я для начала написал код, который делает эту задачу примерно за 100 секунд, причем при этом используется два потока(а почему бы и нет, из-за многопоточности и перешел на Freebasic).
Так вот, один товарищ на том форуме пишет, что у него есть скрипт, который делает то же самое за 7 секунд и даже быстрее на одном ядре не самого нового процессора (а мой код - 100 сек, это он его проверял, у меня чуть быстрее). Ни язык, ни алгоритм не указывает. На этом обсуждение на данный момент заглохло, но меня терзают сомнения...
Вопрос в следующем - возможно ли так быстро выполнить такую задачу вообще, и если да, то можно ли также быстро это сделать на Freebasic?
Или тот человек несколько преувеличивает?
Я пробовал различные алгоритмы:
-регулярные выражения на основе pcre.bi - любой вариант очень медленно
-замену функции instr с английского форумиа на основе asm-а
Т.е. беру весь 26 мб текст и ищу в нем 1 слово из списка, потом 2 и т.д.
С 1 словом один прогон - допустим 0.05 секунд, но если сделать тоже самое 5000 раз...
-строковые функции из crt.bi
разбиваю текст на слова и каждое из 4 000 000 слов ищу в списке из 5000...
Опять слишком медленно...
Т.е. просто определить, что данное слово где-то в тексте есть - это быстро, но нужно-то найти все повторы и их позиции. Ускоряет дело предположение, что в тексте не встречаются все-все 5000 слов, т.е. можно сначала сделать 1 прогон, сократить список, и искать дальше. Но речь именно о варианте с наличием всех слов, т.е. все равно словарь несколько тысяч слов...
А, возможно, я просто смотрю не в том направлении...
Сообщение отредактировал WQ - Пятница, 22.08.2014, 15:37 |
| |
|
|
| haav | Дата: Пятница, 22.08.2014, 21:29 | Сообщение # 2 |
 Генералиссимус
Группа: Администраторы
Сообщений: 1436
Статус: Offline
| А немного памяти, это сколько? Хватит для того, чтобы сразу считать оба файла в память? Кстати, ты как считывал строки из первого и второго файла? Если каждый раз лез в файл, а тот товарищ считал оба файла сразу в память, то такая разница наверно возможна. Все таки скорость обращения с памятью на порядок выше, чем скорость обращения к жесткому диску. А вообще алгоритмика - сильная штука. Я вот например как-то писал чисто для пробы поиск на ассемблере, так он на маленьких строках конечно обгоняет Instr, но если строка подлинее, то усе. А все потому, что у Instr используется гораздо более лучший алгоритм, а у меня просто побайтовый перебор со сравнением  . Может быть для той задачи, которая озвучена тобой выше, побыстрее будет использовать Dictionary(словари) или Map (карты) : http://www.freebasic-portal.de/tutorials/using-mdtypes-en-108.html
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
|
|
| WQ | Дата: Пятница, 22.08.2014, 21:57 | Сообщение # 3 |
|
Полковник
Группа: Проверенные
Сообщений: 215
Статус: Offline
| Немного памяти - это до 2 гигабайт
Файлы, естественно, читаю целиком и дальше работаю с текстом в переменных
За ссылку спасибо - возможно в данном конкретном случае и не подойдет, но подобная вещь как раз нужна в других проектах.
Пока получается, что любой алгоритм быстр при 1 проходе, но при многотысячном повторении все становится хуже 
А также скорость слишком сильно (с моей точки зрения, а может это и нормально) замедляет обращение к массивам: если в цикле с помощью strstr() из crt.bi сравнивать 2 слова 1 000 000 0000 раз - как раз 6 секунд.
Но если подставлять слова из массиваов в 2 цикла (200 000 повторов в одном и 5 000 в другом - тот же 1 000 000 0000) то времени уходит на порядок больше + еще надо получить эти массивы.
Понятно, что есть более заточенные языки типа Perl, возможно, о нем и речь. Но не должен же Freebasic проигрывать в 10-12 раз...
|
| |
|
|
| haav | Дата: Суббота, 23.08.2014, 06:54 | Сообщение # 4 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1436
Статус: Offline
| Цитата WQ (  ) Понятно, что есть более заточенные языки типа Perl, возможно, о нем и речь. Но не должен же Freebasic проигрывать в 10-12 раз...
При одинаковом алгоритме конечно такого быть не должно (результат должен быть сопоставим).
А вообще линейный подход (поиск 1 слова, поиск 2 слова, .... поиск 5000 слова) конечно будет работать медленно. Тут нужен какой-то другой алгоритм.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
|
|
| WQ | Дата: Суббота, 23.08.2014, 19:10 | Сообщение # 5 |
|
Полковник
Группа: Проверенные
Сообщений: 215
Статус: Offline
| Цитата haav ( ) При одинаковом алгоритме конечно такого быть не должно (результат должен быть сопоставим). А вообще линейный подход (поиск 1 слова, поиск 2 слова, .... поиск 5000 слова) конечно будет работать медленно. Тут нужен какой-то другой алгоритм.
По ссылке посмотрел Map - вещь интересная, в одном коде как раз такой не хватало. С помощью этих карт можно получить все данные за один проход, но при большом размере словаря опять слишком медленно (>60 сек)
Нашел код сортировки слов на латинице:
http://www.freebasic.net/forum/viewtopic.php?f=7&t=22401#p197888
не только сортирует, но и удаляет дубликаты слов - вот это и может пригодиться.
Вроде быстро, но нужно на кириллице, для меня пока такой код сложноват, с конструкторами-деструкторами, пытаюсь понять.
Ну, а способ быстро разбить текст на слова тоже есть
|
| |
|
|
|
