Форум программистов, компьютерный форум CyberForum.ru

Быстрый поиск по большому файлу (до нескольких гигабайт) - C++

Восстановить пароль Регистрация
 
N0
0 / 0 / 0
Регистрация: 23.08.2014
Сообщений: 2
23.08.2014, 19:38     Быстрый поиск по большому файлу (до нескольких гигабайт) #1
Как можно организовать быстрый поиск по файлу? Файл может весить гигабайты. Никакой сортировки нет. Пробовал реализовать используя функции fopen, fseek, fgets. Есть ли более быстрые функции? Или быстрее будет через Winapi к примеру? Интересно, как это сделали в антивирусах, им то тоже очень важна скорость, притом что существует огромное разнообразие вирусов и надо с каждым сравнить.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ВАСИЛЕВС
555 / 478 / 60
Регистрация: 14.02.2012
Сообщений: 1,561
23.08.2014, 20:15     Быстрый поиск по большому файлу (до нескольких гигабайт) #2
Есть такая штука как отображение файла в память. Считается, что работа с памятью намного быстрее, к тому же обработка файла большими кусками будет более оптимальной методикой для этой задачи.
fluer
Заблокирован
23.08.2014, 23:18     Быстрый поиск по большому файлу (до нескольких гигабайт) #3
Интересно, как это сделали в антивирусах
Там базы данных используются. Вот и вы их используйте.
Файл базы данных читается не так, как обычный файл (т.е. целиком), а более быстрым методом.
ValeryS
Модератор
6405 / 4871 / 447
Регистрация: 14.02.2011
Сообщений: 16,167
23.08.2014, 23:42     Быстрый поиск по большому файлу (до нескольких гигабайт) #4
Цитата Сообщение от N0 Посмотреть сообщение
Интересно, как это сделали в антивирусах, им то тоже очень важна скорость, притом что существует огромное разнообразие вирусов и надо с каждым сравнить.
давно уже не сравнивают
иначе поменяй один байт и новый вирус никакой базы не хватит
там идет поиск по сигнатурам эвристика и еще много чего
а задача поиска в файле не подразумевает быстрого решения
набери например в поиске все файлы содержащие "мама", сколько комп шерстить будет
убыстрить можно или как предложил ВАСИЛЕВС, или считывание файла по кускам и работа в памяти
например
файл 1 мб нужно найти строку из 10 символов
считываем первые 100 кБ ишем
не нашли тогда считаваем еще 100 кБ
но с места не 100 000 а с 100 000-10(количество символов), это чтобы не нарваться если искомая строка будет на границе
а в памяти ты уже можешь и сортировку и двоичный поиск и что душа пожелает
исходник то не испортится
gazlan
3082 / 1857 / 277
Регистрация: 27.08.2010
Сообщений: 4,998
Записей в блоге: 1
24.08.2014, 00:49     Быстрый поиск по большому файлу (до нескольких гигабайт) #5
Цитата Сообщение от N0 Посмотреть сообщение
Есть ли более быстрые функции?
Boyer–Moore string search algorithm

Или быстрее будет через Winapi
Угу. Вам уже написали про Memory-mapped file


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

существует огромное разнообразие вирусов и надо с каждым сравнить
Aho–Corasick string matching algorithm
N0
0 / 0 / 0
Регистрация: 23.08.2014
Сообщений: 2
24.08.2014, 03:59  [ТС]     Быстрый поиск по большому файлу (до нескольких гигабайт) #6
Только вот ещё вопрос, многопоточность в этом может помочь?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.08.2014, 04:07     Быстрый поиск по большому файлу (до нескольких гигабайт)
Еще ссылки по теме:

C++ Как сделать быстрый поиск по массиву разнотипных данных?
Быстрый поиск C++
C++ Быстрый поиск минимального числа
C++ Быстрый поиск по полям в коллекции
C++ Быстрый поиск подстроки в строке (Кнута-Морриса-Пратта)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
gazlan
3082 / 1857 / 277
Регистрация: 27.08.2010
Сообщений: 4,998
Записей в блоге: 1
24.08.2014, 04:07     Быстрый поиск по большому файлу (до нескольких гигабайт) #7
Цитата Сообщение от N0 Посмотреть сообщение
многопоточность
Может. Есть и аппаратные (многопроцессорные) и программные реализации, но это последнее, с чем я ствл бы связываться, если сигнатура может разделяться смежными или перекрывающимися сегментами.
Yandex
Объявления
24.08.2014, 04:07     Быстрый поиск по большому файлу (до нескольких гигабайт)
Ответ Создать тему
Опции темы

Текущее время: 08:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru