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.
Vous devez vous connecter pour publier un commentaire.
Il y a très, très peu de garanties, mais il y a quelques optimisations:
Les méthodes d'Extension qui utilisent un accès indexé, comme
ElementAt
,Skip
,Last
ouLastOrDefault
, va vérifier pour voir si oui ou non le type sous-jacent implémenteIList<T>
, de sorte que vous obtenez O(1) l'accès au lieu de O(N).La
Count
méthode vérifie pour unICollection
mise en œuvre, de sorte que cette opération est O(1) au lieu de O(N).Distinct
,GroupBy
Join
, et je crois aussi l'ensemble-méthodes d'agrégation (Union
,Intersect
etExcept
) utiliser le hachage, de sorte qu'ils devraient être à proximité de O(N) au lieu de O(N2).Contains
vérifie pour unICollection
mise en œuvre, de sorte qu'il peut O(1) si la collection sous-jacente est également en O(1), comme unHashSet<T>
, mais c'est dépend de la structure de données et n'est pas garanti. Hash jeux de remplacer leContains
méthode, c'est pourquoi ils sont en O(1).OrderBy
méthodes utilisent une stable quicksort, ils sont donc O(N log N) en moyenne cas.Je pense que la plupart, si pas tous de la intégré dans les méthodes d'extension. Il y a vraiment très peu de garanties de performance; Linq lui-même va essayer de profiter de l'efficacité des structures de données, mais ce n'est pas un laissez-passer gratuit pour écrire potentiellement inefficace code.
IEqualityComparer
surcharges?IEqualityComparer
, je ne peux pas de raison pour qu'il affecte la complexité asymptotique.EqualityComparer
implémenteGetHashCode
ainsi queEquals
; mais bien sûr, cela prend tout son sens.Orderby().ThenBy()
encoreN logN
ou est-il(N logN) ^2
ou quelque chose comme ça?ThenBy()
?Skip
ne pas suivre ce que vous avez déclaré. il semble êtreO(n)
referencesource.microsoft.com/#System.Core/System/Linq/...Tout ce que vous pouvez vraiment de la banque, c'est que le Énumérable méthodes sont bien écrits pour le cas général, et de ne pas utiliser les algorithmes naïfs. Il y a probablement tiers des trucs (blogs, etc.) que de décrire les algorithmes utilisés, mais elles ne sont pas officielles ou de la garantie dans le sens que les algorithmes de la STL sont.
Pour illustrer, voici le traduit le code source (avec l'aimable autorisation de ILSpy) pour
Enumerable.Count
à partir du Système.Core:Comme vous pouvez le voir, il va à un certain effort pour éviter les naïfs solution de simplement l'énumération de tous les éléments.
Enumerable.Count
n'a pas d'itérer à moins qu'il n'existe pas de solution évidente. Comment auriez-vous fait moins naïve?IEnumerable<T>
et l'utilisation de Linq, tout comme d'autres collections.ICollection
et seront efficacement utilisé par de nombreuses méthodes Linq.J'ai longtemps connu que
.Count()
retourne.Count
si l'énumération est uneIList
.Mais j'ai toujours été un peu fatigué sur le moment de l'exécution de la complexité de l'Ensemble des opérations:
.Intersect()
,.Except()
,.Union()
.Voici la décompilé BCL (.NET 4.0/4.5) la mise en œuvre de
.Intersect()
(commentaires de la mine):Conclusions:
IEqualityComparer<T>
doit également correspondre.)Pour être complet, voici les implémentations pour
.Union()
et.Except()
.Spoiler alert: elles sont, elles aussi, ont O(N+M) complexité.
J'ai juste éclaté de réflecteur et ils ne cochez le type sous-jacent lorsque
Contains
est appelé.La bonne réponse est "ça dépend". cela dépend de la nature du sous-jacent IEnumerable est. je sais que pour certaines collections (comme les collections de mettre en œuvre ICollection ou IList) il y a des codepaths qui sont utilisés, mais la réelle mise en œuvre n'est pas garanti pour faire quelque chose de spécial. par exemple je sais que ElementAt() est un cas particulier pour indexables des collections, de la même façon avec Count(). Mais en général, vous devriez probablement envisager le pire des cas O(n) de la performance.
En général je ne pense pas que vous allez trouver le type de garanties de performance que vous voulez, mais si vous avez un problème de performance avec une linq l'opérateur, vous pouvez toujours réimplémenté pour votre collection en particulier. Il y a aussi beaucoup de blogs et de l'extensibilité des projets qui s'étendent de Linq to Objects pour ajouter ces types de garanties de performance. découvrez Indexé LINQ qui s'étend et s'ajoute à l'opérateur de définir pour plus d'avantages de performance.