Java中.indexOf方法的算法選擇

我只是看着Java的String類的.indexOf()方法的實現，看起來代碼的作者使用蠻力算法來查找給定字符串中的子字符串。也就是說，該方法在O（mn）中運行，其中m和n分別是源字符串和目標字符串的長度。Java中.indexOf方法的算法選擇

爲什麼沒有作者使用像Rabin-Karp這樣的更有效的算法，如果提供了一個好的散列函數，那麼它的運行時複雜度爲O（m + n）？

我可能錯過了此實現原因背後的完整知識，因此想要了解。

來源

2011-02-14 name_masked

你在說'String.indexOf（String）`嗎？ `substring（）`創建一個新的String。 – ILMTitan 2011-02-14 20:59:23

我不知道爲什麼做出這個決定，但如果我猜測這可能是因爲對於小型模式字符串（一個非常常見的用例），天真的蠻力算法可能速度如果不快一些像Rabin-Karp，Boyer-Moore或Knuth-Morris-Pratt這樣漸近較快的算法。這看起來像是一個合理的默認算法，因爲在很多情況下，您將爲小模式搜索小字符串，並且強大的匹配設置的開銷可能與幼稚方法的運行時間相當。

也就是說，在Java規範中沒有任何地方要求使用這種算法。他們可以輕鬆地選擇Rabin-Karp作爲默認算法。

他們選擇這種方法的另一個原因是因爲如果你想做快速文本搜索，正則表達式庫提供更快的字符串匹配和更強大的搜索功能。默認情況下向用戶提供簡單的強力算法，並且在需要時切換到更強大的一組工具似乎是一種平衡漸進效率和實用效率的好方法。

來源

2011-02-14 21:05:44 templatetypedef

公平起見，正則表達式庫只是最近才添加的，所以它不可能是`indexOf（）`天真實現的原因。 – biziclop 2011-02-14 21:45:26

我假設你的意思是indexOf或包含而不是子字符串。子串是O（1）

通常簡單的代碼運行得更快。例如，創建對象的代碼通常運行速度較慢。

爲什麼不嘗試自己實現它，看看它是否更快。如果是這樣，你可以建議他們改進方法。

來源

2011-02-14 21:00:36

只需要注意，如果考慮> = Java 7，更新6以後，Substring不再是O（1）。 – Swapnil 2017-09-12 17:12:41

我想他們並不認爲人們會將它用於非常大的字符串。字符串長度小於100時不會有太大的不同。

來源

2011-02-14 21:02:53 fastcodejava

只是一個猜測，但請記住由於國際原因，Java字符串存儲爲UTF-16，而不是純8位ASCII。這可能是支持UTF-16（以及更難的UTF-8）的一些algorthims可能會有問題。只是猜測，但。

來源

2011-02-14 21:13:54

Java中.indexOf方法的算法選擇

回答

相關問題