性能差异......这么戏剧化？ [英] Performance differences... so dramatic?

查看：89 发布时间：2016/12/15 18:43:21 c# .net data-structures collections

本文介绍了性能差异......这么戏剧化？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

刚才我阅读了一些有关 List< T> vs LinkedList< T> ，所以我决定自己对一些结构进行基准测试。我基准化 Stack< T> ， Queue< T> ， List< T&通过向/从前/后添加数据和移除数据来创建和 LinkedList< T> 。这是基准结果：

 推送到堆栈...使用时间：7067 ticks 
从堆栈弹出...所用时间：2508分钟
 
入队到队列...使用时间：7509分钟
从队列中出队...使用时间：2973分钟
 
插入到列表在前面...使用时间：5211897 ticks 
 RemoveAt从前面的列表...使用时间：5198380 ticks 
 
添加至列表到最后...使用时间：5691 ticks 
 RemoveAt从列表结束...使用时间：3484 ticks 
 
 AddFirst到LinkedList ...使用时间：14057 ticks 
 RemoveFirst从LinkedList ...使用时间：5132 ticks 
 
 AddLast to LinkedList ...使用时间：9294 ticks 
 RemoveLast from LinkedList ...使用时间：4414 ticks

代码：

  
 using System.Collections.Generic; 
 using System.Linq; 
 using System.Text; 
 using System.Diagnostics; 
 
命名空间基准化
 {
静态类集合
 {
 public static void run（）
 {
 Random rand = new随机（）; 
秒表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\\\
，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\\\
，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（使用时间：{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\\\
，sw.ElapsedTicks）; 
 
 
 sw.Reset（）; 
 Console.Write（{0,40}，添加到列表结束...）; 
 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\\\
，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\\\
，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\\\
，sw.ElapsedTicks）; 
} 
} 
}

 
 
 如您所见， Stack< T> 和<$ 
 
 
  列表< T>< / code>，使用前端和末端有这么多差别！令我惊讶的是，添加/删除操作的性能实际上与 Stack< T> 的性能相当。 
 
 
对于 LinkedList< T> ，用前面操作是快速的（比 List< T>  
 
 
 
 
 
   p>所以...任何专家都可以：
 
 使用 Stack< T& 结束列表< T> ，
 
   List 和 
 
 使用 LinkedList< T> 是 慢（不适用，因为这是一个编码错误，由于使用Linq的 Last（）      ; T> 不处理前面这么好...因为 List< T> 需要移动整个列表那。如果我错了，请更正我。
 
 
 我的 System.Diagnostics.Stopwatch.Frequency 是 2435947 ，并且该程序针对.NET 4客户端配置文件并编译
解决方案
 关于1： 
 
 
  堆叠< T> 和列表< T> 性能相似并不奇怪。我期望他们都使用具有加倍策略的数组。 
 
 
 您可以使用 List< T>  c $ c> Stack< T> ，但 
 
   
  blockquote> 
 我想我知道为什么 List< T> 不处理前面这么好...因为 List< ; T> 需要来回移动整个列表。
 
 在开始插入/移除元素是昂贵的，因为它移动所有元素。 
 
 
 $ b  关于3： b 
您的缓慢 LinkedList< T> .RemoveLast 值是您的基准代码中的错误。
 
 
 或者获得双向链表的最后一项是便宜的。在 LinkedList< T> 的情况下，意味着 RemoveLast 和 Last  
 
 
但是你没有使用 Last 属性，而是LINQ的扩展方法 Last（）。对于不实现 IList< T> 的集合，它迭代整个列表，给它 O（n） 。
 
Just now I read some posts about List<T> vs LinkedList<T>, so I decided to benchmark some structures myself. I benchmarked Stack<T>, Queue<T>, List<T> and LinkedList<T> by adding data and removing data to/from the front/end. Here's the benchmark result:
               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
Code: 
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);
        }
    }
}
The differences are so dramatic!

As you can see, the performance of Stack<T> and Queue<T> are fast and comparable, that's expected.

For List<T>, using the front and the end has so much differences! And to my surprise, performance of adding/removing from the end is actually comparable to the performance of Stack<T>.

For LinkedList<T>, manipulating with the front is fast (-er than List<T>), but for the end, it is incredibly slow for removing manipulating with the end is too.



So... can any experts account on:

the similarity in performance of using Stack<T> and the end of List<T>,
the differences in using the front and the end of List<T>, and

the reason that using the end of LinkedList<T> is so slow (not applicable as that is a coding error due to the use of Linq's Last(), thanks to CodesInChaos)?
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. Correct me if I am wrong.

P.S. My System.Diagnostics.Stopwatch.Frequency is 2435947, and the program is targeted to .NET 4 Client Profile and compiled with C# 4.0, on Windows 7 Visual Studio 2010.
 解决方案 
Concerning 1:

Stack<T>'s and List<T>'s performance being similar isn't surprising. I'd expect both of them to use arrays with a doubling strategy. This leads to amortized constant-time additions.

You can use List<T> everywhere you can use Stack<T>, but it leads to less expressive code.

Concerning 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.
That's correct. Inserting/removing elements at the beginning is expensive because it moves all elements. Getting or replacing elements at the beginning on the other hand is cheap.

Concerning 3:

Your slow LinkedList<T>.RemoveLast value is a mistake in your benchmarking code.

Removing or getting the last item of a doubly linked list is cheap. In the case of LinkedList<T> that means that RemoveLast and Last are cheap.

But you weren't using the Last property, but LINQ's extension method Last(). On collections that don't implement IList<T> it iterates the whole list, giving it O(n) runtime.

                        这篇关于性能差异......这么戏剧化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文

性能差异......这么戏剧化？ [英] Performance differences... so dramatic?

问题描述

相关文章

C#/.NET最新文章

热门教程

热门工具

登录关闭

性能差异......这么戏剧化？ [英] Performance differences... so dramatic?

问题描述

相关文章

C#/.NET最新文章

热门教程

热门工具

登录 关闭

登录关闭