¿El diccionario <TKey, TValue> es más rápido que LINQ en una lista <T>?

Question

Generalmente uso List<T> para colecciones. Pero si necesito una búsqueda rápida en una colección, entonces p. en el siguiente ejemplo me gustaría utilizar un diccionario para que pudiera mirar hacia arriba rápidamente por id:

Dictionary<int, Customer> 

Pero ya que puedo utilizar LINQ para consultar el List<T> todos modos, como es abajo, ¿hay alguna razón para ir a través de la ¿Problemas para usar un diccionario en lugar de una lista? ¿Es más rápido el diccionario o LINQ está haciendo algo detrás de escena que lo hace igual de rápido?

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      List<Customer> customers = new List<Customer>() 
      { 
      new Customer { Id = 234, FirstName = "Jim", LastName = "Smith" }, 
      new Customer { Id = 345, FirstName = "John", LastName = "Thomas" }, 
      new Customer { Id = 654, FirstName = "Rick", LastName = "Ashton" }, 
      new Customer { Id = 948, FirstName = "Rod", LastName = "Anders" } 
      }; 

      var customer = (from c in customers 
          where c.Id == 654 select c).SingleOrDefault(); 
      Console.WriteLine(customer.Display()); 

      Console.ReadLine(); 

     } 
    } 


    public class Customer 
    { 
     public int Id { get; set; } 
     public string FirstName { get; set; } 
     public string LastName { get; set; } 

     internal string Display() 
     { 
      return String.Format("{0}, {1} ({2})", LastName, FirstName, Id); 
     } 

    } 
} 

Answer 1

Si lógicamente desea crear una colección donde puede buscar fácilmente a un cliente por su ID, yo usaría alguna forma de IDictionary<int, Customer>. Eso expresa lo que estás tratando de lograr.

Ahora podría utilizar una lista para hacer lo mismo, y como dice leppie para pequeños conjuntos de datos que será casi tan rápido o incluso más rápido - pero para pequeños conjuntos de datos que va a ser muy rápido de todos modos, ¿por qué hacer ¿te importa? Creo que es más importante decirle al lector de tu código lo que intentas hacer con la colección, y un diccionario logra ese objetivo mucho más efectivamente que una lista, la OMI.

Answer 2

Para listas más pequeñas de 20 artículos, la sobrecarga de una voluntad Dictionary/Hashtable hace que sea más lento que una lista.

Answer 3

LINQ no es mágico. Todavía tendrá que recorrer una lista para encontrar el elemento que desee. El diccionario seguirá siendo más rápido (para colecciones de tamaño adecuado, como señala Leppie)

Answer 4

Según MSDN obtener un elemento de un diccionario basado en la clave "se acerca a una operación O (1)". Por otro lado, la ejecución de Where en una lista recorre los elementos para buscar coincidencias. Por lo general, el diccionario será definitivamente más rápido.

Si desea acelerar las operaciones de Linq puede usar Indexed LINQ que le permite poner índices en sus colecciones.

Answer 5

Quizás pueda utilizar una SortedList y realizar una búsqueda binaria (teniendo en cuenta que elimina la mitad de la colección después de la primera comparación) en esta colección.

Answer 6

LINQ generalmente será más lento en este tipo de operaciones. Sin embargo, en un conjunto lo suficientemente pequeño (como su ejemplo), es probable que sea más rápido, debido a las diferencias en los gastos generales. Sin embargo, una vez más, en un conjunto lo suficientemente pequeño (como su ejemplo), la diferencia entre ambas soluciones será tan pequeña que no importará tanto como la pregunta de si el diccionario busca o dónde() lee de forma más natural.