Есть задача проверять наличие данной строки в файле.
Нюанс в том, что надо проверить присутствуют ли в файле 20-30 тысяч данных строк.
Всё это работает, но занимает довольно долгое время, так как необходимо проверить большое кол-во файлов. Файл 300 Кб проверяется 10-15 секунд.

Есть ли идеи, как ускорить это?
Язык программирования не важен. [Ответ]

это думать надо..

.. забей.. лучше реши задачу про точки в окружности [Ответ]

стырить, наконец, из clamav сигнатурный поиск,а через год попасть на страницы газет "беспринципные воронежские программисты за решеткой" ).

а еще лучше начать выпускать на основе clamav какой-нибудь полукоммерческий продукт. [Ответ]

ниразу не приходилось реализовывать, но алгоритм представляется мне так:

двигаясь по файлу вперед, вычисляем контрольные суммы фрагментов C1,C2, ..CN, где N-максимальная длина фрагмента (сигнатуры).
при загрузке из контрольных сумм сигнатур, строится хеш.
дальше каждое C[i] нужно проверить на нахождение в хеше,
если нашлась в хеше, найти сигнатуру и сверить на фактическое побайтное совпадение.

Наверное у кнута есть что-нибудь по теме. [Ответ]

netwind прикольно придумал [Ответ]

Ну, гениальных мыслей у меня нет - их думать надо - а есть простые принцыпы, как я бы действовал для начала.

1. Файлы, по-возможности, грузить в память, потому что считывание целого файла в память довольно быстрая операция по сравнению с поиском по файлу (на кешь не всегда можно полагаться).
2. Искать не текст (строку), а бинарный код, потому что бинарное сравнение работает быстрее (если, конечно, это возможно).
3. Если возможно, для модуля (процедуры, функции и т.д.) сравнения применять оптимизацию компилятора по скорости. Или, если задача сравнения будет решаться побайтовым сравнением, использовать машинную команду сравнения блоков данных - она самая быстрая.
4. Если возможно, придумать хеш-функцию, которая бы отвергала на 100% неодинаковые значения, оставляя только "похоже, что одно и то же". А уж ее результат сравнивать побайтно. [Ответ]

Открываешь командер,
ф3,
контрол+ф,
пишеш слово,
жмеш поиск.
Алгоритм в 5 строк [Ответ]

zss_vrn Мой алгоритм практически полностью совпадает с тобою сказанным. Скорость низкая. [Ответ]

кто реализует подобную библиотечку для скоростного поиска сразу по тысячам регулярных выражений - навек войдет в историю антиспама.
вот это уже был бы прорыв. [Ответ]

Kerish
[Ответ]

Kerish Если поиск бинарный, то можно с кэшем попробывать поиграться. Т.е. искать за раз по 10-20 строк в небольших отрезках файла. И если проц двуядерный, то про распараллеливание тоже не забыть.
Если поиск по тексту - переводим вверхний регистр и делаем бинарный поиск.
Про интеловский компилятор тоже не надо забывать. Вообще 300 кб пройти 30000 раз за 15 секунд - это как-то странно... Ты не на яве писал? [Ответ]

не, вы вообще читали мой алгоритм в посте №4 ?

Кажется, я понял отчего у меня так тормозит цивилизация4... [Ответ]

netwind Если я правильно понял твой алгоритм, то существенного ускорения он не даст. Может оказаться даже медленнее. Файл у нас не 10Мб... [Ответ]

Калинин Дмитрий наверное, неправильно понял,
там всего за 1 просмотр файла проверяются сразу все сигнатуры.

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

Профессиональные антивирусы ведь работают очень быстро, значит быстрый алгоримт поиска сигнатур есть. И, скорее всего, похож на описанный. [Ответ]