Alv*_*ong 51 .net c# collections data-structures
刚才我读了一些关于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>,使用前面的操作是快速的(比 - 更List<T>),但是最后,对于去除操作也是非常慢的.
所以...任何专家都可以说:
Stack<T>和结束的性能相似List<T>,List<T>,和LinkedList<T>是如此之慢Last(),感谢CodesInChaos)？我想我知道为什么List<T>不能很好地处理前面...因为List<T>需要在执行此操作时来回移动整个列表.如果我错了,请纠正我.
PS My System.Diagnostics.Stopwatch.Frequencyis 2435947,该程序的目标是.NET 4 Client Profile,并在Windows 7 Visual Studio 2010上使用C#4.0进行编译.
Cod*_*aos 35
关于1:
Stack<T>和List<T>他们的表现相似并不令人惊讶.我希望他们两个都使用具有倍增策略的数组.这导致摊销的恒定时间添加.
您可以List<T>在任何可以使用的地方使用它Stack<T>,但它会导致代码性能降低.
关于2:
我想我知道为什么
List<T>不能很好地处理前面...因为List<T>需要在执行此操作时来回移动整个列表.
那是对的.在开头插入/移除元素是昂贵的,因为它移动所有元素.另一方面,在开始时获取或替换元素是便宜的.
关于3:
您的慢速LinkedList<T>.RemoveLast值是基准测试代码中的错误.
删除或获取双向链表的最后一项很便宜.在的情况下,LinkedList<T>这意味着,RemoveLast和Last很便宜.
但是你没有使用该Last属性,而是使用LINQ的扩展方法Last().在没有实现IList<T>它的集合上迭代整个列表,给它O(n)运行时.
小智 13
List<T>是一个动态的过度分配数组(您还将在许多其他语言的标准库中看到的数据结构).这意味着它在内部使用"静态"数组(无法调整大小的数组,在.NET中称为"数组"),该数组可能并且通常大于列表的大小.然后,附加只是增加一个计数器并使用内部数组的下一个先前未使用的插槽.如果内部数组变小以容纳所有项目,则仅重新分配数组(需要复制所有元素).当发生这种情况时,数组的大小会增加一个因子(不是常数),通常为2.
这确保即使在最坏的情况下,用于附加的摊销时间复杂度(基本上,在长序列操作上的每个操作的平均时间)也是O(1).对于在前面添加,没有这样的优化是可行的(至少在保持随机访问和O(1)在末尾附加时).它总是必须复制所有元素以将它们移动到新的插槽中(为第一个插槽中添加的元素腾出空间).Stack<T> 做同样的事情,你只是没有注意到添加到前面的差异,因为你只在一端操作(快速的一端).
获取链表的结尾很大程度上取决于列表的内部.一个可以维持到最后一个元素的引用,但是这使得列表更复杂的所有操作,并可能(我没有在手边的例子)使一些操作更加昂贵.缺少这样的引用,追加到最后需要遍历链表的所有元素以找到最后一个节点,这对于非平凡大小的列表来说当然非常慢.
正如@CodesInChaos所指出的,你的链表操作是有缺陷的.如上所述,您现在看到的快速检索结束很可能是由LinkedList<T>显式维护对最后一个节点的引用引起的.请注意,获取不在任何一端的元素仍然很慢.
速度主要来自插入,删除或搜索项目所需的操作数.您已经注意到,该列表需要内存传输.
Stack是一个列表,只能在top元素访问 - 而且计算机总是知道它在哪里.
链表是另一回事:列表的开头是已知的,因此从开始添加或删除非常快 - 但找到最后一个元素需要时间.缓存最后一个元素OTOH的位置仅值得添加.对于删除,需要遍历完整列表减去一个元素以找到"钩子"或指向最后一个的指针.
只要查看数字,就可以对每个数据结构的内部进行一些有根据的猜测: