刚才我读了some posts about List<T> vs LinkedList<T> ，所以我决定自己对一些结构进行基准测试。我对 Stack<T> 进行了基准测试, Queue<T> , List<T>和 LinkedList<T>通过向/从前端/端添加数据和删除数据。这是基准测试结果:
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<int> stack = new Stack<int>();
Queue<int> queue = new Queue<int>();
List<int> list1 = new List<int>();
List<int> list2 = new List<int>();
LinkedList<int> linkedlist1 = new LinkedList<int>();
LinkedList<int> linkedlist2 = new LinkedList<int>();
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<T> 的性能和 Queue<T>速度快且具有可比性，这是意料之中的。
对于 List<T> ，使用前端和后端有这么大的区别!令我惊讶的是，从末尾添加/删除的性能实际上与 Stack<T> 的性能相当。 .
对于 LinkedList<T> , 前面的操作速度很快(-er than List<T> )，但最后，删除速度非常慢最后的操作也是如此。
所以...任何专家都可以说明:
- 使用
Stack<T>的性能相似性和List<T>的结尾, List<T>的前端和末尾的使用差异, 和使用(不适用，因为这是使用 Linq 的LinkedList<T>结尾的原因这么慢Last()的编码错误，感谢 CodesInChaos)？
我想我知道为什么了List<T>不能很好地处理前面......因为List<T>这样做时需要来回移动整个列表。如果我错了，请纠正我。
附言我的System.Diagnostics.Stopwatch.Frequency是2435947 , 该程序针对 .NET 4 Client Profile，并在 Windows 7 Visual Studio 2010 上使用 C# 4.0 编译。
最佳答案
关于 1:
Stack<T>的和List<T>的表现相似并不奇怪。我希望他们都使用具有加倍策略的数组。这导致摊销的恒定时间增加。
您可以使用 List<T>您可以在任何地方使用 Stack<T> , 但是 it leads to less expressive code .
关于 2:
I think I know why
List<T>doesn't handle the front so well... becauseList<T>needs to move the whole list back and fro when doing that.
没错。在开头插入/删除元素是昂贵的，因为它移动了所有元素。另一方面，在开头获取或替换元素很便宜。
关于 3:
你的慢LinkedList<T>.RemoveLast value 是您的基准测试代码中的一个错误。
删除或获取双向链表的最后一项成本很低。在LinkedList<T>的情况下这意味着RemoveLast和 Last很便宜。
但你没有使用 Last属性，而是 LINQ 的扩展方法 Last() .在未实现 IList<T> 的集合上它遍历整个列表，给它 O(n)运行时。
关于c# - 性能差异...如此显着？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13211277/