为什么 Enumerable<T>.ToArray() 在可以先调用 Count() 的情况下还要使用中间缓冲区？

Question

我正在阅读一个关于在LINQ查询中调用ToList()还是ToArray()更好的问题Is it better to call ToList() or ToArray() in LINQ queries?，并且想知道为什么Enumerable.ToArray()不首先调用Count()方法来查找集合的大小，而是使用内部的Buffer{T}类动态调整大小。类似以下代码：

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

我知道我们无法理解设计师和实现者的想法，而且我相信他们比我聪明得多。所以问这个问题的最佳方式是：上述方法有什么问题？它似乎分配的内存较少，但仍在O(n)时间内运行。

- Anthony

---

因为先调用 Count() 会导致需要两次枚举该序列。 - Richard Deeming

因为调用Count()，然后再次迭代序列以获取元素会执行潜在的副作用两次。 - Nikon the Third

@BrianRasmussen说了我想说的话。 - Anthony

如果是这样的话，那么Count()方法也不会进行同样的优化。 - Anthony

此外，如果输入序列确实实现了 ICollection<T> 接口，Buffer<T> 类将使用 Count 属性来分配一个正确大小的数组。 - Richard Deeming

Answer 1

< p > Buffer <T> 类在源序列实现 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
   {
      ...

如果序列没有实现ICollection<T>，代码就不能假定可以安全地两次枚举该序列，所以它会回退到根据需要调整数组大小的方式。

- Richard Deeming

Answer 2

首先，Buffer<T>类的构造函数还会优化，如果指定的序列可以转换为ICollection(如数组或列表)，该序列就具有一个Count属性:

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 ...

所以，如果它不是一个集合，则必须执行查询以获取总数。但是仅使用Enumerable.Count来正确初始化数组大小可能非常昂贵，并且 - 更重要的是 - 可能具有危险的副作用。因此，它是不安全的。

考虑这个简单的File.ReadLines示例：

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;

由于lines.Count()已经执行了查询，在此期间读取器被处置，因此会引发一个ObjectDisposedException“无法从已关闭的TextReader中读取”。

- Tim Schmelter

---

另一個例子是BlockingCollection.GetConsumingEnumerable()。呼叫Count()會消耗集合中的項目，迭代然後返回空白。 - svick

@TimSchmelter 我本来会投票支持你的答案这里，因为它更完整 - 下次不要删除！ - ErikE

Answer 3

因为Count()会枚举源到末尾。所以它至少要执行2次迭代，一次仅用于计数，另一次用于复制项目。

现在考虑一下问题中的可枚举对象是一个数据库光标或其他类似需要进行非平凡操作的对象。这将会导致性能问题。

更好的方法是只需memcopy并扩展缓冲区。这可能会略微影响性能，但非常小，并且更重要的是它是一个已知量。

- Adrian Zanescu

---

顺便提一句，你无法从IEnumerable<T>中进行“memcopy”，你必须逐个项目地进行。 - svick

我指的是在扩展缓冲区数组时进行内存复制。当然，您需要逐个从可枚举对象中获取每个项。 - Adrian Zanescu

Answer 4

如果 IEnumerable<T> 和/或 IEnumerator<T> 包含了一个属性来询问它是否“知道”它的计数，以及一个 Count 属性，那么对于 ToArray() 来说，利用这样的东西可能是值得的 [在 IEnumerator<T> 中包含 Count 对于调用线程安全可变类型上的 GetEnumerator 枚举快照的情况会很有帮助]。但是，如果没有这样的能力，即使代码具有 ICollection 或 ICollection<T>，也无法知道调用 Count 是否比创建额外的临时数组需要更多或更少的时间。

话虽如此，我认为像ToArray这样的最佳实现可能是使用一些东西的链接列表，每个东西都持有一些项目，以便每个项目都将被读入它所占用的空间，直到可以将其复制到最终数组。 List<T>的加倍策略在这里似乎不是特别合适，因为最好将信息分散在多个小数组中，而不是创建一个超过85,000字节的数组（由于临时数组在退出后将无用，使它们最终进入大对象堆将特别糟糕）。

- supercat

---

“将Count作为IEnumerator<T>的一部分会很有帮助”，这不正是IReadOnlyCollection<T>（以及不太通用的ICollection<T>）的作用吗？ - svick

@svick 这也将删除具有无限可枚举集合的能力，从而删除可枚举的流式处理能力。 - Anthony

@svick：调用接口成员通常比尝试转换为另一个接口类型更快，无论转换是否成功。此外，如果类型Bunch<T>恰好实现了IList<T>但不是非泛型的ICollection，那么期望IEnumerable<Animal>的代码没有很好的方法可以快速找出Bunch<Cat>中有多少个东西。此外，虽然线程安全集合可以提供快照枚举语义，但ICollection.Count返回的值可能与前面或后面的GetEnumerator返回的项数没有关系。 - supercat

@supercat 1. 如果一个类型没有实现 ICollection 或 IReadOnlyCollection<T>，那么它很可能也不会从 IEnumerator<T> 返回计数，即使它可以。2. 如果你想要一个具有计数一致快照的集合，不要实现 IEnumerable<T>，而是添加一个像 IReadOnlyList<T> Snaphost() 这样的方法。3. 我认为你过于复杂化了（我特别担心那个“等等”）。你正在创建一个不可靠的（它总是可以说“我不知道”）怪物，它只在极少数情况下有用。现在，IEnumerator<T> 简单易用，我喜欢这种方式。 - svick

@svick：对于建议集合实现一些“其他”方法来获取快照，通常情况下，想要一个IEnumerable<T>的快照的代码会使用ToArray()或者ToList()等方式。线程安全的集合可以通过实现IEnumerable<T>接口以这种方式工作来获取快照;为什么还需要使用其他方法呢? - supercat