Recherche de dictionnaire (O (1)) vs Linq où

Question

Qu'est-ce qui est plus rapide et devrais-je sacrifier la norme Linq pour atteindre la vitesse (en supposant que la recherche de dictionnaire est vraiment plus rapide)? Alors laissez-moi élaborer:

Je donne les résultats suivants:

List<Product> products = GetProductList(); 

J'ai besoin de chercher un produit basé sur un attribut, par exemple, le numéro de série. Je pourrais d'abord créer un dictionnaire, puis le remplir comme suit:

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

Quand il est temps de trouver un produit, profiter de O (1) offert par le look-up Dictionnaire:

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

Sinon, LINQ:

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

l'inconvénient de l'approche Dict est bien sûr, cela nécessite plus d'espace dans la mémoire, plus de code à écrire, moins élégante, etc (même si la plupart de cela est discutable). Supposons que ce soit non-facteur. Devrais-je prendre la première approche? Pour conclure, je voudrais confirmer si la complexité de l'approche de Linq ci-dessus est bien O (n) et je ne vois pas comment cela pourrait être meilleur que cela.

Answer 1

En supposant que vous commencez avec une énumération des objets et ne faites que cette fois ...

Il sera plus rapide à faire la méthode Where au lieu d'ajouter à un Dictionary<TKey,TValue> puis regardant en arrière vers le haut. La raison en est que la méthode du dictionnaire est et non O (1). Dans ce scénario, vous ajoutez des éléments au dictionnaire, puis vous le recherchez. La partie additionnelle est O (N), ce qui est tout aussi cher que la méthode Where avec surcharge mémoire supplémentaire.

Un autre point mineur à prendre en compte est que Dictionary<TKey,TValue> n'est pas vraiment O (1). Il se rapproche plutôt de O (1) mais peut se dégrader à des performances moindres dans certaines circonstances (beaucoup de clés qui s'affrontent par exemple).