2

我有一些由 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) 时间

4

2 回答 2

0

当您在 Unix/Posix 下运行它时，您可以 mmap() 整个文件并对内存进行操作（并避免 lseek() 和朋友）。

因此，您会得到一个 'char *logbuffer = mmap(...)' 指针，并且可以在那里执行二进制搜索。

于 2013-10-31T15:16:47.320 回答
0

是的你可以。这是按日期排序的日志。为什么不取第一行和最后一行，它应该是最近和最近的日期。

您可以制作一个将日期转换为秒的函数。在第一次通话中转到您的日志中间并检查您的日期是否更大或更小等等......（二进制搜索）

希望这会有所帮助，并希望我对这将如何工作的解释清楚

于 2013-10-31T14:53:27.983 回答