转换IEnumerable< T>的最快方法列出< T>在C#中

问题描述：

在C#中，就编写代码所需的时间而言，使用IEnumberable创建和填充列表的最快方法是什么?关于执行所需的时间呢?

In C#, what is the fastest way to create and fill a List using an IEnumberable in terms of time required to write the code for? What about in terms of time required to execute?

我的第一个想法是:

List<int> list = new List<int>();
foreach(int number in iterator)
    list.Add(number);

有更快的方法吗?

答

当涉及到List<T>时，实际上您有2种方法，我将在下面讨论.为了清楚起见，假设List<T>的分配需要固定的时间(C)，向List<T>添加元素也需要固定的时间.

When it comes to List<T> essentially you have 2 approaches, which I am trying to discuss below. For the sake of clarity lets assume, allocation of the List<T> takes constant time (C), adding an element to the List<T> also takes constant time.

创建一个空的List<T>并填充

Create empty List<T> and populate it

List<int> list = new List<int>(); // C
foreach(int i in iterator)
{
    list.Add(i); //n*C
}

如您所见，这种方法需要n * C + C的时间，所以如果您忽略C，则复杂度为O(n).

as you can see this approach takes n*C + C time, so if you neglect the C the complexity is O(n).

根据其他IEnumerable<T>

Create List<T> based on the other IEnumerable<T>

List<int> list = new List<int>(iterator);

但是，关于迭代器的类型有一个小的区别:

however, there is a small difference regards the type of iterator:

如果迭代器为ICollection<T>

var array = new T [ICollection.Count]//C ICollection.CopyTo(array)//通过MSDN O(n)

var array = new T[ICollection.Count] // C ICollection.CopyTo(array) // by MSDN O(n)

如果迭代器为IEnumerable<T>，则与创建空白并逐项添加

if the iterator is IEnumerable<T>, the same as creating empty and add item by item

因此，如果您分析复杂度，就无法避免O(n)复杂度.

So, if you analyze the complexity you cannot avoid O(n) complexity.

但是...

List<T>的增长和容量有一个警告，可能会影响性能.默认的List<T>容量为4，如果您向List<T>添加4个以上的元素，则将分配新的基础数组，大小是当前大小的两倍，并且将复制这些元素.我们达到了List<T>的容量.您可以想象有多少不必要的复制.为了防止这种情况，最好的选择是预先使用容量初始化List<T>或使用List<T>(ICollection<T>) ctor.

There is one caveat with the List<T> growth and capacity which might impact performances. The default List<T> capacity is 4 and if you add more than 4 elements to the List<T> the new underlying array, twice of the current size, will be allocated and the elements will be copied...this process will repeat again when we reach the capacity of the List<T>. You can imagine how much unnecessary copying you might have. In order to prevent this, the best option is to initialize List<T> with capacity in advance or use the List<T>(ICollection<T>) ctor.

// benchmark example
var enumerable = Enumerable.Repeat(1, 1000000);
var collection = enumerable.ToList();

Stopwatch st = Stopwatch.StartNew();
List<int> copy1 = new List<int>(enumerable);
Console.WriteLine(st.ElapsedMilliseconds);

st = Stopwatch.StartNew();
List<int> copy2 = new List<int>(collection);
Console.WriteLine(st.ElapsedMilliseconds);

转换IEnumerable< T>的最快方法列出< T>在C#中

相关推荐