刚才我读了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> )，但最后，删除速度非常慢最后的操作也是如此。

所以...任何专家都可以说明:

1. 使用 Stack<T> 的性能相似性和 List<T> 的结尾,
2. List<T>的前端和末尾的使用差异, 和
3. 使用LinkedList<T>结尾的原因这么慢(不适用，因为这是使用 Linq 的 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... because List<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/