執行字符串startsWith

我想，如果提供的字符串與任何一個數組的字符串開始比較Java的最佳途徑。最簡單的解決方案之中：執行字符串startsWith

String b = ...; 
boolean matched = false; 
for (String a : array) { 
    if (b.startsWith(a)) 
    match = true; 
}

然而，直覺，我想使用類似特里結構以獲得更好的效率，因爲字符串數組可能增長到相當大的，我需要運行這些比賽很快。我可以保證這些字符串都是按字母順序排列的。我還可以保證數組中的所有字符串的長度都是2或更小。在Java中實現這種類似於trie的結構的最佳方式是什麼？我找不到任何這樣做的基於Java的庫。

謝謝！

來源

2013-04-16 Jin

你可能看http://stackoverflow.com/questions/623892/where-do -i-發現 - 一個標準 - 特里基於地圖的實現功能於Java或有關分析第一本https://forums.oracle.com/forums/thread.jspa?messageID=8787521 – CPerkins

一個簡單的解決方案是將字符串插入Set<String>，然後對其執行兩個查找，其中一個第一個字符爲b，然後與b的前兩個字符不匹配。

例如，

class StartsWithAny { 
    private Set<String> set; 

    public StartsWithAny(String[] array) { 
     set = new HashSet<String>(); 
     for (String a : array) { 
      set.add(a); 
     } 
    } 

    // returns true if b starts with any strings contained in array 
    // with the condition that b.length() <= 2 
    public boolean startsWithAny(final String b) { 
     if (b.length() > 0 && set.contains(b.substring(0, 1))) { 
      return true; 
     } 

     if (b.length() > 1 && set.contains(b.substring(0, 2))) { 
      return true; 
     } 

     return false; 
    } 
}

在此的變化將是利用兩個獨立的Set S，一個用於單個字符的查找，一個用於在兩個字符查找其它能改善性能有點。

一種替代但類似的方法將是實現將所述排序後的數組上操作並執行類似的功能的二進制搜索算法。

來源

2013-04-16 18:29:05

我真的結束了簡單地使用TreeSet並做一個contains（）查找，不知道這是否比單獨查找顯着更慢/更快，但它只有2個字符，所以它應該沒有那麼大的不同，我想..謝謝對於這個建議！ – Jin

我想比較，如果提供的字符串與任何一個數組中的字符串的開始。

嘛 - 你當然可以在當前解決方案提高：

static boolean startsAny(final String b) { 
    for (String a : array) { 
     if (b.startsWith(a)) { 
      return true; 
     } 
    } 
    return false 
}

可以使用String#matches用正則表達式，但我不知道這是更有效的。你是否分析了代碼並將其識別爲瓶頸？

來源

2013-04-16 17:46:18

這個問題問得好，這速度更快（但不會編譯 - 它需要最後一個'return false'）。 – CPerkins

好的建議分析..這可能是我優化得太早，我會運行一些測試，看看。 – Jin

哎呀，謝謝。 –

如果你真的有成爲一個瓶頸，一個線索可能確實幫助不夠開頭的字符串。

這個問題已經被問和回答了這個非常網站：Where do I find a standard Trie based map implementation in Java?

這就是答案：https://forums.oracle.com/forums/thread.jspa?messageID=8787521

來源

2013-04-16 18:47:12 CPerkins

感謝您的鏈接，我記得看過帖子，沒有看到標準的實施。我最終只使用了一個普通的TreeSet，並在獲取其他庫之前首先分析性能。再次感謝！ – Jin

加1爲鏈接 –

執行字符串startsWith

回答

相關問題