时间戳

首页 > 解决方案 > 转换 IEnumerable 的最快方法列出在 C# 中

c# - 转换 IEnumerable 的最快方法列出在 C# 中

问题描述

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

我的第一个想法是这样的：

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

foreach(int number in iterator)
    list.Add(number);

有更快的方法吗？

标签： c#listcollectionsiteratorienumerable

解决方案

当谈到List<T>本质上你有两种方法，我试图在下面讨论。为了清楚起见，我们假设分配List<T>元素需要恒定时间（C），向其中添加元素List<T>也需要恒定时间。

创建空List<T>并填充它

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

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

List<T>在其他基础上创建IEnumerable<T>

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

但是，迭代器的类型有一点不同：

  1. 如果迭代器是ICollection<T>

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

  2. 如果迭代器是IEnumerable<T>，则与创建空并逐项添加相同

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

但...

增长和容量有一个警告List<T>可能会影响性能。默认List<T>容量为 4，如果您向新的底层数组添加超过 4 个元素List<T>，则将分配两倍于当前大小的元素并复制元素......当我们达到容量时，此过程将再次重复List<T>. 你可以想象你可能有多少不必要的复制。为了防止这种情况，最好的选择是List<T>提前用容量初始化或使用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);

推荐阅读