Поиск даты и времени в файле журнала с помощью двоичного поиска в C / Stack Overflow
У меня есть некоторые файлы журналов, которые записаны в формате 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) времени
Решение
Да, ты можешь. Это заказанный журнал по дате. Почему бы не взять первую и последнюю строку, которая должна быть самой последней и последней последней датой.
Вы можете сделать функцию, которая конвертирует дату в секунды. во время первого звонка перейдите к середине журнала и проверьте, больше или меньше ваша дата и т. д. (бинарный поиск)
Надеюсь, это поможет, и надеюсь, что мое объяснение того, как это будет работать, понятно
Другие решения
Когда вы запускаете его в Unix / Posix, вы можете mmap () весь файл и работать с памятью (и избегать lseek () и друзей).
Таким образом, вы получаете указатель ‘char * logbuffer = mmap (…)’ и можете выполнять там бинарный поиск.