Wydajność pomijania (i podobnych funkcji, takich jak Take)

Question

Właśnie obejrzałem kod źródłowy metod rozszerzeń Skip/Take systemu .NET Framework (w typie IEnumerable<T>) i okazało się, że wewnętrzna implementacja działa z Sposób GetEnumerator:

// .NET framework 
    public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count) 
    { 
     if (source == null) throw Error.ArgumentNull("source"); 
     return SkipIterator<TSource>(source, count); 
    } 

    static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source, int count) 
    { 
     using (IEnumerator<TSource> e = source.GetEnumerator()) 
     { 
      while (count > 0 && e.MoveNext()) count--; 
      if (count <= 0) 
      { 
       while (e.MoveNext()) yield return e.Current; 
      } 
     } 
    } 

Załóżmy, że mieć IEnumerable<T> z 1000 elementów (typ bazową jest List<T>). Co się stanie, jeśli robię list.Skip (990) .Take (10)? Czy będzie to powtórzyć po 990 pierwszych elementach przed wzięciem ostatniej dziesiątki? (tak to rozumiem). Jeśli tak, to nie rozumiem, dlaczego Microsoft nie dostosował metodę Skip takiego:

// Not tested... just to show the idea 
    public static IEnumerable<T> Skip<T>(this IEnumerable<T> source, int count) 
    { 
     if (source is IList<T>) 
     { 
      IList<T> list = (IList<T>)source; 
      for (int i = count; i < list.Count; i++) 
      { 
       yield return list[i]; 
      } 
     } 
     else if (source is IList) 
     { 
      IList list = (IList)source; 
      for (int i = count; i < list.Count; i++) 
      { 
       yield return (T)list[i]; 
      } 
     } 
     else 
     { 
      // .NET framework 
      using (IEnumerator<T> e = source.GetEnumerator()) 
      { 
       while (count > 0 && e.MoveNext()) count--; 
       if (count <= 0) 
       { 
        while (e.MoveNext()) yield return e.Current; 
       } 
      } 
     } 
    } 

W rzeczywistości, zrobili to dla metody Count na przykład ...

// .NET Framework... 
    public static int Count<TSource>(this IEnumerable<TSource> source) 
    { 
     if (source == null) throw Error.ArgumentNull("source"); 

     ICollection<TSource> collectionoft = source as ICollection<TSource>; 
     if (collectionoft != null) return collectionoft.Count; 

     ICollection collection = source as ICollection; 
     if (collection != null) return collection.Count; 

     int count = 0; 
     using (IEnumerator<TSource> e = source.GetEnumerator()) 
     { 
      checked 
      { 
       while (e.MoveNext()) count++; 
      } 
     } 
     return count; 
    } 

Jaki jest tego powód?

Answer 1

W Jon Skeet za doskonały poradnik re-wykonawczego Linq, Omówił (krótko), że bardzo pytanie:

Chociaż większość z tych operacji nie może być rozsądnie zoptymalizowane, to sensu optymalizacji przeskakiwany podczas źródło implementuje IList. Możemy pominąć pomijanie, by tak rzec, i przejść bezpośrednio do odpowiedniego indeksu . Nie wykryłoby to przypadku, w którym źródło zostało zmienione między kolejnymi iteracjami, co może być jednym z powodów, dla których nie jest ono zaimplementowane w ramach, o ile mi wiadomo.

To wydaje się być rozsądnym powodem, aby wstrzymać się z tą optymalizacją, ale zgadzam się, że w konkretnych przypadkach warto dokonać tej optymalizacji, jeśli możesz zagwarantować, że twoje źródło nie może/nie będzie modyfikowane .

Answer 2

Zakładam, że chcieli rzucić InvalidOperationException "Kolekcja została zmodyfikowana ...", gdy kolekcja bazowa została zmodyfikowana w międzyczasie w innym wątku. Twoja wersja tego nie robi. Przyniesie straszliwe rezultaty.

Jest to standardowa praktyka, którą MSFT stosuje w całej strukturze .Net we wszystkich kolekcjach, która nie jest bezpieczna dla wątków (niektóre są jednak wyjątkowe).

Answer 3

Jak wspomniał ledbutter, kiedy Jon Skeet reimplemented LINQ, wspomniał, że optymalizacja taka jak twoja Skip "nie wykryłaby przypadku, w którym źródło zostało zmodyfikowane pomiędzy iteracjami". Możesz zmienić swój kod na poniższe, aby sprawdziła, czy w tym przypadku. Czyni to, wywołując MoveNext() na moduł wyliczający kolekcji, nawet jeśli nie używa ona e.Current, tak aby metoda wyrzuciła, jeśli kolekcja ulegnie zmianie.

To eliminuje znaczącą część optymalizacji: moduł wyliczający musi zostać utworzony, częściowo przekroczony i unieszkodliwiony, ale nadal ma tę zaletę, że nie ma potrzeby bezsensownego przechodzenia przez pierwsze obiekty count . I może być mylące, że masz e.Current, który nie jest przydatny, ponieważ wskazuje na list[i - count] zamiast list[i].

public static IEnumerable<T> Skip<T>(this IEnumerable<T> source, int count) 
{ 
    using (IEnumerator<T> e = source.GetEnumerator()) 
    { 
     if (source is IList<T>) 
     { 
      IList<T> list = (IList<T>)source; 
      for (int i = count; i < list.Count; i++) 
      { 
       e.MoveNext(); 
       yield return list[i]; 
      } 
     } 
     else if (source is IList) 
     { 
      IList list = (IList)source; 
      for (int i = count; i < list.Count; i++) 
      { 
       e.MoveNext(); 
       yield return (T)list[i]; 
      } 
     } 
     else 
     { 
      // .NET framework 
      while (count > 0 && e.MoveNext()) count--; 
      if (count <= 0) 
      { 
       while (e.MoveNext()) yield return e.Current; 
      } 
     } 
    } 
}