为什么 LinkedList 通常比 List 慢? [英] Why is a LinkedList Generally Slower than a List?

问题描述

我开始在我的一些 C# 算法中使用一些 LinkedList 而不是 List，希望能加快它们的速度.但是，我注意到他们只是感觉变慢了.像任何优秀的开发人员一样，我认为我应该尽职调查并验证我的感受.所以我决定对一些简单的循环进行基准测试.

I started using some LinkedList’s instead of Lists in some of my C# algorithms hoping to speed them up. However, I noticed that they just felt slower. Like any good developer, I figured that I should do due diligence and verify my feelings. So I decided to benchmark some simple loops.

我认为用一些随机整数填充集合就足够了.我在调试模式下运行此代码以避免任何编译器优化.这是我使用的代码:

I thought that populating the collections with some random integers should be sufficient. I ran this code in Debug mode to avoid any compiler optimizations. Here is the code that I used:

var rand = new Random(Environment.TickCount);
var ll = new LinkedList<int>();
var list = new List<int>();
int count = 20000000;

BenchmarkTimer.Start("Linked List Insert");
for (int x = 0; x < count; ++x)
  ll.AddFirst(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();

BenchmarkTimer.Start("List Insert");
for (int x = 0; x < count; ++x)
  list.Add(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();

int y = 0;
BenchmarkTimer.Start("Linked List Iterate");
foreach (var i in ll)
  ++y; //some atomic operation;
BenchmarkTimer.StopAndOutput();

int z = 0;
BenchmarkTimer.Start("List Iterate");
foreach (var i in list)
  ++z; //some atomic operation;
BenchmarkTimer.StopAndOutput();

这里是输出:

Linked List Insert: 8959.808 ms
List Insert: 845.856 ms
Linked List Iterate: 203.632 ms
List Iterate: 125.312 ms

这个结果让我很困惑.链接列表插入应该是 O(1) 而列表插入是 Θ(1)，如果需要调整大小，则 O(n)(因为复制).由于枚举器，两个列表迭代都应该是 O(1).我查看了反汇编的输出，它并没有说明情况.

This result baffled me. A Linked List insert should be O(1) whereas as List Insert is Θ(1), O(n) (because of copy) if it needs to be resized. Both list iterations should be O(1) because of the enumerator. I looked at the disassembled output and it doesn’t shed much light on the situation.

还有其他人对为什么会这样有任何想法吗?我是否遗漏了一些非常明显的东西?

Anyone else have any thoughts on why this is? Did I miss something glaringly obvious?

注意:这里是简单的 BenchmarkTimer 类的来源:http://procbits.com/2010/08/25/benchmarking-c-apps-algorithms/

Note: here is the source for the simple BenchmarkTimer class: http://procbits.com/2010/08/25/benchmarking-c-apps-algorithms/

推荐答案

更新(回应您的评论):您说得对，单独讨论 big-O 表示法并不是很有用.我在最初的回复中包含了 James 回答的链接，因为他已经很好地解释了 List 总体上优于 LinkedList 的技术原因.

Update (in response to your comment): you're right, discussing big-O notation by itself is not exactly useful. I included a link to James's answer in my original response because he already offered a good explanation of the technical reasons why List<T> outperforms LinkedList<T> in general.

基本上，这是内存分配和局部性的问题.当您的所有集合元素都在内部存储在一个数组中时(如 List 的情况)，它们都在一个连续的内存块中，可以非常快速地访问em>.这适用于添加(因为这只是写入已分配数组中的一个位置)以及迭代(因为这会访问许多非常靠近的内存位置而不必遵循指向完全断开连接的内存位置的指针).

Basically, it's a matter of memory allocation and locality. When all of your collection's elements are stored in an array internally (as is the case with List<T>), it's all in one contiguous block of memory which can be accessed very quickly. This applies both to adding (as this simply writes to a location within the already-allocated array) as well as iterating (as this accesses many memory locations that are very close together rather than having to follow pointers to completely disconnected memory locations).

A LinkedList 是一个 专门的 集合，它仅在您执行随机插入的情况下优于 List或从列表的中间删除——即使那样，也只有可能.

A LinkedList<T> is a specialized collection, which only outshines List<T> in the case where you are performing random insertions or removals from the middle of the list—and even then, only maybe.

至于缩放的问题:你是对的，如果大 O 符号是关于操作缩放的程度，那么 O(1) 操作最终应该击败 O(>1) 给定足够大的输入的操作——这显然是你在 2000 万次迭代中想要的.

As for the question of scaling: you're right, if big-O notation is all about how well an operation scales, then an O(1) operation should eventually beat out an O(>1) operation given a large enough input—which is obviously what you were going for with 20 million iterations.

这就是为什么我提到 List.Add 有一个 摊销复杂度.这意味着向列表添加也是一种与输入大小线性缩放的操作，与链表相同(有效).忘记有时列表必须调整自身大小的事实(这就是摊销"的用武之地；如果您还没有，我鼓励您访问维基百科的那篇文章).他们缩放相同.

This is why I mentioned that List<T>.Add has an amortized complexity of O(1). That means adding to a list is also an operation that scales linearly with the size of the input, the same (effectively) as with a linked list. Forget about the fact that occasionally the list has to resize itself (this is where the "amortized" comes in; I encourage you to visit that Wikipedia article if you haven't already). They scale the same.

现在，有趣的是，也许与直觉相反，这意味着 List 和 LinkedList 之间的性能差异(同样，当随着元素数量的增加，添加)实际上变得更加明显.原因是当列表的内部数组空间不足时，它会将数组的大小加倍；因此，随着元素越来越多，调整大小操作的频率降低——以至于数组基本上从不调整大小.

Now, interestingly, and perhaps counter-intuitively, this means that if anything, the performance difference between List<T> and LinkedList<T> (again, when it comes to adding) actually becomes more obvious as the number of elements increases. The reason is that when the list runs out of space in its internal array, it doubles the size of the array; and thus with more and more elements, the frequency of resizing operations decreases—to the point where the array is basically never resizing.

所以假设 List 以一个足够大的内部数组开始，可以容纳 4 个元素(我相信这是准确的，虽然我不太记得了).然后当您添加多达 2000 万个元素时，它总共调整自身大小 ~(log₂(20000000) - 1) 或 23 次.将此与 2000 万次相比，您在 LinkedList 上执行相当效率较低的 AddLast，它会在每次调用时分配一个新的 LinkedListNode，而这 23 次调整大小突然显得微不足道.

So let's say a List<T> starts with an internal array large enough to hold 4 elements (I believe that's accurate, though I don't remember for sure). Then as you add up to 20 million elements, it resizes itself a total of ~(log₂(20000000) - 1) or 23 times. Compare this to the 20 million times you're performing the considerably less efficient AddLast on a LinkedList<T>, which allocates a new LinkedListNode<T> with every call, and those 23 resizes suddenly seem pretty insignificant.

我希望这会有所帮助！如果我有任何不清楚的地方，请告诉我，我会尽力澄清和/或更正自己.

I hope this helps! If I haven't been clear on any points, let me know and I will do my best to clarify and/or correct myself.

詹姆斯是对的

请记住，大 O 表示法旨在让您了解算法的性能如何扩展.这并不意味着在保证 O(1) 时间内执行的某些内容会胜过在摊销 O(1) 时间内执行的其他内容(如 List 的情况).

Remember that big-O notation is meant to give you an idea of how the performance of an algorithm scales. It does not mean that something that performs in guaranteed O(1) time will outperform something else that performs in amortized O(1) time (as is the case with List<T>).

假设您有两项工作可供选择，其中一项需要在偶尔会遇到交通拥堵的道路上通勤 5 英里.通常，此驱动器大约需要 10 分钟，但在糟糕的一天可能更像是 30 分钟.另一份工作在 60 英里外，但高速公路始终畅通无阻，从不堵车.这个车程总是需要你一个小时.

Suppose you have a choice of two jobs, one of which requires a commute 5 miles down a road that occasionally suffers from traffic jams. Ordinarily this drive should take you about 10 minutes, but on a bad day it could be more like 30 minutes. The other job is 60 miles away but the highway is always clear and never has any traffic jams. This drive always takes you an hour.

这基本上就是 List 和 LinkedList 用于添加到列表末尾的情况.

That's basically the situation with List<T> and LinkedList<T> for purposes of adding to the end of the list.

这篇关于为什么 LinkedList 通常比 List 慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！