Pourquoi Enumerable<T>.ToArray() utilise-t-il un tampon intermédiaire alors qu'il peut simplement appeler Count() en premier ?

Question

Je lisais une question demandant Est-il préférable d'appeler ToList() ou ToArray() dans les requêtes LINQ ? et je me suis retrouvé à me demander pourquoi Enumerable.ToArray() ne devrait pas d'abord appeler le Count() pour trouver la taille de la collection au lieu d'utiliser la méthode interne Buffer{T} qui se redimensionne dynamiquement. Quelque chose comme ce qui suit :

T[] ToArray<T>(IEnumerable<T> source)
{
    var count = source.Count();
    var array = new T[count];

    int index = 0;
    foreach (var item in source) array[index++] = item;
    return array;
}

Je sais que nous ne pouvons pas comprendre ce qui se passe dans l'esprit des concepteurs et des responsables de la mise en œuvre et je suis sûr qu'ils sont beaucoup plus intelligents que moi. La meilleure façon de poser cette question est donc de se demander ce qui ne va pas avec l'approche présentée ci-dessus. Il semble qu'il y ait moins d'allocation de mémoire et qu'elle fonctionne toujours en temps O(n).

Answer 1

El Buffer<T> a une optimisation pour le cas où la séquence source implémente ICollection<T> :

internal Buffer(IEnumerable<TElement> source)
{
   int length = 0;
   TElement[] array = null;
   ICollection<TElement> collection = source as ICollection<TElement>;
   if (collection != null)
   {
      length = collection.Count;
      if (length > 0)
      {
         array = new TElement[length];
         collection.CopyTo(array, 0);
      }
   }
   else
   {
      ...

Si la séquence ne met pas en œuvre ICollection<T> le code ne peut pas supposer qu'il est sûr d'énumérer la séquence deux fois, il se rabat donc sur le redimensionnement du tableau comme requis.

Answer 2

Tout d'abord, le Buffer<T> Le constructeur de la classe optimise également si la séquence spécifiée peut être casted en ICollection (comme un tableau ou une liste) qui possède un Count propriété :

TElement[] array = null;
int num = 0;
ICollection<TElement> collection = source as ICollection<TElement>;
if (collection != null)
{
    num = collection.Count;
    if (num > 0)
    {
        array = new TElement[num];
        collection.CopyTo(array, 0);
    }
}
else
    // now we are going the long way ...

Donc, s'il ne s'agit pas d'une collection, la requête doit être exécutée pour obtenir le nombre total. Mais en utilisant Enumerable.Count juste pour initialiser le tableau correctement dimensionné peut s'avérer très coûteux et - plus important encore - pourrait avoir des effets secondaires dangereux. C'est pourquoi cette méthode n'est pas sûre.

Considérez cette simple File.ReadLines exemple :

var lines = File.ReadLines(path);
int count = lines.Count(); // executes the query which also disposes the underlying IO.TextReader 
var array = new string[count];
int index = 0;
foreach (string line in lines) array[index++] = line;

Ceci lancera un ObjectDisposedException "Impossible de lire depuis un TextReader fermé" depuis lines.Count() a déjà exécuté la requête et pendant ce temps le lecteur est disposé à foreach .

Answer 3

Parce que Count() énumère la source jusqu'à la fin. Donc il fera au moins 2 itérations, une juste pour le compte et l'autre pour copier les éléments.

Considérons maintenant que l'énumérable en question est un curseur de base de données ou quelque chose de similaire qui implique des opérations non triviales lors de l'itération. Ce serait une perte de performance.

C'est une bien meilleure idée de simplement copier et étendre le tampon. Cela peut avoir un léger impact sur les performances, mais il est très faible et, plus important encore, c'est un moyen de réduire les coûts. quantité connue .

Answer 4

Si IEnumerable<T> et/ou IEnumerator<T> avait inclus une propriété pour demander si elle "connaissait" son compte, ainsi qu'une Count propriété, il aurait pu être intéressant pour ToArray() de faire usage d'une telle chose [avoir le Count faire partie de IEnumerator<T> serait utile dans les cas où, par exemple, le fait d'appeler GetEnumerator sur un type mutable thread-safe énumérera un instantané]. En l'absence d'une telle capacité, même si le code possède un ICollection o ICollection<T> il n'y a aucun moyen pour lui de savoir si appeler Count prendra plus ou moins de temps que la création de tableaux temporaires supplémentaires.

Ceci étant dit, je m'attends à ce que l'implémentation optimale pour quelque chose comme ToArray serait probablement d'utiliser une liste chaînée de choses, dont chacune contient un certain nombre d'éléments, de sorte que chaque élément soit lu dans l'espace qu'il occupe jusqu'à ce qu'il puisse être copié dans le tableau final. La stratégie de doublement de List<T> ne semble pas particulièrement approprié ici, puisqu'il serait préférable de répartir les informations dans plusieurs petits tableaux plutôt que de créer un tableau de plus de 85 000 octets (étant donné que les tableaux temporaires seront inutiles après la sortie de l'application, il serait particulièrement mauvais qu'ils finissent sur le tas de gros objets).