Quelles garanties y a-t-il sur la complexité à court terme (Big-O) des méthodes LINQ?

Tout ce que vous pouvez vraiment compter sur est que les méthodes énumérables sont bien écrits pour le cas général et n'utiliseront pas des algorithmes naïfs. Il y a probablement des trucs de tiers (blogs, etc.) qui décrivent les algorithmes réellement utilisés, mais ils ne sont pas officiels ou garantis au sens où les algorithmes STL le sont.

pour illustrer, voici le code source reflété (avec la permission de ILSpy) pour Enumerable.Count du système.Central:

// 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 on peut voir, il va à un certain effort pour éviter la solution naïve de simplement énumérer chaque élément.

je sais depuis longtemps que .Count() retourne .Count si le dénombrement est un IList .

mais j'ai toujours été un peu las de la complexité des opérations de tournage: .Intersect() , .Except() , .Union() .

Voici L'implémentation de la BCL décompilée (.net 4.0/4.5) pour .Intersect() (commentaires mine):

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:

• le performance is O (M + N)
• la mise en œuvre n'est pas profiter quand les collections sont déjà . (Ce n'est pas nécessairement simple, car le IEqualityComparer<T> utilisé doit aussi correspondre.)

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

Spoiler alert: eux aussi ont O (N+M) 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;
  }
}

je viens de casser le réflecteur et ils vérifient le type sous-jacent quand Contains est 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 de quel type est le IEnumerable sous-jacent. je sais que pour certaines collections (comme les collections qui mettent en œuvre ICollection ou IList) il y a des chemins de codes spéciaux qui sont utilisés, mais la mise en œuvre réelle n'est pas garantie de faire quoi que ce soit de spécial. par exemple, je sais que ElementAt() a un cas spécial pour les collections indexables, de la même façon que Count(). Mais en général, vous devriez probablement supposer le pire cas O(n) performance.

en général, je ne pense pas que vous allez trouver le genre de garanties de performance que vous voulez, bien que si vous rencontrez un problème de performance particulier avec un opérateur linq, vous pouvez toujours simplement le réimposer 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 performance. vérifier LINQ indexé qui s'étend et ajoute à l'opérateur ensemble pour plus avantages de performance.