Obtener la clave más grande en un diccionario

Question

Tengo un diccionario con claves que son enteros. Me gustaría obtener la clave más grande. No realizo un seguimiento de las claves para que puedan ser consecutivas (por ejemplo, 1, 2, 3, 4, 5, 6), pero pueden omitir (1, 3, 4, 5) aunque dudo que haya alguna diferencia.

No sólo tiene que utilizar una búsqueda binaria o hay un método? Por lo que veo, difícilmente puedes vencer a la búsqueda binaria por una tarea tan simple, quizás puedas reducirla a la mitad.

Answer 1

Si tiene LINQ disponibles, usted debe ser capaz de hacer:

Answer 2

Una búsqueda binaria sería el más rápido pero no funcionaría en un diccionario normal, ya que las claves no se almacenan en cualquier orden particular. La respuesta de @ Minitech, usando Linq Max(), es la más fácil si está usando un diccionario normal.

Si esta es una operación que tendrá que hacer muchas veces, puede considerar pasar a un SortedDictionary<TKey, TValue> que clasifica las entradas según la clave.

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: Este puede ser más lenta que un diccionario normal. Supongo que habría sido bueno mencionar eso. Esto se debe a las entradas en el diccionario se almacenan de una manera diferente (a/árbol Negro Rojo contra recipientes de hash/tabla hash)

Hay es un punto que el SortedDictionary se convierte en más rápido que una normal de Dictionary. Sin embargo, esto probablemente resultaría en alrededor de 1 millón de artículos, sin embargo, eso es solo una suposición. Resulta que es unas 10 veces más rápido que en muchos artículos (pero estamos hablando de 100ths de un segundo de todos modos, por lo que lo hace realmente importa?). Es casi igual en la versión x64 para 100000 elementos. Teniendo en cuenta que hay gastos adicionales de agregar elementos al diccionario, probablemente no valga la pena. Además, me "engañé" un poco anulando el comparer para que ordene en orden inverso, así que en realidad estoy haciendo dict.Keys.First() en lugar del último para obtener el ítem más grande.

Un SortedDictionary sirve realmente para si necesita iterar sobre todos los pares de valores clave en orden. Creo que la respuesta de @ SimonMourier es probablemente la mejor. Te garantizo que es el más rápido, con una sobrecarga mínima.

Answer 3

Si el rendimiento es realmente un problema, me gustaría crear una nueva clase en la parte superior de uno ya existente, la aplicación de las interfaces estándar, así:

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