Quelles garanties y a-t-il sur la complexité d'exécution (Big-O) des méthodes LINQ?

J'ai récemment commencé à utiliser un peu LINQ, et je n'ai vraiment vu aucune mention de la complexité d'exécution pour aucune des méthodes LINQ. De toute évidence, de nombreux facteurs sont en jeu ici, nous allons donc limiter la discussion au IEnumerablefournisseur LINQ-to-Objects. De plus, supposons que tout élément Funcpassé en tant que sélecteur / mutateur / etc. est une opération O (1) bon marché.

Il semble évident que toutes les opérations monopasse ( Select, Where, Count, Take/Skip, Any/All, etc.) seront O (n), car ils ne doivent marcher une fois la séquence; bien que même cela soit sujet à la paresse.

Les choses sont plus troubles pour les opérations plus complexes; l'ensemble comme les opérateurs ( Union, Distinct, Except, etc.) en utilisant le travail GetHashCodepar défaut (afaik), il semble donc raisonnable de supposer qu'ils utilisent une interne table de hachage, ce qui rend ces opérations O (n) et, en général. Qu'en est-il des versions qui utilisent un IEqualityComparer?

OrderByaurait besoin d'un tri, donc nous examinons très probablement O (n log n). Et si c'est déjà trié? Et si je dis OrderBy().ThenBy()et fournis la même clé aux deux?

Je pouvais voir GroupBy(et Join) utiliser soit le tri, soit le hachage. Lequel est-ce?

Containsserait O (n) sur a List, mais O (1) sur a HashSet- LINQ vérifie-t-il le conteneur sous-jacent pour voir s'il peut accélérer les choses?

Et la vraie question - jusqu'à présent, je suppose que les opérations sont performantes. Cependant, puis-je miser là-dessus? Les conteneurs STL, par exemple, spécifient clairement la complexité de chaque opération. Existe-t-il des garanties similaires sur les performances LINQ dans la spécification de la bibliothèque .NET?

Plus de question (en réponse aux commentaires):
Je n'avais pas vraiment pensé à la surcharge, mais je ne m'attendais pas à ce qu'il y en ait beaucoup pour de simples Linq-to-Objects. Le post CodingHorror parle de Linq-to-SQL, où je peux comprendre l'analyse de la requête et rendre SQL ajouterait des coûts - y a-t-il également un coût similaire pour le fournisseur Objects? Si oui, est-ce différent si vous utilisez la syntaxe déclarative ou fonctionnelle?

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, Lastou LastOrDefault, vérifiera si les instruments de type sous - jacent IList<T>, de sorte que vous obtenez O (1) l' accès au lieu de O (N).

• La Countméthode vérifie une ICollectionimplémentation, de sorte que cette opération est O (1) au lieu de O (N).

• Distinct, GroupBy Joinet je crois aussi que les méthodes d'agrégation d'ensembles ( Union, Intersectet Except) utilisent le hachage, elles devraient donc être proches de O (N) au lieu de O (N²).

• Containsvérifie une ICollectionimplémentation, il peut donc être O (1) si la collection sous-jacente est également O (1), comme a HashSet<T>, mais cela dépend de la structure de données réelle et n'est pas garanti. Les ensembles de hachage remplacent la Containsméthode, c'est pourquoi ils sont O (1).

• OrderBy Les méthodes utilisent un tri rapide stable, donc elles sont un cas moyen O (N log N).

Je pense que cela couvre la plupart sinon la totalité des méthodes d'extension intégrées. Il y a vraiment très peu de garanties de performance; Linq lui-même essaiera de tirer parti de structures de données efficaces, mais ce n'est pas une passe gratuite pour écrire du code potentiellement inefficace.

Je sais depuis longtemps que cela .Count()revient .Countsi l'énumération est un IList.

Mais je suis toujours un peu fatigué de la complexité d' exécution des opérations Set: .Intersect(), .Except(), .Union().

Voici l'implémentation décompilée BCL (.NET 4.0 / 4.5) pour .Intersect()(commentaires du mien):

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:

• la performance est O (M + N)
• l'implémentation ne profite pas lorsque les collections sont déjà des ensembles. (Ce n'est peut-être pas nécessairement simple, car IEqualityComparer<T>il faut également que le modèle utilisé corresponde.)

Par souci d'exhaustivité, voici les implémentations de .Union()et .Except().

Alerte spoiler: eux aussi ont une complexité O (N + M) .

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;
  }
}

Tout ce sur quoi vous pouvez vraiment compter, c'est que les méthodes Enumerable sont bien écrites pour le cas général et n'utiliseront pas d'algorithmes naïfs. Il y a probablement des éléments tiers (blogs, etc.) qui décrivent les algorithmes réellement utilisés, mais ceux-ci ne sont ni officiels ni garantis au sens où les algorithmes STL le sont.

Pour illustrer, voici le code source reflété (avec l'aimable autorisation de ILSpy) Enumerable.Countde System.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 faut faire des efforts pour éviter la solution naïve de simplement énumérer chaque élément.

Je viens de casser le réflecteur et ils vérifient le type sous-jacent quand il Containsest appelé.

public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value)
{
    ICollection<TSource> is2 = source as ICollection<TSource>;
    if (is2 != null)
    {
        return is2.Contains(value);
    }
    return source.Contains<TSource>(value, null);
}

La bonne réponse est "ça dépend". cela dépend du type de IEnumerable sous-jacent. Je sais que pour certaines collections (comme les collections qui implémentent ICollection ou IList), il existe des chemins de code spéciaux qui sont utilisés, mais la mise en œuvre réelle n'est pas garantie de faire quelque chose de spécial. par exemple, je sais que ElementAt () a un cas particulier pour les collections indexables, de même avec Count (). Mais en général, vous devriez probablement supposer les pires performances O (n).

En général, je ne pense pas que vous trouverez le type de garanties de performances que vous souhaitez, mais si vous rencontrez un problème de performances particulier avec un opérateur linq, vous pouvez toujours simplement le réimplémenter pour votre collection particulière. Il existe également de nombreux blogs et projets d'extensibilité qui étendent Linq aux objets pour ajouter ces types de garanties de performances. consultez Indexed LINQ qui étend et ajoute à l'ensemble d'opérateurs pour plus d'avantages en termes de performances.