性能差异如此惊人？
性能差异如此惊人？
刚刚我阅读了有关List和LinkedList的一些帖子，所以我决定自己测试一下一些数据结构。 我通过添加数据和从前面/后面删除数据对Stack，Queue，List和LinkedList进行了基准测试。 下面是基准测试结果:
Pushing to Stack... Time used: 7067 ticks
Poping from Stack... Time used: 2508 ticks
Enqueue to Queue... Time used: 7509 ticks
Dequeue from Queue... Time used: 2973 ticks
Insert to List at the front... Time used: 5211897 ticks
RemoveAt from List at the front... Time used: 5198380 ticks
Add to List at the end... Time used: 5691 ticks
RemoveAt from List at the end... Time used: 3484 ticks
AddFirst to LinkedList... Time used: 14057 ticks
RemoveFirst from LinkedList... Time used: 5132 ticks
AddLast to LinkedList... Time used: 9294 ticks
RemoveLast from LinkedList... Time used: 4414 ticks
代码:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace Benchmarking
{
static class Collections
{
public static void run()
{
Random rand = new Random();
Stopwatch sw = new Stopwatch();
Stack stack = new Stack();
Queue queue = new Queue();
List list1 = new List();
List list2 = new List();
LinkedList linkedlist1 = new LinkedList();
LinkedList linkedlist2 = new LinkedList();
int dummy;
sw.Reset();
Console.Write("{0,40}", "Pushing to Stack...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
stack.Push(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Poping from Stack...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = stack.Pop();
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Enqueue to Queue...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
queue.Enqueue(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Dequeue from Queue...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = queue.Dequeue();
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Insert to List at the front...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
list1.Insert(0, rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "RemoveAt from List at the front...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = list1[0];
list1.RemoveAt(0);
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Add to List at the end...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
list2.Add(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "RemoveAt from List at the end...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = list2[list2.Count - 1];
list2.RemoveAt(list2.Count - 1);
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "AddFirst to LinkedList...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
linkedlist1.AddFirst(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "RemoveFirst from LinkedList...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = linkedlist1.First.Value;
linkedlist1.RemoveFirst();
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "AddLast to LinkedList...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
linkedlist2.AddLast(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "RemoveLast from LinkedList...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = linkedlist2.Last.Value;
linkedlist2.RemoveLast();
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
}
}
}
差异如此明显!
如您所见，Stack和Queue的性能非常快且可比较，这是预期的。
对于List，使用前和后有如此大的差异！ 令我惊讶的是，从末尾添加/删除的性能实际上可以与Stack的性能相媲美。
对于LinkedList，控制前面很快（比List快），但是对于末尾操作，删除操作非常缓慢。
那么...... 有没有专家可以解释一下：
- 使用
Stack和List末尾的性能相似， - 使用
List的前端和末端有所不同， - 使用
LinkedList的末尾如此缓慢的原因（不适用，因为这是使用Linq的Last()导致的编码错误，谢谢CodesInChaos）？
我认为我知道为什么List在前端表现不佳......因为List在这样做的时候需要将整个列表前后移动。如果我错了，请指正我。
附带说明：我的 System.Diagnostics.Stopwatch.Frequency 是 2435947，程序是针对 .NET 4 客户端档案和使用 C# 4.0 编译的，运行在 Windows 7 上的 Visual Studio 2010。
List是一个动态超额分配数组（也是许多其他语言标准库中经常出现的数据结构）。这意味着它在内部使用了一个“静态”数组（在.NET中称为“数组”，它不能被调整大小），该数组可能比列表的大小大得多。然后，追加操作仅增加计数器，并使用内部数组的下一个先前未使用的插槽。仅在内部数组变得太小而无法容纳所有项时才重新分配该数组（这需要复制所有元素）。发生这种情况时，数组的大小增加的因素（不是一个常数），通常是2。
这确保了追加的平摊时间复杂度（基本上是在一系列操作的情况下，每个操作的平均时间）即使在最坏的情况下也是O（1）。对于在前面添加元素，没有这样的优化是可行的（至少在同时保持随机访问和O（1）在末尾追加的情况下不可行）。它必须始终复制所有元素以将它们移动到它们的新插槽中（以腾出空间为新元素的第一个插槽）。 Stack 做同样的事情，只是您并不注意在前面添加元素时的差异，因为您只操作其中一个端点（速度较快的那个）。
获取链表的末尾取决于列表的内部情况。可以维护对最后一个元素的引用，但这会使得列表上的所有操作更加复杂，并且可能（我手头没有例子）使某些操作变得更加昂贵。如果没有这样的引用，则在末尾添加元素需要遍历整个链表以查找最后一个节点，这对于较大的列表来说当然非常慢。
正如@CodesInChaos指出的那样，你的链接列表操作存在缺陷。你现在看到的快速检索末尾节点的方式很可能是由LinkedList明确维护对最后一个节点的引用所造成的，如上所述。请注意，在不在两端的位置获取元素仍然很慢。
关于1：
Stack和List的性能相似并不奇怪。我会期望它们都使用数组和倍增策略。这会导致摊销常数时间的添加。
您可以在可以使用Stack的任何地方使用List，但这导致的代码表达力不如Stack。
关于2：
我想我知道为什么
List不太好地处理前面...因为List需要在做这个操作时将整个列表向后移动。
没错。在开头插入/删除元素很费时间，因为它移动了所有元素。另一方面，在开头获取或替换元素很便宜。
关于3：
您的慢LinkedList值是您基准测试代码中的错误。
从双向链表中删除或获取最后一项很便宜。在LinkedList的情况下，这意味着RemoveLast和Last很便宜。
但是您没有使用Last属性，而是使用了LINQ的扩展方法Last()。在不实现IList的集合上，它会迭代整个列表，使其具有O(n)的运行时间。