最快的搜索算法

我想實現一個算法來搜索某個記錄的多個XML文件。已知記錄沒有排序（我沒有索引編號）。搜索該記錄的最快算法是什麼？
請讓我知道如果有什麼是提前最快的搜索算法

來源

2010-07-13 Moayyad Yaghi

當然，它聽起來像你應該預處理XML文件，並建立一個索引，以促進快速搜索。 – polygenelubricants 2010-07-13 10:29:16

是的，如果你想搜索一次或多次，這很重要。因爲那你可能需要建立一個索引。但是，如果你只搜索一次，這將是無用的。 – galambalazs 2010-07-13 10:32:25

有趣的問題。我想知道我們何時會看到來自Moayyad的一些反饋，特別是關於一次或多次訪問的問題？ – 2010-07-13 13:17:23

galambalazs是正確的：未排序的數據意味着你必須要經歷這一切尋找你所需要的。但這只是解決問題的一小部分。

在處理多個文件時，可能大部分處理時間將被文件I/O佔用。按照計算機標準，需要很長時間才能在目錄中找到文件並將其打開。但無論您最終使用哪種程序，這都是基本上會產生的成本。

性能等式的另一部分是您使用的解析器。根據XML的結構，您可以選擇使用手寫解析器，DOM XML解析器或Sax解析器。

如果圍繞您尋找的數據的標籤總是出現在與該數據相同的行上並且不存在歧義，則逐行讀取文件並通過字符串搜索或正則表達式進行搜索是一種有效的可能性。 SO上的許多人會抗議正則表達式匹配是處理XML的可怕方式，這通常是正確的;在一組非常特定和有限的情況下執行搜索是一種快速和骯髒的方法，並且對於最終使用的XML結構而言非常脆弱。

DOM解析器將您的整個XML文檔「吸入」到內存中的結構，然後您的應用程序可以按順序搜索它的任何內容。當您想要在XML樹上執行許多複雜的操作時，DOM非常棒;對於順序搜索他們是一個可怕的想法，因爲

所需的內存量與文件大小成正比，所以一個大文件可能會讓你運行內存不足。
必須從文件內容構建大型數據結構。一次搜索後，它會立即被丟棄。計算和內存資源將最終被浪費。

因此，最推薦的方法是使用SAX解析器。谷歌搜索會找到你一個最喜歡的語言。 SAX解析器掃描您的輸入文件一次，在您可以（並且必須）以適當方式處理的每個元素上生成事件。數據是按順序處理的，除了您決定對所找到的數據做什麼以外，沒有其他存儲空間。 SAX解析器通常比DOM解析器快得多，但需要對如何處理事件進行一些規劃。

來源

2010-07-13 10:38:18

另外，可以使用XPath。雖然，實施細節很重要。例如。據我所知，默認的Java XPath實現基於DOM解析器，因此繼承了其所有的性能影響。但XPath的表現力如此強烈以至於有時候會超出性能=） – Rorick 2010-07-13 12:29:28

現在您已經提到它了，一種合理且非常「XML-y」的方式可能是使用XSLT將XML輸入文檔轉換爲任意輸出文檔，其中包含只是搜索字符串。這裏的吸引力在於，很有可能將Transformer掛接到SAX源，從而確保（可能？）輸入只能按順序處理。這可以讓您將用於定義搜索的XPath表達式的表達性與SAX解析的速度結合起來。 – 2010-07-13 13:15:47