Performances LINQ en mémoire

Question

Plus qu’à propos de LINQ à [insérez votre fournisseur préféré ici], cette question concerne la recherche ou le filtrage des collections en mémoire.

Je sais que LINQ (ou les méthodes d'extension de recherche / filtrage) fonctionne dans les objets implémentant IEnumerable ou IEnumerable<T>. La question est la suivante: en raison de la nature de l'énumération, chaque complexité de la requête est-elle au moins O (n) ?

Par exemple:

var result = list.FirstOrDefault(o => o.something > n);

Dans ce cas, chaque algorithme prendra au moins O (n) à moins que list ne soit commandé par rapport à 'something'. Dans ce cas, la recherche doit prendre O (log (n)) : il devrait s'agir d'une recherche binaire. Toutefois, si je comprends bien, cette requête sera résolue par énumération. Par conséquent, le traitement doit prendre O (n) , même si <=> a déjà été commandé.

• Que puis-je faire pour résoudre une requête dans O (log (n)) ?
• Si je veux des performances, dois-je utiliser Array.Sort et Array.BinarySearch?

Answer 1

Même avec la parallélisation, c'est toujours O (n). Le facteur constant serait différent (en fonction de votre nombre de cœurs), mais comme n variait, le temps total varierait toujours de manière linéaire.

Bien sûr, vous pouvez écrire vos propres implémentations des différents opérateurs LINQ sur vos propres types de données, mais elles ne conviendraient que dans des situations très spécifiques. aspects optimisés des données. Par exemple, si vous avez une liste de personnes classée par âge, cela ne vous aidera pas avec une requête qui essaie de trouver une personne portant un nom particulier:)

Pour examiner le prédicat, vous devrez utiliser des arbres d'expression au lieu de délégués, et la vie deviendra beaucoup plus difficile.

J'imagine que j'ajouterais normalement de nouvelles méthodes indiquant clairement que vous utilisez le type de données indexé / ordonné / quelle que soit la nature du type de données, et qui fonctionneront toujours de manière appropriée. Vous ne pouvez évidemment pas invoquer ces méthodes supplémentaires à partir d'expressions de requête, mais vous pouvez toujours utiliser LINQ avec la notation par points.

Answer 2

Oui, le cas générique est toujours O (n), comme dit Sklivvz.

Cependant, de nombreuses méthodes LINQ sont un cas spécial lorsque l'objet implémentant IEnumerable implémente réellement, par exemple. ICollection. (J'ai vu cela pour IEnumerable.Contains au moins.)

En pratique, cela signifie que LINQ IEnumerable.Contains appelle par exemple le fast HashSet.Contains si IEnumerable est en réalité un HashSet.

IEnumerable<int> mySet = new HashSet<int>();

// calls the fast HashSet.Contains because HashSet implements ICollection.
if (mySet.Contains(10)) { /* code */ }

Vous pouvez utiliser réflecteur pour vérifier exactement la manière dont les méthodes LINQ sont définies, c’est ainsi que j’ai compris cela.

Oh, et aussi LINQ contient les méthodes IEnumerable.ToDictionary (associe une clé à une valeur unique) et IEnumerable.ToLookup (associe une clé à plusieurs valeurs). Ce dictionnaire / table de consultation peut être créé une seule fois et utilisé plusieurs fois, ce qui peut accélérer de plusieurs ordres de code le code qui sollicite fortement LINQ.

Answer 3

Oui, cela doit être le cas, car le seul moyen d'accéder à un membre d'un IEnumerable consiste à utiliser ses méthodes, ce qui signifie O (n).

Cela semble être un cas classique dans lequel les concepteurs de langage ont décidé d'échanger la performance contre la généralité.