獲取字典中的最大密鑰

我有一個帶有ints鍵的字典。我想獲得最大的關鍵。我沒有跟蹤密鑰，所以它們可能是連續的（例如1,2,3,4,5,6），但可能會跳過（1,3,4,5），儘管我懷疑這有什麼區別。獲取字典中的最大密鑰

我只是使用二進制搜索還是有方法？就我所見，你幾乎無法擊敗二進制搜索這樣一個簡單的任務 - 也許你可以將它減半。

來源

2011-11-29 s5s

字典不排序所以二進制搜索會做你小好。 –

@AustinSalonen'詞典'沒有排序，但它提到有一些'IDictionary '的有序實現。 – phoog

如果你有LINQ提供，你應該能夠做到：

來源

2011-11-29 17:36:18 Ryan

對於任何想要使用它的人來說，你需要確保你包含linq擴展方法'Imports System.Linq'，並且編譯成.net 3.5+ - 作品一個treat然後:) – HeavenCore

二進制搜索將是最快的，但不會對正常的字典工作，因爲該鍵不被存儲在任何特定的順序。 @ Minitech的答案，使用Linq Max()，是最簡單的，如果你使用一個正常的字典。

如果這是一個操作，你將不得不做很多次，你可能會考慮移動到一個SortedDictionary<TKey, TValue>，根據密鑰對條目進行排序。

var dict = new SortedDictionary<int, int> {{3, 0}, {12, 0}, {32, 0}, 
              {2, 0}, {16, 0}, {20, 0}}; 
Console.WriteLine(dict.Keys.Last()); //prints 32

編輯：這可以比正常慢字典。我想這件事本來很好。這是因爲在字典中的條目存儲在以不同的方式（紅/黑樹VS散列桶/哈希表）

有是點在於SortedDictionary變得比正常Dictionary更快。不過，這可能會達到100萬件左右，但這只是一個猜測。事實證明，它在許多物品上的速度快了10倍（但是我們仍然在談論第100秒，所以真的是很重要？）。對於100000個項目，它在x64版本上大致相同。考慮到向字典添加項目會帶來額外的開銷，這可能不值得。此外，我通過覆蓋比較器來「欺騙」一些，所以它會按相反的順序排序，所以我實際上是在執行dict.Keys.First()而不是最後一個來獲得最大的項目。

如果您需要按順序遍歷所有Key Value對，那麼SortedDictionary真的適用。我認爲@ SimonMourier的答案可能是最好的。我向你保證它是最快的，只需很少的開銷。

來源

2011-11-29 17:42:58

由於字典排序，下面的代碼也可以使用：'dict.Last（）。Key;' – Jordan

如果性能是一個真正的問題，我會創建一個現有的頂部一個新的類，實現了標準接口，如：

public class RememberMaxDictionary<K, V> : IDictionary<K, V> where K: IComparable<K> 
    { 
     private Dictionary<K, V> _inner; 

     public RememberMaxDictionary() 
     { 
      _inner = new Dictionary<K, V>(); 
     } 

     public K MaxKey { get; private set; } 

     public void Add(K key, V value) 
     { 
      _inner.Add(key, value); 

      if (key.CompareTo(MaxKey) > 0) // test null if needed 
      { 
       MaxKey = key; 
      } 
     } 

    ... TODO implement the rest...

來源

2011-11-29 18:05:21

獲取字典中的最大密鑰

回答

相關問題