Ottieni la chiave più grande in un dizionario

Question

Ho un dizionario con chiavi che sono ints. Mi piacerebbe avere la chiave più grande. Non tengo traccia delle chiavi in ​​modo che possano essere consecutive (ad esempio 1,2,3,4,5,6) ma potrebbero saltare (1,3,4,5) anche se dubito che ciò faccia qualche differenza.

Ho appena usato una ricerca binaria o c'è un metodo? Per quanto vedo, difficilmente puoi battere la ricerca binaria per un compito così semplice - forse puoi dimezzarlo.

Answer 1

Se si dispone di LINQ a disposizione, si dovrebbe essere in grado di fare:

Answer 2

una ricerca binaria sarebbe il più veloce, ma non avrebbe funzionato contro un dizionario normale, dal momento che le chiavi non vengono memorizzati in qualsiasi ordine particolare. @ La risposta di Minitech, utilizzando Linq Max(), è la più semplice se si utilizza un dizionario normale.

Se si tratta di un'operazione che dovrà essere eseguita molte volte, è possibile prendere in considerazione il passaggio a SortedDictionary<TKey, TValue> che ordina le voci in base alla chiave.

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: Questo può essere più lenta di un dizionario normale. Suppongo che sarebbe stato bello dirlo. Questo perché le voci del dizionario sono memorizzati in modo diverso (a/albero Nero Rosso vs secchi hash/tabella di hash)

C'è è un punto che il SortedDictionary diventa più veloce di un normale Dictionary. Tuttavia, questo probabilmente dovrebbe essere di circa 1 milione di articoli, tuttavia è solo un'ipotesi. Si scopre che è circa 10 volte più veloce in quel numero di elementi (ma parliamo comunque di 100 secondi di secondo, quindi è lo in realtà?). Riguarda la versione x64 per 100000 elementi. Considerando che c'è un ulteriore sovraccarico nell'aggiunta di elementi al dizionario, probabilmente non ne vale la pena. Inoltre, ho "imbrogliato" un po 'ignorando il comparatore in modo da ordinare in ordine inverso, quindi in realtà sto facendo dict.Keys.First() invece di ultimo per ottenere l'elemento più grande.

Un SortedDictionary è davvero pensato per se è necessario iterare su tutte le coppie di valori chiave in ordine. Penso che la risposta di @ SimonMourier sia probabilmente la migliore. Ti garantisco che è il più veloce, con un sovraccarico minimo.

Answer 3

Se le prestazioni sono davvero un problema, vorrei creare una nuova classe in cima ad uno esistente, attuare le interfacce standard, in questo modo:

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