Поиск большого файла для данных в C / C ++

Question

У меня есть файл журнала в таком формате:

DATE-TIME ### attribute1  ### attribute2 ###attribute3 

Мне нужно найти в этом файле журнала атрибут ввода (введенный из командной строки) и вывести строки, соответствующие введенному атрибуту.
Наивный подход может быть примерно таким:

scan the entire file line by line
search for the attribute
print if found, else ignore.

Этот подход медленный, так как он требует O (n) сравнений, где n - количество строк, которое может быть очень большим.
Другой подход может заключаться в использовании хеш-таблицы, но сохранение такой хеш-таблицы в памяти для большого файла может оказаться невозможным.
Итак, что является лучшим возможным решением? Как я могу индексировать весь файл по различным атрибутам?

EDIT:
Файл журнала может содержать около 100 тыс. Строк, почти как файлы системного журнала в linux. При одном вызове пользователь может искать несколько атрибутов, которые неизвестны до тех пор, пока поиск по 1-му атрибуту не будет завершен, как в интерактивной консоли.

Спасибо

Answer 1

Если вы ищете только один раз, вы не можете сделать лучше, чем O (n).

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

EDIT : Я хотел бы отметить, что инструмент Berkeley DB, который предложил KeithB, попадает в эту категорию для хэшей на диске. Berkeley DB не является реляционной базой данных, использующей SQL.

Answer 2

Вы можете использовать Berkley DB для индексирования этого файла. Как правило, просмотрите весь файл один раз, и для каждого найденного атрибута сохраните положение файла атрибута. Berkley DB использует эффективную реализацию B-Tree и не требует хранения всего индекса в памяти, только необходимых частей. Я делал это раньше с хорошим успехом.

Answer 3

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

Нечастый поиск

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

Частый поиск

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

Другая альтернатива - ваша программа преобразует файл в формат, который может использовать лучший инструмент, например электронную таблицу или базу данных.Одним из примеров является Comma Separate Values ​​или некоторые инструменты, которым нравится разделять значения через '|'.

Смена генератора

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

Answer 4

Звучит как работа для системы баз данных.

Как я могу проиндексировать весь файл по различным атрибутам?

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

Вы также можете найти Map-Reduce интереса.

Answer 5

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

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

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

Answer 6

Да ладно, серьезно, ребята. База данных для файлов журнала?

Файлы журнала меняются постоянно или, по крайней мере, каждый день. Итак, что вам действительно нужно, это сделать какую-то ротацию файлов журналов, из которых есть много готовых и неудачных, которые можно выполнить за несколько часов, если вы знаете даже небольшой Perl. Вам, вероятно, действительно не нужен С ++ для этого. Это только замедлит время разработки, а конечный результат станет хуже.

Answer 7

Не волнуйся. Просто отсканируйте его.

Серьезно. Вы говорите, что этот файл содержит 100 тыс. Строк, что на самом деле почти соответствует размеру файла / var / log / messages на компьютере, на котором я это печатаю. Ну, это нетбук, то есть очень медленный по современным стандартам - и все же простой анализ моих / var / log / messages настолько быстр, что он затмевается количеством времени, затрачиваемым на вывод результатов на экран.

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

Answer 8

Вы можете попробовать прямой линейный поиск файла, но запустить рабочий поток, чтобы выполнить поиск. Таким образом, вы можете создавать несколько рабочих потоков и запускать их в разных точках файла. На машине с несколькими процессорами / ядрами этот параллелизм должен повысить производительность по сравнению с простым однопоточным линейным поиском.

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

Answer 9

Я бы построил индекс, используя b-дерево или хеш-таблицу. Я бы сохранил индекс на диске. Если вы контролируете обновления этого файла, вы также можете обновить индекс при обновлении файла. Если вы не контролируете обновления, используйте хеш файла, чтобы определить, нужно ли его восстанавливать.

Подумав об этом, я понял, что я обычно ищу файлы журнала с 600k + строками (100M), используя grep в командной строке. Это довольно быстро. Так что я не думаю, что 100k - это проблема, если в ваших файлах не будет больше данных.

Возможно, вы захотите также использовать поворот журнала, если файлы журнала становятся большими.

Answer 10

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

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

Для поиска попробуйте boost :: regex или QRegExp .

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