Поиск даты и времени в файле журнала с помощью двоичного поиска в 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) времени

1

Решение

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

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

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

0

Другие решения

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

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

0

По вопросам рекламы [email protected]