为什么LinkedList通常比列表慢？

Question

我开始在我的一些C#算法中使用一些LinkedList而不是Lists来希望加速它们.但是,我注意到他们感觉速度慢了.像任何优秀的开发者一样,我认为我应该尽职尽责并验证我的感受.所以我决定测试一些简单的循环.

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

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).我查看了拆卸后的输出,并没有对这种情况有所了解.

其他人对这是为什么有任何想法？我错过了一些明显的东西吗？

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

Answer 1

更新(回应你的评论):你是对的,讨论big-O符号本身并不完全有用.我在最初的回复中包含了詹姆斯答案的链接,因为他已经提供了一个很好的解释,为什么一般List<T>表现优异的技术原因LinkedList<T>.

基本上,这是内存分配和位置的问题.当你的所有集合元素都在内部存储在一个数组中时(就像这样List<T>),它就在一个连续的内存块中,可以非常快速地访问它.这既适用于添加(因为它只是写入已经分配的数组中的位置)以及迭代(因为它访问非常靠近的许多内存位置,而不必遵循指向完全断开的内存位置的指针).

A LinkedList<T>是一个专门的集合,只有List<T>在你从列表中间执行随机插入或删除的情况下才会出类拔萃- 即便如此,也许只有.

关于缩放的问题:你是对的,如果大O符号完全取决于操作的扩展程度,那么在给定足够大的输入的情况下,O(1)操作最终应该击败O(> 1)操作 -这显然是你想要的2000万次迭代.

这就是为什么我提到它List<T>.Add具有O(1)的摊销复杂性.这意味着添加到列表中的操作也是与输入大小成线性比例的操作,与链接列表相同(有效).忘记这个事实,偶尔列表必须自己调整大小(这是"摊销"的地方;我鼓励你访问维基百科的文章,如果你还没有).它们规模的相同.

现在,有趣的是,也许是反直觉的,这意味着如果有的话,随着元素数量的增加,List<T>和之间的性能差异LinkedList<T>(再次,当涉及到添加时)实际上变得更加明显.原因是当列表在其内部数组中耗尽空间时,它会使数组的大小加倍 ; 因此,随着越来越多的元素,调整大小操作的频率降低到数组基本上从不调整大小的程度.

所以,让我们说一个List<T>内部数组开始,足以容纳4个元素(我相信这是准确的,虽然我不记得确定).然后,当您添加多达2000万个元素时,它会自行调整大约〜(log ₂(20000000) - 1)或23次.相比之下,你执行的2000万次 a的效率要低得多,每次调用都会分配一个新的,而这23个调整大小突然显得非常微不足道.AddLastLinkedList<T>LinkedListNode<T>

我希望这有帮助!如果我对任何要点都不清楚,请告诉我,我会尽力澄清和/或纠正自己.

詹姆斯是对的.

请记住,big-O表示法旨在让您了解算法的性能如何扩展.这并不意味着在保证的O(1)时间内执行的某些事情将胜过在摊销的O(1)时间内执行的其他事情(如果是这样List<T>).

假设您可以选择两个工作,其中一个工作需要在一条路上行驶5英里,偶尔会遇到交通拥堵.通常这个驱动器应该花费大约10分钟,但在糟糕的一天它可能更像是30分钟.另一项工作是60英里远,但高速公路总是很清晰,从来没有任何交通拥堵.这个驱动器总是需要一个小时.

这基本上与状况List<T>,并LinkedList<T>添加到列表的末尾的目的.

Answer 2

请记住,你已经有了基元列表.对于List,这非常简单,因为它创建了一个完整的int数组,当它不需要分配更多内存时,它很容易将它们向下移动.

将此与一个始终必须分配内存以包装整数的LinkedList进行对比.因此,我认为内存分配可能对您的时间贡献最大.如果您已经分配了节点,那么整体应该更快.我尝试使用AddFirst的重载进行实验,该实验使得LinkedListNode进行验证(即,创建在定时器范围之外的LinkedListNode,只需添加它的时间).

迭代是类似的,转到内部数组中的下一个索引比跟踪链接要高效得多.

Answer 3

我强烈推荐文章《数字运算：为什么你不应该再使用链表》。那里没有太多其他地方没有的东西，但我花了相当多的时间试图弄清楚为什么LinkedList<T>在我认为明显有利于链接的情况下比List<T>慢得多在我找到它之前列出它，在查看之后，事情变得更有意义了：

\n

\n

链表的项位于不相交的内存区域，因此，我们可以说它是缓存行敌对的，因为它使缓存未命中最大化。不相交的内存使得遍历列表会导致频繁且昂贵的意外 RAM 查找。

\n

另一方面，向量[相当于ArrayList或List<T> ] 将其项目存储在相邻内存中，这样做可以最大限度地提高缓存利用率并避免缓存未命中。通常，在实践中，这足以抵消整理数据时产生的成本。

\n

\n

如果您想从更权威的来源听到这一点，请参阅MSDN 上的“改进时间关键代码的提示”：

\n

\n

有时，由于引用位置不佳，看起来很棒的数据结构实际上很糟糕。下面是两个例子：

\n

\n

• 动态分配的链表（LinkedListNode<T>是引用类型，因此是动态分配的）会降低程序性能，因为当您搜索某个项目或遍历列表到末尾时，每个跳过的链接都可能会错过缓存或导致页面错误。基于简单数组的列表实现实际上可能会更快，因为更好的缓存和更少的页面错误\xe2\x80\x94 即使考虑到数组更难增长的事实，它仍然可能更快。

  \n
\n

• 使用动态分配的链表的哈希表会降低性能。通过扩展，使用动态分配的链接列表来存储其内容的哈希表的性能可能会差很多。事实上，归根结底，通过数组进行简单的线性搜索实际上可能会更快（取决于具体情况）。基于数组的哈希表（IIRC，Dictionary<TKey,TValue>是基于数组的）是一种经常被忽视的实现，但通常具有卓越的性能。

  \n
\n

\n

\n\n

这是我最初的（不太有用）答案，我做了一些性能测试。

\n

普遍的共识似乎是链表在每次添加时分配内存（因为节点是一个类），情况似乎确实如此。我尝试将分配代码与将项目添加到列表的定时代码隔离开来，并从结果中得出要点： https://gist.github.com/zeldafreak/d11ae7781f5d43206f65

\n

我运行测试代码 5 次并调用GC.Collect()在它们之间进行调用。将 2000 万个节点插入链表需要 193-211 毫秒 (198 毫秒)，而需要 77-89 毫秒 (81 毫秒)，因此即使没有分配，标准列表的速度也会快 2 倍多一点。迭代列表需要 54-59 毫秒，而链表则需要 76-101 毫秒，这比链表快了 50% 左右。

\n

Answer 4

正如詹姆斯在他的回答中所说,内存分配可能是导致LinkedList变慢的一个原因.

此外,我认为主要区别来自无效测试.您将项目添加到链接列表的开头,但是添加到普通列表的末尾.不会在普通列表的开头添加项目会使基准测试结果再次转向支持LinkedList吗？