¿Cómo funciona IEnumerable <T> .ToArray()?

Question

¿Es un algoritmo de dos pasos? es decir, itera el enumerable una vez para contar la cantidad de elementos para que pueda asignar la matriz, y luego volver a pasar para insertarlos.

¿Hace un bucle una vez y sigue cambiando el tamaño de la matriz?

¿O utiliza una estructura intermedia como una lista (que probablemente redimensiona internamente una matriz)?

Answer 1

Se utiliza una estructura intermedia. El tipo real involucrado es un Buffer, que es una estructura interna en el marco. En la práctica, este tipo tiene una matriz, que se copia cada vez que está llena para asignar más espacio. Esta matriz comienza con una longitud de 4 (en .NET 4, es un detalle de implementación que podría cambiar), por lo que podría terminar asignando y copiando mucho al hacer ToArray.

Sin embargo, existe una optimización en su lugar. Si la fuente implementa ICollection<T>, usa Count para asignar el tamaño correcto de la matriz desde el inicio.

Answer 2

Primero comprueba si la fuente es ICollection<T>, en cuyo caso puede llamar al método ToArray() de la fuente.

De lo contrario, enumera la fuente exactamente una vez. Como lo enumera, almacena elementos en una matriz de almacenamiento intermedio. Cada vez que llega al final de la matriz de almacenamiento intermedio, crea un nuevo almacenamiento intermedio de dos veces el tamaño y copia en los elementos antiguos. Una vez que la enumeración finaliza, devuelve el búfer (si tiene el tamaño exacto) o copia los elementos del búfer en una matriz del tamaño correcto exacto.

Así es código de pseudo-fuente para la operación de:

public static T[] ToArray<T>(this IEnumerable<T> source) 
{ 
    T[] items = null; 
    int count = 0; 

    foreach (T item in source) 
    { 
     if (items == null) 
     { 
      items = new T[4]; 
     } 
     else if (items.Length == count) 
     { 
      T[] destinationArray = new T[count * 2]; 
      Array.Copy(items, 0, destinationArray, 0, count); 
      items = destinationArray; 
     } 
     items[count] = item; 
     count++; 
    } 

    if (items.Length == count) 
    { 
     return items; 
    } 
    T[] destinationArray = new TElement[count]; 
    Array.Copy(items, 0, destinationArray, 0, count); 
    return destinationArray; 
} 

Answer 3

gusta esta (a través de .NET Reflector):

public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source) 
{ 
    if (source == null) 
    { 
     throw Error.ArgumentNull("source"); 
    } 
    Buffer<TSource> buffer = new Buffer<TSource>(source); 
    return buffer.ToArray(); 
} 

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

    internal TElement[] ToArray() 
    { 
     if (this.count == 0) 
     { 
      return new TElement[0]; 
     } 
     if (this.items.Length == this.count) 
     { 
      return this.items; 
     } 
     TElement[] destinationArray = new TElement[this.count]; 
     Array.Copy(this.items, 0, destinationArray, 0, this.count); 
     return destinationArray; 
    } 
} 

Answer 4

En primer lugar, los artículos se cargan en una clase interna Buffer<T> que permite el conteo que se genere

A continuación, Buffer<T>.ToArray se llama, que hace y Array.Copy de la matriz Buffer<T> en una matriz devuelta.

.NET Reflector muestra este código si quiere verlo usted mismo.

http://www.red-gate.com/products/reflector/

Answer 5

En general, el intento de repetir dos veces una numerable puede conducir a un desastre ya que no hay garantía de que el enumerables se pueden repetir una segunda vez. Por lo tanto, realizar un Count y luego asignar y luego copiar está fuera.

En Reflector, muestra que utiliza un tipo llamado Buffer que transmite eficazmente la secuencia en una matriz de cambio de tamaño (duplicación en cada reasignación de modo que el número de reasignaciones es O(log n)) según sea necesario y luego devuelve una matriz de tamaño apropiado cuando llega al final