在文本文件中查找子串的最快方法

在文本文件中查找字符串的最快方法是什麼？案例場景：在列出大約50000個文件路徑的文本文件中查找特定路徑（每個路徑都有它自己的行）。在文本文件中查找子串的最快方法

2009-08-07 shadeMe

這個大小的文件應該很容易適應內存，並且可以將它作爲它的項目作爲std :: set（或者甚至更好的哈希集合，如果有庫的話）。檢查一條確切的路徑是否會非常快。

如果您還需要查找子路徑，排序的std :: vector（如果您只查找前綴）可能是唯一有用的方法 - 或者如果您正在尋找完整的一般子串的路徑，那麼無論如何你都需要掃描所有的矢量，但除非你必須做數十億次，即使這樣也不會太壞。

2009-08-07 04:59:07

我懷疑，這是最快的方法 - 其最簡單的。如果以最快的方式搜索特定路徑，爲了讀取每一行，將其與搜索到的路徑進行比較並在找到匹配後立即中止。其他一切都是開銷。除此之外，std :: hash_set通常比std :: set快得多。 – 2009-08-07 11:26:06

是的，我確實推薦了一個哈希集，如果你有一個庫，那麼儘管標準違規的'std：'前綴某些庫使用，但記住它不在C++標準中。按照您的建議，將I/O和CPU工作混合在一起，以一次吞吐的方式讀取幾個100 KB的數據，實驗速度更快（至少在多任務系統上具有良好的FS，磁盤緩存，預讀等） - 今天，磁盤I/O比線性讀取（100KB <1msec）要多得多，並且混合容易允許上下文切換，導致尋道（因爲其他進程將在磁盤上的其他地方尋找）。 – 2009-08-07 16:07:41

我花時間寫了一個基準樣本。你錯了：用80000行讀取一個5MB文件在一臺好機器上需要大約0.60秒的時間，包括每行讀取的strcmp。如果我省略了strcmp，而是建立了一個std :: set，運行時間增加到了0.75s。 – 2009-08-10 11:41:15

這是正則表達式的字段;你應該看看grep和awk。

來源

2009-08-07 05:49:41 Tordek

您是否必須在文件中找到一個字符串，同一個字符串在多個文件中重複出現，同一個文件中有多個字符串？

根據情況，你有幾個可能的答案。

構建數據stucture（如由亞歷克斯提議下集）是有用的，如果你有使用像Boyer-Moore的算法是有效的，如果你要搜索找到在同一個文件
幾串一個字符串
使用正則表達式引擎可能會更好，如果你必須搜索幾個字符串。

來源

2009-08-07 06:43:38 AProgrammer

我不確定你想使用搜索的程度，但是FSM是很好的選擇。

這裏是討論：Short example of regular expression converted to a state machine?

來源

2009-08-07 07:14:49

在文本文件中查找子串的最快方法

回答

相關問題