.NET 列表上的随机访问很慢，但如果我总是引用第一个元素怎么办？

Question

我知道一般来说，.NET 列表不适合随机访问。我一直被告知数组最适合。我有一个程序需要连续（超过十亿次）访问 .NET 列表的第一个元素，我想知道这是否会减慢速度，或者这无关紧要，因为它是列表中的第一个元素列表。我还做了很多其他事情，比如在我进行的过程中从列表中添加和删除项目，但列表永远不会为空。

我使用的是 F#，但我认为这适用于任何 .NET 语言（我使用的是 .NET 列表，而不是 F# 列表）。我的列表大约有 100 个元素。

Answer 1

随机访问数组和列表的性能差别不大。这是我机器上的测试。

var list = Enumerable.Range(1, 100).ToList();
var array = Enumerable.Range(1, 100).ToArray();

int total = 0;

var sw = Stopwatch.StartNew();
for (int i = 0; i < 1000000000; i++) {
    total ^= list[0];
}
Console.WriteLine("Time for list: {0}", sw.Elapsed);

sw.Restart();
for (int i = 0; i < 1000000000; i++) {
    total ^= array[0];
}
Console.WriteLine("Time for list: {0}", sw.Elapsed);

这会产生以下输出：

 Time for list: 00:00:05.2002620 
 Time for array: 00:00:03.0159816

如果你知道你有一个固定大小的列表，那么使用数组是有意义的，否则，~~列表的成本并不高。~~（查看更新）

更新！

我发现了一些非常重要的新信息。在发布模式下执行脚本后，故事发生了很大变化。

Time for list: 00:00:02.3048339
Time for array: 00:00:00.0805705

在这种情况下，数组的性能完全支配了列表。我很惊讶，但数字不会说谎。

使用数组。

Answer 2

在 F# 中，.NET 列表 (System.Collections.Generic.List) 恰如其分地别名为 ResizeArray，这毫无疑问会发生什么。它是一个可以调整自身大小的数组，而不是 CS 课堂对该术语的理解中的真正列表。它与简单数组之间的任何性能差异很可能是因为编译器可以更积极地优化数组使用。

回到你的问题。如果您只访问列表的第一个元素，那么您选择什么都没有关系。 ResizeArray 和 list（使用 F# 术语）对第一个元素（head）的访问权限为 O(1)。

如果您的其他操作也适用于头部元素，则

A list 将是更好的选择，即您仅从头部添加元素。如果你想将元素附加到列表的末尾，或者改变一些已经存在的元素，你会从 ResizeArray.

中获得更好的里程数

也就是说，ResizeArray 的 F# 代码非常罕见。通常的方法有利于（并且不受使用）不可变数据结构的影响，所以看到一个通常对我来说是一个小危险信号。

.NET 列表上的随机访问很慢，但如果我总是引用第一个元素怎么办？

Random access on .NET lists is slow, but what if I always reference the first element?

.net

c#

f#

list

random-access

更新！