Поиск даты и времени в файле журнала с помощью бинарного поиска в C/C++

Question

У меня есть несколько файлов журнала, который записан в формате log4cpp

- По характеру log4cpp, этот файл отсортирован по дате и времени в начале каждой строки

Предполагая, что формат похож

2012-09-02 17:17:36.891 This is line 1 in file 2   
...
2013-08-05 14:17:35.344 This is line 607082 in file 2
2013-08-05 14:17:36.891 This is line 607083 in file 2
...
2013-09-05 14:27:36.891 This is line 934594 in file 2

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

Например, если я бегу

./my_program -start_time "2013-08-05 14:17:36" file_2.txt

Я ожидаю, что эта программа может вернуть 607083 в результате.

Кроме того, -start_time может основываться на другой степени детализации, например "2013-08-05 14:17:35.899" или "2013-08-15", но я ожидаю ближайшего результата.

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

Мне интересно, можем ли мы использовать бинарный поиск для этого. Я думаю, что это лучший способ вернуть ближайший результат и занимает всего O (LGN) времени

Answer 1

Да, ты можешь. Это заказанный журнал по дате. Почему бы не взять первую и последнюю строку, которая должна быть самой последней и последней последней датой.

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

Надеюсь, что это поможет, и надеюсь, что мое объяснение о том, как это будет работать, понятно

Answer 2

Когда вы запускаете его под Unix/Posix, вы можете mmap() весь файл и работать с памятью (и избегать lseek() и друзей).

Таким образом, вы получаете указатель 'char *logbuffer = mmap(...)' и можете выполнять там бинарный поиск.