Старый 15.12.2005, 10:51   #1   
Модератор
 
Сообщений: 665
Регистрация: 09.01.2002

Kerish вне форума Не в сети
Question Поиск строки в файле

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

Есть ли идеи, как ускорить это?
Язык программирования не важен.
  Ответить с цитированием
Старый 15.12.2005, 13:07   #2   
Форумец
 
Аватар для VBA b0.3
 
Сообщений: 166
Регистрация: 02.08.2005
Возраст: 44

VBA b0.3 вне форума Не в сети
это думать надо..

.. забей.. лучше реши задачу про точки в окружности
  Ответить с цитированием
Старый 15.12.2005, 14:16   #3   
Registered User
 
Аватар для netwind
 
Сообщений: 1,905
Регистрация: 25.03.2003

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

а еще лучше начать выпускать на основе clamav какой-нибудь полукоммерческий продукт.
  Ответить с цитированием
Старый 15.12.2005, 14:38   #4   
Registered User
 
Аватар для netwind
 
Сообщений: 1,905
Регистрация: 25.03.2003

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

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

Наверное у кнута есть что-нибудь по теме.
  Ответить с цитированием
Старый 15.12.2005, 14:41   #5   
girl-1.0asp
 
Аватар для Terry
 
Сообщений: 566
Регистрация: 20.09.2005
Возраст: 41

Terry вне форума Не в сети
netwind прикольно придумал
  Ответить с цитированием
Старый 15.12.2005, 14:48   #6   
Форумец
 
Аватар для zss_vrn
 
Сообщений: 2,045
Регистрация: 27.08.2003

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

1. Файлы, по-возможности, грузить в память, потому что считывание целого файла в память довольно быстрая операция по сравнению с поиском по файлу (на кешь не всегда можно полагаться).
2. Искать не текст (строку), а бинарный код, потому что бинарное сравнение работает быстрее (если, конечно, это возможно).
3. Если возможно, для модуля (процедуры, функции и т.д.) сравнения применять оптимизацию компилятора по скорости. Или, если задача сравнения будет решаться побайтовым сравнением, использовать машинную команду сравнения блоков данных - она самая быстрая.
4. Если возможно, придумать хеш-функцию, которая бы отвергала на 100% неодинаковые значения, оставляя только "похоже, что одно и то же". А уж ее результат сравнивать побайтно.
  Ответить с цитированием
Старый 15.12.2005, 14:58   #7   
Форумец
 
Аватар для Ray79
 
Сообщений: 831
Регистрация: 04.08.2005

Ray79 вне форума Не в сети
Открываешь командер,
ф3,
контрол+ф,
пишеш слово,
жмеш поиск.
Алгоритм в 5 строк
  Ответить с цитированием
Старый 16.12.2005, 10:34   #8   
Модератор
 
Сообщений: 665
Регистрация: 09.01.2002

Kerish вне форума Не в сети
zss_vrn Мой алгоритм практически полностью совпадает с тобою сказанным. Скорость низкая.
  Ответить с цитированием
Старый 17.12.2005, 09:52   #9   
Registered User
 
Аватар для netwind
 
Сообщений: 1,905
Регистрация: 25.03.2003

netwind вне форума Не в сети
кто реализует подобную библиотечку для скоростного поиска сразу по тысячам регулярных выражений - навек войдет в историю антиспама.
вот это уже был бы прорыв.
  Ответить с цитированием
Старый 19.12.2005, 09:12   #10   
Форумец
 
Аватар для zss_vrn
 
Сообщений: 2,045
Регистрация: 27.08.2003

zss_vrn вне форума Не в сети
Kerish
  Ответить с цитированием
Старый 19.12.2005, 10:14   #11   
Форумец
 
Сообщений: 2,159
Регистрация: 15.01.2003

Akad вне форума Не в сети
Kerish Если поиск бинарный, то можно с кэшем попробывать поиграться. Т.е. искать за раз по 10-20 строк в небольших отрезках файла. И если проц двуядерный, то про распараллеливание тоже не забыть.
Если поиск по тексту - переводим вверхний регистр и делаем бинарный поиск.
Про интеловский компилятор тоже не надо забывать. Вообще 300 кб пройти 30000 раз за 15 секунд - это как-то странно... Ты не на яве писал?
  Ответить с цитированием
Старый 19.12.2005, 10:32   #12   
Registered User
 
Аватар для netwind
 
Сообщений: 1,905
Регистрация: 25.03.2003

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

Кажется, я понял отчего у меня так тормозит цивилизация4...
  Ответить с цитированием
Старый 19.12.2005, 11:02   #13   
Форумец
 
Сообщений: 2,159
Регистрация: 15.01.2003

Akad вне форума Не в сети
netwind Если я правильно понял твой алгоритм, то существенного ускорения он не даст. Может оказаться даже медленнее. Файл у нас не 10Мб...
  Ответить с цитированием
Старый 19.12.2005, 11:17   #14   
Registered User
 
Аватар для netwind
 
Сообщений: 1,905
Регистрация: 25.03.2003

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

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

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


Опции темы

Быстрый переход:

  Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения
BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Support by DrIQ & Netwind