c＃.net Compact Framework 3.5中最快的字典查找

我正在尋找最快的查找方式，如果列表，集，字典包含特定的關鍵字（字符串）。我不需要存儲任何數據，我只想知道我的關鍵字是否在列表中。c＃.net Compact Framework 3.5中最快的字典查找

我想過像一些可能性：

Dictionary<string, bool> myDictionary = new Dictionary<string, bool>(); 
if (myDictionary.ContainsKey(valueToSearch)) 
{ 
    // do something 
}

，但我並不需要一個值。

string[] myArray = {"key1", "key2", "key3"} 
if (Array.IndexOf(myArray, valueToSearch) != -1) 
{ 
    // do something 
}

然後我發現：

List<string> list = new List<string>(); 
if (list.Contains(valueToSearch))  
{ 
    // do something 
}

查找會經常發生，具有非常快。任何想法什麼是最快的方法來檢查一個值是否是給定的鍵列表之一？

來源

2011-04-12 Haiperlink

爲什麼你沒有得到RedGate Profiler的副本並自己運行一些測試？它會給你一個很好的指示，看看會更快。有些事情會影響性能，如項目的順序和使用的算法以及列表的大小。我打算這樣做，但我的試用期已過期http://www.red-gate.com/products/dotnet-development/ants-performance-profiler/ – 2011-04-12 14:47:46

哪種數據結構最快通常與問題的大小緊密相關，數據的冗餘度，查詢的分佈以及「垃圾」（即不匹配）查詢的可能性。我們在製作編譯器局部變量查找表時遇到的問題與您在快速查找Scrabble字典時遇到的問題完全不同。局部變量表很小並且查詢傾向於集羣;拼字遊戲字典很大，查詢很少重複。你能更詳細地描述問題的特徵嗎？ – 2011-04-12 15:34:30

在標準集合類型中，Dictionary將是最快的，因爲我認爲您在緊湊框架中沒有HashSet<T>。另外兩個進行順序搜索。

來源

2011-04-12 14:42:01

我不確定是否正確解釋了MSDN，但看起來HashSet 包含在緊湊框架中。 [HashSet 文檔]（http://msdn.microsoft.com/en-us/library/bb359438（v = VS.100）.aspx） – Justin 2011-04-12 14:48:11

@Justin：HashSet在CF中不可用。 – ctacke 2011-04-12 14:56:23

@ctacke - 啊，我現在看到 - 我在MSDN上讀到了「客戶端配置文件」，並認爲「緊湊框架」。 – Justin 2011-04-12 14:59:30

一般而言，只要您的密鑰是良好的散列值，在字典的查找表中得到一個均勻的分佈，字典查找就是這樣的問題的常見解決方案。

但是，在某些情況下，列表查找似乎運行得更快，具體取決於數據的排序方式以及查找的內容。

要告訴的最好方法是運行每個案例的配置文件，並查看哪個更好。

來源

2011-04-12 14:45:16

我同意安迪。你也可以看看SortedList它本質上是一個按鍵排序的字典。如果它已經排序，應該更快地搜索...

來源

2011-04-12 14:58:34 tobias86

排序項目不會增加查找速度，因爲'SortedDictionary'仍然使用散列表進行查找。哈希表查找是O（1）操作。在排序列表中搜索通常是O（log n）操作。唯一的一次搜索將超越哈希查找是，如果哈希表有過多的衝突（意味着哈希函數不足或表幾乎滿）。 – 2011-04-12 15:09:01

c＃.net Compact Framework 3.5中最快的字典查找

回答

相關問題