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

C++

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

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

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

Как можно организовать быстрый поиск по файлу? Файл может весить гигабайты. Никакой сортировки нет. Пробовал реализовать используя функции fopen, fseek, fgets. Есть ли более быстрые функции? Или быстрее будет через Winapi к примеру? Интересно, как это сделали в антивирусах, им то тоже очень важна скорость, притом что существует огромное разнообразие вирусов и надо с каждым сравнить.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2014, 19:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрый поиск по большому файлу (до нескольких гигабайт) (C++):

Быстрый поиск - C++
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в исходном наборе чисел. Написал такой поиск, но работает...

Быстрый поиск в мапе - C++
Есть мапа вида : std::map<size_t, std::string> Нужно найти элемент меньший или равный элементу из rbf с конца мапы. Есть ли быстрый...

Быстрый поиск элемента - C++
Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в...

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

Быстрый поиск минимального числа - C++
подскажите быстрый алгоритм поиска второго минимального числа в массиве?

Быстрый поиск по полям в коллекции - C++
Есть коллекция объектов класса с разными полями. Нужно организовать быстрый поиск первого элемента (может потом множества элементов) по...

6
ВАСИЛЕВС
556 / 479 / 60
Регистрация: 14.02.2012
Сообщений: 1,561
23.08.2014, 20:15 #2
Есть такая штука как отображение файла в память. Считается, что работа с памятью намного быстрее, к тому же обработка файла большими кусками будет более оптимальной методикой для этой задачи.
1
fluer
Заблокирован
23.08.2014, 23:18 #3
Интересно, как это сделали в антивирусах
Там базы данных используются. Вот и вы их используйте.
Файл базы данных читается не так, как обычный файл (т.е. целиком), а более быстрым методом.
0
ValeryS
Модератор
6651 / 5060 / 470
Регистрация: 14.02.2011
Сообщений: 16,918
23.08.2014, 23:42 #4
Цитата Сообщение от N0 Посмотреть сообщение
Интересно, как это сделали в антивирусах, им то тоже очень важна скорость, притом что существует огромное разнообразие вирусов и надо с каждым сравнить.
давно уже не сравнивают
иначе поменяй один байт и новый вирус никакой базы не хватит
там идет поиск по сигнатурам эвристика и еще много чего
а задача поиска в файле не подразумевает быстрого решения
набери например в поиске все файлы содержащие "мама", сколько комп шерстить будет
убыстрить можно или как предложил ВАСИЛЕВС, или считывание файла по кускам и работа в памяти
например
файл 1 мб нужно найти строку из 10 символов
считываем первые 100 кБ ишем
не нашли тогда считаваем еще 100 кБ
но с места не 100 000 а с 100 000-10(количество символов), это чтобы не нарваться если искомая строка будет на границе
а в памяти ты уже можешь и сортировку и двоичный поиск и что душа пожелает
исходник то не испортится
1
gazlan
3132 / 1908 / 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
0
N0
0 / 0 / 0
Регистрация: 23.08.2014
Сообщений: 2
24.08.2014, 03:59  [ТС] #6
Только вот ещё вопрос, многопоточность в этом может помочь?
0
gazlan
3132 / 1908 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
24.08.2014, 04:07 #7
Цитата Сообщение от N0 Посмотреть сообщение
многопоточность
Может. Есть и аппаратные (многопроцессорные) и программные реализации, но это последнее, с чем я ствл бы связываться, если сигнатура может разделяться смежными или перекрывающимися сегментами.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.08.2014, 04:07
Привет! Вот еще темы с ответами:

Быстрый поиск в векторе из pair - C++
Пытаюсь сделать вектор: vector< pair<string, string> > myVect; По идее, проще воспользоваться чем-то вроде map или unordered_map,...

Быстрый поиск совершенных чисел - C++
Чтобы легко можно было отсылать вопрошающих по этому вопросу, создаю новую тему. Напомню, что Доказано, что все четные совершенные...

Быстрый поиск ip адреса в текстовом файле - C++
Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько раз). На каждой строчке по 1 ip-адресу. Всего строк ~300...

Подскажите быстрый поиск количества интервалов в отрезке - C++
Есть массив H Есть отрезок x+dx. Задача найти количество интервалов на которое делится отрезок x+dx массивом H. Наверняка с такой...


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

Или воспользуйтесь поиском по форуму:
7
Yandex
Объявления
24.08.2014, 04:07
Ответ Создать тему
Опции темы

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