Поиск нескольких слов в очень больших текстовых файлах (10 ГБ) с помощью C ++ самый быстрый способ

Question

У меня есть эта программа, где я должен искать конкретные значения и номер строки в очень большом текстовом файле, и может быть несколько раз для одного и того же значения.

Я пробовал простые программы на C ++, которыечитает текстовые файлы построчно и ищет значение, используя strstr, но это занимает очень длинное времяgggggggggggggggg

Я также пытался использовать системную команду, используя grep, но все же это занимает много времени, не так долгокак и раньше, но все еще слишком много времени.

Я искал библиотеку, которую можно использовать для ускорения поиска.Любая помощь и предложения?Спасибо:)

Answer 1

Использовать несколько потоков. Каждый поток может отвечать за поиск по части файла. Например на 4-х ядерном компьютере порождаются 12 потоков. Первый поток просматривает первые 8% вечера файла, второй поток - вторые 8% файла и т. Д. Вам нужно будет настроить количество потоков на ядро, чтобы сохранить максимальную загрузку процессора. Поскольку это операция ввода-вывода, вы никогда не достигнете 100% загрузки ЦП.

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

Answer 2

Есть две проблемы, связанные со спидом: время, которое требуется на самом деле прочитайте данные и время поиска.

Вообще говоря, самый быстрый способ прочитать файл - это mmap это (или эквивалент под Windows). Это может осложниться, если весь файл не помещается в адресное пространство, но вы упоминаете 10 ГБ в заголовок; если поиск - это все, что вы делаете в программе, это не должно создавать любые проблемы.

В более общем случае, если скорость является проблемой, избегайте использования getline на string. Чтение больших блоков и сбор строк (как char[]) из них, без копирования, значительно быстрее. (Как простой компромисс, вы можете скопировать, когда линия пересекает границу блока. Если вы имеете дело с блоками по МБ или более, это не должно быть слишком довольно часто; Я использовал эту технику на старых, 16-битных машинах с блоками 32 КБ, и все же получил значительное улучшение производительности.)

Что касается поиска, если вы ищете один, исправлено строка (не регулярное выражение или другое сопоставление с образцом), вы можете хочу попробовать поиск БМ. Если искомая строка достаточно долго, это может иметь существенное значение по сравнению с другими поисковые алгоритмы. (Я думаю, что некоторые реализации grep будут используйте это, если шаблон поиска на самом деле является фиксированной строкой и достаточно долго, чтобы это имело значение.)

Answer 3

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

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

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

Answer 4

Я бы попытался сначала загрузить как можно большую часть файла в ОЗУ (сопоставление памяти файла - хороший вариант), а затем выполнить поиск по частям в нескольких процессорах. Вам нужно будет позаботиться о границах буфера, чтобы не пропустить ни одного слова. Кроме того, вы можете попробовать что-то более эффективное, чем типовая strstr (), см. Эти:
Алгоритм поиска Бойера – Мура
Алгоритм Кнута – Морриса – Пратта

Answer 5

Если ваш большой текстовый файл не часто меняется, то создайте базу данных (например, SQLite) с таблицей:

create table word_line_numbers
  (word varchar(100), line_number integer);

Прочитайте ваш файл и вставьте запись в базу данных для каждого слова с чем-то вроде этого:

insert into word_line_numbers(word, line_number) values ('foo', 13452);
insert into word_line_numbers(word, line_number) values ('foo', 13421);
insert into word_line_numbers(word, line_number) values ('bar', 1421);

Создайте индекс слов:

create index wird_line_numbers_idx on word_line_numbers(word);

И затем вы можете быстро найти номера строк для слов, используя этот индекс:

select line_number from word_line_numbers where word='foo';

Для добавленияскорость (из-за меньшего размера базы данных) и сложность вы можете использовать 2 таблицы: words(word_id integer primary key, word not null) и word_lines(word_id integer not null references words, line_number integer not null).

Answer 6

Если вы хотите использовать библиотеку, вы можете использовать xapian .

Вы также можете попробовать токенизировать свой текст перед выполнением поиска, и я бы также предложил вам попробовать регулярное выражение, но это займет много времени, если у вас нет индекса для этого текста, поэтому я определенно рекомендую вам попробовать xapian или какой-нибудь поисковик.