c# - 在 C# 中将 IEnumerable<T> 转换为 List<T> 的最快方法

Question

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

我的第一个想法是:

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

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

有没有更快的方法？

Answer 1

说到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，如果向 List<T> 添加超过 4 个元素将分配当前大小两倍的新基础数组并复制元素...当我们达到 List<T> 的容量时，此过程将再次重复。您可以想象您可能有多少不必要的复制。为了防止这种情况，最好的选择是初始化 List<T>提前具备容量或使用List<T>(ICollection<T>) Actor 。

// 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);