辞書の中で最大の鍵を取得

Question

私はint型のキーを持つ辞書を持っています。私は最大の鍵を取得したいと思います。キーを追跡してキーが連続しないようにします（たとえば1,2,3,4,5,6など）が、スキップ（1,3,4,5）する可能性がありますが、違いはありません。

バイナリ検索を使用するだけですか、それとも方法がありますか？私が見る限り、このような簡単な作業のバイナリ検索はほとんどできません。おそらく半分にすることができます。

Answer 1

あなたが利用できるLINQを持っている場合は、あなたが行うことができるはず：

Answer 2

バイナリ検索が最速になりますが、キーはいずれにも保存されていないため、通常の辞書に対して動作しません特定の順序。 Linq Max()を使用して@ Minitechの答えは、あなたが通常の辞書を使用している場合、最も簡単です。

これは何度も行わなければならない操作であれば、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 

EDIT：このは、通常の辞書より遅くなる可能性があります。それについて言及することは良いことだと思います。辞書のエントリは異なる方法で保存されているためです（レッド/ブラックツリーは、ハッシュバケット/ハッシュテーブルVS）

ははSortedDictionaryが通常Dictionaryよりも速くなった点があります。しかし、これはおそらく約100万アイテムになると思われますが、これは単なる推測です。それは多くの項目で約10倍速くなっています（しかし、とにかく100分の1秒を話していますので、は本当にとなりますか？）。それは100000アイテムのx64リリースではほぼ同じです。アイテムを辞書に追加する余分なオーバーヘッドがあることを考えると、それはおそらくそれに値するものではありません。また、私は逆に並べ替えるようにcomparerをオーバーライドすることによってちょっと気になったので、実際には最大の項目を得るために最後の代わりにdict.Keys.First()をやっています。

SortedDictionaryは、すべてのキー値のペアを順番に反復処理する必要がある場合にのみ使用します。私は@ SimonMourierの答えはおそらく最高だと思います。私はそれが最小限のオーバーヘッドで最速であることを保証します。

Answer 3

パフォーマンスが本当に問題であるならば、私は標準インタフェースを実装する、既存の上に新しいクラスを作成し、次のように：

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...