快速字符串查找的最佳集合

我需要一個字符串列表和一種方法來快速確定字符串是否包含在該列表中。快速字符串查找的最佳集合

爲了提高查詢速度，我考慮了SortedList和Dictionary;然而，兩者都與KeyValuePair s一起工作，當我需要的只是一個string。

我知道我可以使用KeyValuePair並簡單地忽略Value部分。但我更喜歡高效，只是想知道是否有一個更適合我的要求的集合。

2011-04-03 Jonathan Wood

如果您使用.NET 3.5或更高版本，請使用HashSet<String>。

做不到這一點，一個Dictionary<string, byte>（或任何你想要的類型爲TValue類型參數），如果你有很多條目會比SortedList更快 - 後者將使用二進制搜索，因此這將是O（日誌n）查找，而不是O（1）。

來源

2011-04-03 17:31:50

酷，謝謝。（儘管看起來有點奇怪，但直到3.5纔有這樣的課程。） – 2011-04-03 17:33:58

@Jonathan：同意 - 儘管如此。在.NET 4中，有一個接口來表示集合（'ISet '），也是'SortedSet '中的另一個選項（在這種情況下，這又不會特別有用）。 – 2011-04-03 17:37:19

我只是回頭看這個。 O（1）查找確實很快。不過，我猜這個集合實現了某種哈希。那麼O（1）不會假設沒有碰撞？（順便說一下，我正在通過你的書工作。） – 2011-06-16 16:13:02

如果你只是想知道，如果一個字符串是在裝置使用HashSet<string>

來源

2011-04-03 17:32:03 BrokenGlass

HashSet<string>就像一個Dictionary，但只有鑰匙。

來源

2011-04-03 17:32:30

如果您想旋轉自己的數據結構，請使用Trie。 http://en.wikipedia.org/wiki/Trie

最壞情況是如果字符串是本：O（串的長度）

來源

2011-04-03 17:33:20 James

這聽起來像

var keys = new HashSet<string>();

每MSDN作業：將包含函數O（1）複雜。

但是，您應該知道，添加時，它不會給出重複的錯誤。

來源

2011-04-03 17:33:29

更確切地說，Add方法不會引發異常，但如果已添加密鑰，則返回true;如果已存在，則返回false。 – 2011-04-03 17:35:47

@Alois：聽起來很完美。每當有些事情不僅僅是拋出異常時，.NET庫中的大部分習慣總是困擾着我。 – 2011-04-03 17:41:40

我知道這個答案對這個聚會來說有點遲，但我遇到了一個問題，我們的系統運行緩慢。分析後，我們發現有很多字符串查找與我們的數據結構的結構有關。

所以我們做了一些研究，came across these benchmarks，做了我們自己的測試，現在已經切換到使用SortedList。

if (sortedlist.ContainsKey(thekey)) 
{ 
//found it. 
}

儘管字典被證明速度更快，但是我們不得不重構的代碼更少，性能提升對我們來說足夠好。

無論如何，要分享的網站，以防其他人遇到類似問題。他們在數據結構之間進行比較，其中你要查找的字符串是一個「鍵」（如HashTable，Dictionary等），或者是一個「值」（列表，數組或字典等）存儲。

來源

2014-11-10 00:14:15

我知道這個問題已經過時了，但我只需要解決同樣的問題，只適用於一小部分字符串（在2到4之間）。

在我的情況下，我實際上對一串字符串使用了手動查找，結果比HashSet<string>（我測試過它的速度）快得多。

for (int i = 0; i < this.propertiesToIgnore.Length; i++) 
{ 
    if (this.propertiesToIgnore[i].Equals(propertyName)) 
    { 
     return true; 
    } 
}

請注意，它比散列集僅適用於微小陣列！

編輯：只適用於手動for循環，不使用LINQ，在該評論的詳細

來源

2018-01-14 16:08:58

是的，'HashSet <>'有一些開銷。我只會在搜索較大的集合時推薦它。順便說一句，你的代碼可以縮短爲'return PropertiesToIgnore.Any（p => p.Equals（propertyName））' – 2018-01-14 16:12:03

不幸的是，使用Linq減慢了執行速度10倍！基準結果'ArrayManualLoop：6.018 ns''ArrayLinq：59.171 ns'。 Linq將處理器緩存區分開來，所有可能的收益都會丟失。 – 2018-01-14 16:20:40

快速字符串查找的最佳集合

回答

相關問題