.NET列表的随机访问速度较慢，但如果我总是引用第一个元素呢？

Question

我知道一般来说，.NET列表不适用于随机访问。我一直听说最好使用数组。我有一个程序需要连续(超过十亿次)访问.NET列表的第一个元素，我想知道这是否会减缓任何东西，或者它不重要，因为它是列表中的第一个元素。我还做了很多其他事情，比如在进行操作时添加和删除列表项，但是列表从未为空。

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

- user3685285

---

List<T>是由一个数组支持的，它能够提供常数级别的随机访问。 - jdphenix

List<T> 内部使用数组：source 在 reference source.microsoft.com 上显示了 private T[] _items; 字段。 - Wai Ha Lee

@jdphenix：我最初认为列表中的数组大致相同，但我的实验证明了相反的情况。数组和列表的访问都是O(1)，但这并不保证类似的性能。我的测试显示速度差异超过50倍。 - recursive

数组和List<T>具有快速的随机访问能力。LinkedList<T>是一种双向链表，因此具有较慢的随机访问能力（且不提供索引器）。F#的列表是单向链表，因此具有较慢的随机访问能力。 - CodesInChaos

Answer 1

在F#中，.NET列表（System.Collections.Generic.List）被巧妙地别名为ResizeArray，这让人们对其期望有了很少的疑惑。它是一个可以自动调整大小的数组，而不是CS课堂上理解的列表。它与简单数组之间的任何性能差异可能来自于编译器在优化数组使用方面更加积极的事实。

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

如果你的其他操作也是在头部元素上进行的，比如只从头部添加元素，那么list将是更好的选择。如果你想要将元素附加到列表的末尾，或者改变一些已经存在的元素，那么ResizeArray会更加有效。

话虽如此，在符合F#习惯用法的代码中，很少看到ResizeArray。通常的做法是使用不可变数据结构，因此看到ResizeArray通常会引起我的轻微警觉。

- scrwtp

Answer 2

对于数组和列表的随机访问性能，差别不是很大。以下是在我的计算机上进行的测试。

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

在这种情况下，数组的性能完全超过列表。我很惊讶，但数字不会撒谎。

选择数组。

- recursive

---

肯定会有人问（在这种情况下，那个人就是我）- 这是在“DEBUG”模式下吗？ - Wai Ha Lee

你的基准测试有些可疑。总是读取相同的元素。数组比List<T>更快，但在有意义的测试中，差异会小得多。 - CodesInChaos

@CodesInChaos：问题指定了始终访问第一个元素，因此基准测试测量了这一点。我不明白这是如何使其成为可疑的。如果有优化，那么它也适用于OP的用例。 - recursive

它所展示的只是使用List每十亿次读取将会产生2秒的开销。对我来说这毫无意义。 - scrwtp

@scrwtp：这很合理。我同意，但根据您的用例不同，持不同意见也不是不合理的。我提供了足够的信息来重现测试。人们应该根据自己的用例得出自己的结论。 - recursive