Dictionary Lookup (O (1)) vs Linq wo

Question

Was ist schneller und sollte ich den Linq-Standard opfern, um Geschwindigkeit zu erreichen (vorausgesetzt, Dictionary-Lookup ist wirklich schneller)? Also lassen Sie mich erarbeiten:

Ich habe folgendes:

List<Product> products = GetProductList(); 

ich eine Notwendigkeit für ein Produkt suchen auf einige Attribut basiert, beispielsweise die Seriennummer. Ich konnte zuerst ein Wörterbuch erstellen und dann es wie folgt füllen:

Dictionary<string, Product> dict = new Dictionary<string, Product>(); 
foreach(Product p in products) 
{ 
    dict.Add(p.serial, p); 
} 

Wenn es Zeit ist, ein Produkt, nutzen Sie O (1) durch das Wörterbuch Look-up angeboten zu finden:

string some_serial = ...; 
try { Product p = dict[some_serial]; } catch(KeyNotFoundException) { } 

Alternativ mit Linq:

Product p = products.Where(p => p.serial.Equals(some_serial)).FirstOrDefault(); 

der Nachteil bei dem Dict Ansatz natürlich erfordert dies mehr Platz im Speicher, mehr Code, weniger elegant zu schreiben, usw. (obwohl die meisten dies fraglich sind). Angenommen, das ist kein Faktor. Soll ich den ersten Ansatz nehmen?

Abschließend möchte ich bestätigen, ob die Komplexität des obigen Linq-Ansatzes tatsächlich O (n) ist und ich nicht sehe, wie es besser sein kann.

Answer 1

Sie beginnen mit einer Aufzählung von Objekten Unter der Annahme, und tun dies nur einmal ...

Es wird schneller sein, die Where Methode zu tun im Gegensatz zum Hinzufügen zu einem Dictionary<TKey,TValue> und dann suchen wieder nach oben. Der Grund dafür ist, dass die Wörterbuchmethode nicht O (1) ist. In diesem Szenario fügen Sie Elemente zum Wörterbuch hinzu und suchen dann nach. Der Additionsteil ist O (N), der genauso teuer ist wie die Where Methode mit zusätzlichem Speicheraufwand. Ein weiterer kleiner Punkt zu beachten ist, dass Dictionary<TKey,TValue> nicht wirklich O (1) ist. Es nähert sich stattdessen O (1), kann aber unter bestimmten Umständen zu einer geringeren Leistung führen (z. B. viele zusammenstoßende Schlüssel).