Quelles garanties sont là, sur le moment de l'exécution de la complexité (Big-O) de méthodes LINQ?

J'ai récemment commencé à l'aide de LINQ un peu, et je n'ai pas vraiment vu aucune mention de la durée d'exécution de la complexité pour l'une des méthodes LINQ. Évidemment, il y a beaucoup de facteurs en jeu, ici, nous allons donc restreindre la discussion à la plaine IEnumerable LINQ-to-Objets fournisseur. En outre, supposons que tout Func transmis sous la forme d'un sélecteur /mutateur /etc. est un bon O(1) de l'opération.

Il semble évident que tout le seul passe-opérations (Select, Where, Count, Take/Skip, Any/All, etc.) O(n), puisqu'ils ont seulement besoin de marcher sur la séquence une fois; bien que même cela est soumis à la paresse.

Les choses sont claires pour les opérations plus complexes; l'ensemble-comme les opérateurs (Union, Distinct, Except, etc.) travailler à l'aide de GetHashCode par défaut (autant que je sache), il semble donc raisonnable de supposer qu'ils sont à l'aide d'une table de hachage en interne, ce qui rend ces opérations en O(n) ainsi, en général. Que sur les versions qui utilisent un IEqualityComparer?

OrderBy aurait besoin d'un autre, le plus probable, nous sommes à la recherche en O(n log n). Que faire si il est déjà trié? Que diriez-vous si je dis OrderBy().ThenBy() et de fournir la même clé pour tous les deux?

J'ai pu voir GroupBy (et Join) à l'aide de tri, ou le hachage. Qui est-il?

Contains serait O(n) sur un List, mais O(1) sur un HashSet - ne LINQ vérifier le conteneur sous-jacent à voir si ça peut accélérer les choses?

Et la vraie question - jusqu'à présent, j'ai été prise sur la foi que les opérations sont performants. Cependant, puis-je banque sur qui? Des conteneurs STL, par exemple, d'indiquer clairement la complexité de chaque opération. Existe-il des garanties semblables sur LINQ performance dans le .NET-library cahier des charges?

Plus de question (en réponse aux commentaires):

N'avais pas vraiment réfléchi dessus, mais je ne m'attendais pas là pour être très simple Linq-to-Objets. Le CodingHorror post parle de Linq-to-SQL, où je peux comprendre l'analyse de la requête et de prise de SQL s'ajouter le coût est - il un coût similaire pour les Objets fournisseur de trop? Si oui, est-elle différente si vous utilisez le déclaratif ou de syntaxe fonctionnelle?

  • Bien que je ne peux pas vraiment répondre à votre question, je tiens à faire remarquer que, en général, le jacuzzi, la partie de la performance sera "frais généraux" par rapport à la fonctionnalité de base. Ce n'est évidemment pas le cas lorsque vous avez de très grands ensembles de données (> 10k articles), donc im curieux de savoir dans le cas où vous voulez savoir.
  • Re: "est-il différent si vous utilisez le déclaratif ou de syntaxe fonctionnelle?" - le compilateur traduit la syntaxe déclarative dans la syntaxe fonctionnelle, de sorte qu'ils devraient être les mêmes.
  • "Conteneurs STL préciser clairement la complexité de chaque opération" .NET conteneurs a également spécifier clairement la complexité de chaque opération. Extensions Linq, sont comparables à des algorithmes de la STL, pas de conteneurs STL. Tout comme lorsque vous appliquez un STL algorithme pour un conteneur STL, vous avez besoin de combiner la complexité de l'extension Linq avec la complexité de la .NET conteneur(s) pour l'analyser correctement la résultante de la complexité. Ceci inclut la comptabilité pour les spécialisations de modèle, comme Aaronaught la réponse de mentions.
  • Une question sous-jacente est pourquoi Microsoft n'était pas plus concerné que IList<T> optimisation serait de peu d'utilité, étant donné qu'un développeur ne devrait compter que sans-papiers comportement si son code en dépendait pour être performant.
InformationsquelleAutor tzaman | 2010-05-09