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

C++

Войти
Регистрация
Восстановить пароль
 
N0
0 / 0 / 0
Регистрация: 23.08.2014
Сообщений: 2
#1

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

23.08.2014, 19:38. Просмотров 650. Ответов 6
Метки нет (Все метки)

Как можно организовать быстрый поиск по файлу? Файл может весить гигабайты. Никакой сортировки нет. Пробовал реализовать используя функции fopen, fseek, fgets. Есть ли более быстрые функции? Или быстрее будет через Winapi к примеру? Интересно, как это сделали в антивирусах, им то тоже очень важна скорость, притом что существует огромное разнообразие вирусов и надо с каждым сравнить.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2014, 19:38     Быстрый поиск по большому файлу (до нескольких гигабайт)
Посмотрите здесь:
Быстрый поиск C++
Быстрый поиск элемента C++
Быстрый поиск в векторе из pair C++
C++ Быстрый поиск минимального числа
Быстрый поиск совершенных чисел C++
Быстрый поиск супернатуральных чисел C++
C++ Быстрый поиск по полям в коллекции
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ВАСИЛЕВС
555 / 478 / 60
Регистрация: 14.02.2012
Сообщений: 1,561
23.08.2014, 20:15     Быстрый поиск по большому файлу (до нескольких гигабайт) #2
Есть такая штука как отображение файла в память. Считается, что работа с памятью намного быстрее, к тому же обработка файла большими кусками будет более оптимальной методикой для этой задачи.
fluer
Заблокирован
23.08.2014, 23:18     Быстрый поиск по большому файлу (до нескольких гигабайт) #3
Интересно, как это сделали в антивирусах
Там базы данных используются. Вот и вы их используйте.
Файл базы данных читается не так, как обычный файл (т.е. целиком), а более быстрым методом.
ValeryS
Модератор
6537 / 5003 / 460
Регистрация: 14.02.2011
Сообщений: 16,635
23.08.2014, 23:42     Быстрый поиск по большому файлу (до нескольких гигабайт) #4
Цитата Сообщение от N0 Посмотреть сообщение
Интересно, как это сделали в антивирусах, им то тоже очень важна скорость, притом что существует огромное разнообразие вирусов и надо с каждым сравнить.
давно уже не сравнивают
иначе поменяй один байт и новый вирус никакой базы не хватит
там идет поиск по сигнатурам эвристика и еще много чего
а задача поиска в файле не подразумевает быстрого решения
набери например в поиске все файлы содержащие "мама", сколько комп шерстить будет
убыстрить можно или как предложил ВАСИЛЕВС, или считывание файла по кускам и работа в памяти
например
файл 1 мб нужно найти строку из 10 символов
считываем первые 100 кБ ишем
не нашли тогда считаваем еще 100 кБ
но с места не 100 000 а с 100 000-10(количество символов), это чтобы не нарваться если искомая строка будет на границе
а в памяти ты уже можешь и сортировку и двоичный поиск и что душа пожелает
исходник то не испортится
gazlan
3130 / 1905 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 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++ Быстрый поиск ip адреса в текстовом файле
C++ Подскажите быстрый поиск количества интервалов в отрезке
Быстрый поиск наиболее близких вершин графа C++
C++ Быстрый поиск подстроки в строке (Кнута-Морриса-Пратта)
C++ Как сделать быстрый поиск по массиву разнотипных данных?

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

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

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