Estoy tratando de entender qué estructuras de datos son las más eficientes y cuándo / dónde usar cuáles.

Ahora, podría ser que simplemente no entiendo las estructuras lo suficientemente bien, pero ¿cómo es ILookup(of key, ...)diferente de a Dictionary(of key, list(of ...))?

Además, ¿dónde me gustaría usar un ILookupy dónde sería más eficiente en términos de velocidad del programa / memoria / acceso a datos, etc.?

Dos diferencias significativas:

• LookupEs inmutable. Yay :) (Al menos, creo que la Lookupclase concreta es inmutable, y la ILookupinterfaz no proporciona ningún miembro mutante. Por supuesto, podría haber otras implementaciones mutables).
• Cuando busca una clave que no está presente en una búsqueda, obtiene una secuencia vacía en lugar de a KeyNotFoundException. (Por lo tanto, no hay TryGetValue, AFAICR).

Es probable que sean equivalentes en eficiencia: la búsqueda bien puede usar un Dictionary<TKey, GroupingImplementation<TValue>>detrás de escena, por ejemplo. Elija entre ellos según sus requisitos. Personalmente, encuentro que la búsqueda suele ser más adecuada que a Dictionary<TKey, List<TValue>>, principalmente debido a los dos primeros puntos anteriores.

Tenga en cuenta que, como detalle de implementación, IGrouping<,>cuya implementación concreta se utiliza para los implementos de valores IList<TValue>, lo que significa que es eficiente de usar Count(), ElementAt()etc.

Es interesante que nadie haya declarado la mayor diferencia real (tomada directamente de MSDN ):

Una búsqueda se asemeja a un diccionario. La diferencia es que un Diccionario asigna claves a valores individuales, mientras que una Búsqueda asigna claves a colecciones de valores.

Tanto a Dictionary<Key, List<Value>>como a Lookup<Key, Value>lógicamente pueden contener datos organizados de manera similar y ambos son del mismo orden de eficiencia. La principal diferencia es que Lookupes inmutable: no tiene Add()métodos ni constructor público (y, como Jon mencionó, puede consultar una clave inexistente sin excepción y tener la clave como parte de la agrupación).

En cuanto a cuál usa, realmente depende de cómo quiera usarlos. Si mantiene un mapa de clave a múltiples valores que se modifica constantemente, entonces Dictionary<Key, List<Value>>probablemente sea mejor ya que es mutable.

Sin embargo, si tiene una secuencia de datos y solo desea una vista de solo lectura de los datos organizados por clave, entonces una búsqueda es muy fácil de construir y le dará una instantánea de solo lectura.

La principal diferencia entre an ILookup<K,V>y a Dictionary<K, List<V>>es que un diccionario es mutable; puede agregar o eliminar claves, y también agregar o eliminar elementos de la lista que se busca. Un ILookupes inmutable y no se puede modificar una vez creado.

La implementación subyacente de ambos mecanismos será la misma o similar, por lo que su velocidad de búsqueda y huella de memoria será aproximadamente la misma.

Otra diferencia que aún no se menciona es que Lookup () admite claves nulas :

La clase de búsqueda implementa la interfaz ILookup. La búsqueda es muy similar a un diccionario, excepto que se permite asignar múltiples valores a la misma clave y se admiten claves nulas.

Cuando la excepción no es una opción, vaya a Buscar

Si está tratando de obtener una estructura tan eficiente como una Dictionarypero no sabe con certeza que no hay una clave duplicada en la entrada, Lookupes más seguro.

Como se menciona en otra respuesta, también admite claves nulas, y siempre devuelve un resultado válido cuando se consulta con datos arbitrarios, por lo que parece más resistente a la entrada desconocida (menos propenso que el Diccionario para generar excepciones).

Y es especialmente cierto si lo compara con la System.Linq.Enumerable.ToDictionaryfunción:

// won't throw
new[] { 1, 1 }.ToLookup(x => x); 

// System.ArgumentException: An item with the same key has already been added.
new[] { 1, 1 }.ToDictionary(x => x);

La alternativa sería escribir su propio código duplicado de administración de claves dentro de un foreachbucle.

Consideraciones de rendimiento, Diccionario: un claro ganador

Si no necesita una lista y va a administrar una gran cantidad de elementos, Dictionary(o incluso su propia estructura personalizada) sería más eficiente:

        Stopwatch stopwatch = new Stopwatch();
        var list = new List<string>();
        for (int i = 0; i < 5000000; ++i)
        {
            list.Add(i.ToString());
        }
        stopwatch.Start();
        var lookup = list.ToLookup(x => x);
        stopwatch.Stop();
        Console.WriteLine("Creation: " + stopwatch.Elapsed);

        // ... Same but for ToDictionary
        var lookup = list.ToDictionary(x => x);
        // ...

Como Lookupdebe mantener una lista de elementos para cada tecla, es más lenta que Dictionary (alrededor de 3 veces más lenta para una gran cantidad de elementos)

Velocidad de búsqueda: Creación: 00: 00: 01.5760444

Velocidad del diccionario: Creación: 00: 00: 00.4418833