System.Linq.Enumerable.Reverse copia tutti gli elementi internamente a un array?

Question

Alcuni anni fa, somebody complained about the implementation of Linq.Reverse() and Microsoft promised to fix that. Era nel 2008, quindi la domanda è: Framework 4 ha un'implementazione ottimizzata di Linq.Reverse() che non materializza la raccolta (ad esempio, copia tutti gli elementi in un array interno) quando il tipo di raccolta lo consente (ad esempio IList<T>)?

Answer 1

Ovviamente non è possibile ottimizzare tutti i casi. Se alcuni oggetti implementano solo IEnumerable<T> e non IList<T>, è necessario iterarlo fino alla fine per trovare l'ultimo elemento. Quindi l'ottimizzazione sarebbe solo per i tipi che implementano IList<T> (come T[] o List<T>).

Ora, è effettivamente ottimizzato in. NET 4.5 DP?Diamo accendiamo Riflettore ILSpy:

public static IEnumerable<TSource> Reverse<TSource>(
    this IEnumerable<TSource> source) 
{ 
    if (source == null) 
    { 
     throw Error.ArgumentNull("source"); 
    } 
    return ReverseIterator<TSource>(source); 
} 

Va bene, come fa ReverseIterator<TSource>() sguardo?

private static IEnumerable<TSource> ReverseIterator<TSource>(
    IEnumerable<TSource> source) 
{ 
    Buffer<TSource> buffer = new Buffer<TSource>(source); 
    for (int i = buffer.count - 1; i >= 0; i--) 
    { 
     yield return buffer.items[i]; 
    } 
    yield break; 
} 

Che quel blocco iteratore fa è creare un Buffer<T> per la raccolta e iterare a ritroso attraverso quella. Siamo quasi arrivati, che cos'è Buffer<T>?

[StructLayout(LayoutKind.Sequential)] 
internal struct Buffer<TElement> 
{ 
    internal TElement[] items; 
    internal int count; 
    internal Buffer(IEnumerable<TElement> source) 
    { 
     TElement[] array = null; 
     int length = 0; 
     ICollection<TElement> is2 = source as ICollection<TElement>; 
     if (is2 != null) 
     { 
      length = is2.Count; 
      if (length > 0) 
      { 
       array = new TElement[length]; 
       is2.CopyTo(array, 0); 
      } 
     } 
     else 
     { 
      foreach (TElement local in source) 
      { 
       if (array == null) 
       { 
        array = new TElement[4]; 
       } 
       else if (array.Length == length) 
       { 
        TElement[] destinationArray = new TElement[length * 2]; 
        Array.Copy(array, 0, destinationArray, 0, length); 
        array = destinationArray; 
       } 
       array[length] = local; 
       length++; 
      } 
     } 
     this.items = array; 
     this.count = length; 
    } 

    // one more member omitted 
} 

Cosa abbiamo qui? Copiamo il contenuto in un array. In ogni caso. L'unica ottimizzazione è che se conosciamo Count (ovvero, la collezione implementa ICollection<T>), non è necessario riallocare l'array.

Quindi, l'ottimizzazione per IList<T> è non in .Net 4.5 DP. Crea una copia dell'intera collezione in ogni caso.

Se dovessi indovinare perché non è ottimizzato, dopo aver letto Jon Skeet's article on this issue, penso che sia perché l'ottimizzazione è osservabile. Se si modifica la raccolta mentre si sta iterando, si vedranno i dati modificati con l'ottimizzazione, ma i vecchi dati senza di essa. E le ottimizzazioni che effettivamente cambiano il comportamento di qualcosa in modo sottile sono una brutta cosa, a causa della retrocompatibilità.

Answer 2

EDIT: Sì, sembra che questa modifica è stata effettuata

Il bug report si è collegato ai marchi il bug come fissa, ma ho voluto assicurarsi che per me stesso. Così, ho scritto questo piccolo programma:

static void Main(string[] args) 
{ 
    List<int> bigList = Enumerable.Range(0, 100000000).ToList(); 

    Console.WriteLine("List allocated"); 
    Console.ReadKey(); 

    foreach (int n in bigList.Reverse<int>()) 
    { 
     // This will never be true, but the loop ensures that we enumerate 
     // through the return value of Reverse() 
     if (n > 100000000) 
      Console.WriteLine("{0}", n); 
    } 
} 

L'idea è che il programma alloca 400 MB di spazio in bigList, quindi attende che l'utente prema un tasto, quindi chiama Enumerable.Reverse(bigList) tramite sintassi metodo di estensione.

Ho testato questo programma con una build di debug su un computer Windows 7 x64. L'utilizzo della memoria prima di avviare il programma è esattamente 2,00 GB, in base al Task Manager. Quindi, prima di premere un tasto, l'utilizzo della memoria raggiunge 2,63 GB. Dopo aver premuto il tasto, l'utilizzo della memoria raggiunge brevemente i 2.75 GB. È importante sottolineare, tuttavia, che non ha un picco di 400 MB o più, il che sarebbe il caso se Enumerable.Reverse() stessero facendo una copia.

ORIGINALE POST

È impossibile per una corretta Enumerable.Reverse() attuazione non copiare a una matrice o altra struttura dati in alcune situazioni.

La denuncia che si collega a offerte solo con IList<T>. Nel caso generale, tuttavia, sostengo che Enumerable.Reverse()deve copiare gli elementi in un buffer interno.

Si consideri il seguente metodo

private int x = 0; 

public IEnumerable<int> Foo() 
{ 
    for (int n = 0; n < 1000; n++) 
    { 
     yield return n; 
     x++; 
    } 
} 

Ora diciamo che Enumerable.Reverse() non ha copiato l'ingresso IEnumerable<T> ad un buffer in questo caso. Quindi, il ciclo

foreach (int n in Foo().Reverse()) 
    Console.WriteLine("{0}", n); 

sarebbe scorrere tutto il percorso attraverso il blocco iteratore per ottenere il primo n, tutto il percorso attraverso le prime 999 elementi per ottenere la seconda n, e così via. Ma questo non avrebbe lo stesso effetto su x come iterazione diretta, perché dovremmo effettuare la mutazione di x ogni volta che viene ripetuta quasi completamente il valore di ritorno di Foo(). Per evitare questa disconnessione tra iterazione diretta e inversa, il metodo Enumerable.Reverse()deve essere una copia dell'ingresso IEnumerable<T>.