字符串搜索算法

Question

我有一個關於基準測試字符串匹配算法的項目，我想知道是否每個算法都有一個標準，這樣我就可以用我的實驗獲得公平的結果。我打算使用java的system.nanotime來獲取每個算法的運行時間。非常感謝對我的問題的任何評論或反應。謝謝！

Answer 1

我不完全確定你在問什麼。不過，我猜你正在問如何得到最現實的結果。你需要運行你的算法數百次，甚至數千次迭代才能獲得平均值。關閉你的語言可能做的任何緩存也是非常重要的，並且不要重用對象，除非它是你的算法的一部分。

Answer 2

我不完全確定你在問什麼。然而，對於你所問的問題的另一種解釋可以通過試圖找出給定算法如何增加問題的大小來解決。使用原始時間比較給定字符串大小的算法不一定能夠進行準確的比較。相反，您可以嘗試使用不同字符串大小的每種算法，並查看算法在字符串大小變化時的行爲。

馬克的建議也不錯。因此，您正在對許多不同的字符串長度進行重複試驗，以獲得一個算法如何工作的圖片，然後針對下一個算法重複該操作。

Answer 3

再次，目前還不清楚你問什麼，但這裏除了又一想什麼託尼和馬克說：

要非常小心，只測試「真實」輸入或只是「隨機」的輸入。一些算法被調整爲在典型輸入（在英文文本中搜索單詞）上做得很好，而另一些算法則被調整用於在病態嚴重病例中良好工作。您需要各種不同類型和大小的可能輸入的大量組合才能做出真正的好的基準。