Quelles garanties sont a-t-il sur la complexité de l’exécution (Big-O) des méthodes LINQ ?

Question

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).

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.) travail à l'aide d' 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 auraient besoin d'une sorte, donc, très probablement, 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) en 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 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?

Answer 1

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 ou LastOrDefault, va vérifier pour voir si oui ou non le type sous-jacent implémente IList<T>, de sorte que vous obtenez O(1) l'accès au lieu de O(N).

• L' Count méthode vérifie pour un ICollection 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 et Except) utiliser le hachage, de sorte qu'ils devraient être à proximité de O(N) au lieu de O(N2).

• Contains recherche un ICollection mise en œuvre, de sorte qu'il peut être O(1) si la collection sous-jacente est également en O(1), tel qu'un HashSet<T>, mais c'est dépend de la structure de données et n'est pas garanti. Hash jeux de remplacer l' Contains méthode, c'est pourquoi ils sont en O(1).

• OrderBy méthodes utilisent une stable quicksort, ils sont donc O(N log N) cas moyen.

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.

Answer 2

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.

Pour illustrer, voici le traduit le code source (avec l'aimable autorisation de ILSpy) Enumerable.Count à partir du Système.Core:

// System.Linq.Enumerable
public static int Count<TSource>(this IEnumerable<TSource> source)
{
    checked
    {
        if (source == null)
        {
            throw Error.ArgumentNull("source");
        }
        ICollection<TSource> collection = source as ICollection<TSource>;
        if (collection != null)
        {
            return collection.Count;
        }
        ICollection collection2 = source as ICollection;
        if (collection2 != null)
        {
            return collection2.Count;
        }
        int num = 0;
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                num++;
            }
        }
        return num;
    }
}

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.

Answer 3

J'ai longtemps connu que .Count() retours .Count si l'énumération est une IList.

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) mise en œuvre pour l' .Intersect() (commentaires de la mienne):

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in second)                    // O(M)
    set.Add(source);                                    // O(1)

  foreach (TSource source in first)                     // O(N)
  {
    if (set.Remove(source))                             // O(1)
      yield return source;
  }
}

Conclusions:

• l'exécution est O(M + N)
• la mise en œuvre n'est pas à prendre l'avantage lors de la collections sont déjà définit. (Il peut ne pas être forcément facile, parce que l'employée 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) de la complexité.

private static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in first)
  {
    if (set.Add(source))
      yield return source;
  }
  foreach (TSource source in second)
  {
    if (set.Add(source))
      yield return source;
  }
}


private static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in second)
    set.Add(source);
  foreach (TSource source in first)
  {
    if (set.Add(source))
      yield return source;
  }
}

Answer 4

J’ai juste éclaté de réflecteur et ils ne vérifient pas le sous-jacent tapez lorsque `` est appelé.

Answer 5

La bonne réponse est "ça dépend". cela dépend de la nature du sous-jacent IEnumerable. 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.