搜索一個日期/ 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++

回答

相關問題