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

问题描述

我开始使用一些链表的，而不是列出了一些我的C＃算法，希望能加速他们。不过，我注意到，他们只是觉得慢。像任何优秀的开发者，我想我应该做的尽职调查，并确认了我的感情。所以我决定基准一些简单的循环。

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.

我想填充一些随机整数集合应该足够了。我跑这code。在调试模式，以避免任何编译器优化。这里是code，我用：

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类：<一href="http://procbits.com/2010/08/25/benchmarking-c-apps-algorithms/">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/

推荐答案

更新（响应您的评论）：你说的没错，本身讨论大O记法是不完全有用。我包括一个链接到詹姆斯的回答在我原来的回应，因为他已经提供的技术原因，名单，其中一个很好的解释; T＆GT; 性能优于的LinkedList＆LT; T＆GT ; 一般

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.

基本上，它是内存分配和局部性的问题。当所有的集合的元素存储在内部数组（如与名单，其中的情况下，T＆GT; ），这一切都在一个内存连续块可接很快的。这适用于的添加的（因为这只是写入已分配的数组中的位置），以及迭代的（因为这样的访问非常接近了众多的内存位置而不必遵循指针完全断开的存储器位置）。

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＆LT; T＆GT; 是专业的集合，它只是一枝独秀名单，其中，T＆GT; 在您从中的的列表，即使在当时，只有的也许的。

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.

这就是为什么我提到名单，其中，T＆GT;。新增有一个的摊销复杂的O（1）。这意味着添加到列表是也的一个操作，即线性扩展与输入的大小，相同的（有效），为与一个链表。忘了，偶尔名单有调整自身的事实（这正是摊销进来，我建议您访问维基百科的文章，如果您还没有的话）。他们的比例的在同一个

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.

现在，有趣的是，或许与直觉相反，这意味着，如果有的话，列表℃之间的性能差异; T＆GT; 和的LinkedList＆LT; T＆GT ; （同​​样，当涉及到的添加的）居然成为作为元素的数量增加更为明显。其理由是，当该列表耗尽在其内部阵列空间，它的加倍的阵列的大小;从而与越来越多的元件，调整操作的频率的减少的-to的点阵列基本上都不调整大小

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.

所以我们可以说一个名单，其中，T＆GT; 开始的内部数组大到足以容纳4个元素（我相信这是准确的，但我不记得肯定） 。然后，当你把20万的元素，它会调整自己共〜（对数 ₂ （20000000） - 1）或 23倍。与此相比，在 2000万次您正在执行的相当的效率较低 AddLast 在 LinkedList的＆LT; T＆GT; ，它分配一个新的一个LinkedListNode＆LT; T＆GT; 与每一个电话，而那些23调整大小，顿时显得pretty的微不足道。

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.

<一个href="http://stackoverflow.com/questions/5983059/why-is-a-linkedlist-generally-slower-than-a-list/5983124#5983124">James是正确的。

请记住，大O记法是为了让您了解一个算法的性能的扩展的一个想法。这并不意味着一些执行中的保证O（1）时间的表现将优于执行的摊销O（1）时间其他的东西（如与名单，其中的情况下，T＆GT; ）

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.

这基本上与名单，其中的情况; T＆GT; 和的LinkedList＆LT; T＆GT; 为了增加年底的列表。

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

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