Dictionnaire Lookup (O (1)) vs Linq où

Question

Qu'est-ce que est plus rapide et devrais-je sacrifier la norme Linq pour atteindre la vitesse (en supposant Dictionnaire recherche est vraiment plus rapide)? Permettez-moi de préciser:

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 Dictionnaire Recherch:

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

Vous pouvez également, en utilisant 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). On suppose que ce non-facteur. Dois-je prendre la première approche?

Pour conclure, je voudrais confirmer si la complexité de l'approche Linq est en effet O ci-dessus (n) et je ne vois pas comment il peut être mieux 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 pour laquelle est que la méthode de dictionnaire est pas O (1). Dans ce scénario, vous ajoutez des éléments au dictionnaire et regarder vers le haut. La partie d'addition est O (N) qui est aussi cher que le procédé d'Where avec une surcharge de la mémoire supplémentaire.

Un autre point mineur à prendre en compte est que Dictionary<TKey,TValue> est pas vraiment O (1). Il approche au lieu O (1), mais peut se dégrader en performance moindre dans certaines circonstances (beaucoup de se heurtant par exemple les clés).