搜索一个日期/ C++

写 - 截至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年8月5日14时17分36秒” file_2.txt

我期待这个程序可以返回607083结果。

此外，-start_time可以基于其他粒度，如“2013-08-05 14：17：35.899”或“2013-08-15”但我期待的是最近的结果。

我可以逐行遍历这个文件，并比较每行开头的时间戳（只是使用字符串比较），但它会花费O（N）时间。我已经实现了它，并且发现如果在开始时有数百万行跳过，它真的很慢。

我想知道是否可以使用二进制搜索。我认为这是最好的方式返回最接近的结果，只需要O（lgN）时间

来源

2013-10-31 Yifei

你应该剖析你的程序并找出什么是慢的部分，我期望（如果文件很大）大部分时间都花在阅读文件上，而不是比较字符串值。这将指出如何优化（更大的读取缓冲区等）。 – Hogan

对我有意义。将文件大小分成两半，寻找那个位置，找到最近的\ n，解析日期和时间 - >选择哪一半继续挖掘。如果日期和时间不断增加，您最终会找到您要搜索的内容。 – Anton

@Anton这些行不按时间排序。 – this

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

您可以制作一个将日期转换为秒的功能。在第一次调用去你的日志中，请检查是否您的日期是更大或更小等等...（二进制搜索）

希望这有助于，并希望我这是如何将工作解释清楚

来源

2013-10-31 14:53:27 artud2000

是的，这就是我的想法。但在C++中，我发现使用seekg和tellg来操纵位置很困难。它支持+运营商吗？ – Yifei

不确定它是否支持+操作符，但是您可以使用seekg从当前位置前后移动，使用seekg难以管理位置。让我想想如何管理文件中的位置，我会尽快回复您 – artud2000

当您在Unix/Posix下运行它时，您可以mmap（）整个文件并在内存上运行（并避免lseek（）和朋友）。所以，你会得到'char * logbuffer = mmap（...）'指针，并且可以在那里执行二分搜索。

来源

2013-10-31 15:16:47 ensc

感谢您的回答！但这是一个更大的应用程序的子问题，我必须同时在一堆大文件上执行此操作。所以我想立即执行它，而不是将它们全部加载到内存中:-) – Yifei

mmap（）很便宜;您只分配一些内部管理对象。因此阅读例如char字符[8192]'消耗的内存可能比mmap（）'太大的文件大。 – ensc

搜索一个日期/ C++

回答

相关问题