表演差异如此戏剧性？
表演差异如此戏剧性？
提问于 2018-04-02 02:30:35
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> - 这是由于使用Linq的编码错误
Last()
回答 2
Stack Overflow用户
发布于 2018-04-02 10:30:57
事关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)运行时。
Stack Overflow用户
发布于 2018-04-02 11:58:50
L这意味着它在内部使用“静态”数组(一个不能调整大小的数组，在.NET中称为“数组”)，该数组可能而且通常大于列表的大小。然后，附加一个计数器并使用内部数组的下一个未使用的槽。如果内部数组变小以容纳所有项，则只重新分配数组(这需要复制所有元素)。当发生这种情况时，数组的大小会增加一个因子(而不是常数)，通常是2。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100007903
复制相关文章
相似问题
腾讯云开发者
