在 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)。

根据另一个IEnumerable<T>

创建List<T>

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

然而，关于迭代器的类型有一点不同：

如果迭代器是ICollection<T>

var array = new T[ICollection.Count] // C ICollection.CopyTo(数组) // 来自 MSDN O(n)
如果迭代器是IEnumerable<T>，等同于创建空并逐项添加

因此，如果分析复杂度，则无法避免 O(n) 复杂度。

但是...

有一个注意事项是 List<T> 增长和容量可能会影响性能。默认 List<T> 容量为 4，如果您向 List<T> 添加超过 4 个元素，则将分配当前大小两倍的新底层数组并复制元素...此过程当我们达到 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);

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

Fastest way to convert IEnumerable<T> to List<T> in C#

c#

collections

ienumerable

iterator

list