C#:ToArray表现

Question

背景:

我承认我并没有尝试对此进行基准测试,但我很好奇......

Enumerable.ToArray<T>(和它的堂兄Enumerable.ToList<T>)的CPU /内存特性是什么？

既然IEnumerable不预先通告它有多少元素,我(可能是天真地)假定ToArray必须"猜测"一个初始数组大小,然后如果第一个猜测看起来太小则重新调整/重新分配数组,然后调整大小如果第二次猜测看起来太小等等,它又会再次出现......这会产生比线性更差的性能.

我可以想象更好的方法涉及(混合)列表,但这仍然需要多个分配(虽然不是重新分配)和相当多的复制,尽管它可能是线性整体尽管开销.

题:

幕后是否有任何"神奇"发生,避免了重复调整大小的需要,并ToArray在空间和时间上呈线性？

更一般地说,是否有关于BCL性能特征的"官方"文档？

Answer 1

没有魔法.如果需要,可以调整大小.

请注意,并不总是需要它.如果IEnumerable<T>被.ToArray编还实现ICollection<T>,则该.Count属性被用于预分配的阵列(使得在空间和时间的算法是线性的.)如果没有,但是,执行以下的(粗糙)代码:

    foreach (TElement current in source)
    {
        if (array == null)
        {
            array = new TElement[4];
        }
        else
        {
            if (array.Length == num)
            {
                // Doubling happens *here*
                TElement[] array2 = new TElement[checked(num * 2)];
                Array.Copy(array, 0, array2, 0, num);
                array = array2;
            }
        }
        array[num] = current;
        num++;
    }

注意阵列填充时加倍.

无论如何,避免打电话通常是一种很好的做法.ToArray(),.ToList()除非你绝对要求它.在需要时直接询问查询通常是更好的选择.

Answer 2

我使用.NET Reflector提取了.ToArray()方法后面的代码:

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

和Buffer.ToArray:

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

在Buffer构造函数中,它遍历所有元素以计算真实的Count和Elements数组.