Ist Dictionary <TKey, TValue> schneller als LINQ auf einer Liste <T>?

Question

Ich verwende generell List<T> für Sammlungen. Aber wenn ich eine schnelle Suche auf einer Sammlung benötigen, dann z.

Dictionary<int, Customer> 

Aber da ich LINQ verwenden können, um abzufragen, um die List<T> sowieso, wie unten, gibt es keinen Grund, durch die gehen: im folgenden Beispiel würde ich ein Wörterbuch verwenden, so könnte ich es schnell durch id nachschlagen Probleme mit einem Wörterbuch anstelle einer Liste? Ist das Wörterbuch schneller oder macht LINQ etwas hinter den Kulissen, das macht es genauso schnell?

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

Wenn Sie logisch eine Sammlung erstellen möchten, in der Sie einen Kunden leicht nach seiner ID suchen können, würde ich eine Form von IDictionary<int, Customer> verwenden. Das drückt aus, was Sie erreichen wollen.

Sie jetzt konnten eine Liste verwenden, um die gleiche Sache zu tun, und wie leppie für kleine Datensätze sagt es etwa so schnell oder sogar schneller sein - aber für kleine Datensätze wird es sehr schnell sowieso, also warum tun du kümmerst dich? Ich denke, es ist wichtiger, dem Leser Ihres Codes mitzuteilen, was Sie mit der Sammlung zu tun haben - und ein Wörterbuch erreicht dieses Ziel weit effektiver als eine Liste, IMO.

Answer 2

Für Listen kleiner als 20 Einzelteile, die Overhead eines Dictionary/Hashtable Willen bewirkt, dass es als eine Liste langsamer.

Answer 3

LINQ ist keine Magie. Es muss immer noch durch eine Liste iterieren, um das gewünschte Element zu finden. Das Wörterbuch wird immer noch schneller (für Sammlungen geeigneter Größe, wie leppie zeigt)

Answer 4

Nach MSDN ein Element aus einem Wörterbuch basierend auf Schlüssel "nähert sich einem O (1) -Operation." Auf der anderen Seite führt die Ausführung von Where in einer Liste eine Schleife durch die Elemente, um Übereinstimmungen zu finden. Im Allgemeinen wird das Wörterbuch definitiv schneller sein.

Wenn Sie die Operationen von Linq beschleunigen möchten, können Sie Indexed LINQ verwenden, mit dem Sie Indizes zu Ihren Sammlungen hinzufügen können.

Answer 5

Sie könnten vielleicht eine SortedList verwenden und binäre Suche durchführen (wenn man bedenkt, dass sie die Hälfte der Sammlung nach dem ersten Vergleich eliminiert) für diese Sammlung.

Answer 6

LINQ wird bei dieser Art von Operation im Allgemeinen langsamer sein. Bei einem kleinen Format (wie in Ihrem Beispiel) wird es jedoch aufgrund der Unterschiede beim Overhead wahrscheinlich schneller sein. Bei einer kleinen Menge (wie in Ihrem Beispiel) wird der Unterschied zwischen beiden Lösungen jedoch so klein sein, dass es nicht so wichtig ist wie die Frage, ob das Wörterbuch nachschaut oder wo() sich natürlicher liest.