性能差异......如此戏剧性？ [英] Performance differences... so dramatic?

问题描述

刚才我看了关于<$ C $一些帖子C>列表< T> VS 的LinkedList< T> ，所以我决定基准一些结构自己。我为基准堆栈< T> ，队列< T> ，列表< T> 和的LinkedList< T> 由前/末尾添加数据和删除数据/。这里的基准测试结果：

 推叠...使用时间：7067蜱
从堆栈坡平...使用时间：2508年蜱
 
排队到队列...使用时间：7509蜱
出列从队列...使用时间：2973年蜱
 
插入到列表在前面......时间用于：5211897蜱
 RemoveAt移除从列表中的前...时间用于：5198380蜱
 
添加到列表结尾......时使用：5691从列表蜱
 RemoveAt移除末...使用时间：3484蜱
 
 addfirst仅到链表...使用时间：从14057滴答的LinkedList 
 RemoveFirst ...使用时间：5132蜱
 
 addlast仅到链表...使用时间：4414蜱
   RemoveLast pre> 
 
 
代码：  http://pastebin.com/k3SWx9kF    http://pastebin.com/5Qe22dmK  
（代码太长，所以我把它放在那里，而不是在这里。）
 
 
 
的差异所以戏剧性！
 
 
 
正如你所看到的，堆叠式和LT的表现; T> 和队列< T> 是快速和可比，这是预期。
 
 
 
有关列表< T> ，使用前和结束时有这么大的差别！让我吃惊，添加/从端排出的表现实际上是堪比堆叠式和LT的表现; T>  
 
 
 
有关的LinkedList< T> ，与前操作速度快（-er比列表< T> ）的的，但为底，它是用于去除操纵与端是太令人难以置信的慢
 
 
 
 
 
 
所以......可以在任何专家解释：
 
 
 
 
 
在使用性能相似堆栈< T> 和年底名单< T> ，
 
 
在使用前的差异和结束列表< T> 和 
 
 
，使用的结束的原因的LinkedList< T> 是所以的慢（不适用，因为这是一个编码错误是由于使用的LINQ的最后（），感谢CodesInChaos ）？
 
 
 
 
 
我想我知道为什么名单，LT ; T> 不处理前那么好......因为列表< T> 需要移动整个名单回来，来回做的时候那。纠正我，如果我错了。
 
 
 
 P.S。我的 System.Diagnostics.Stopwatch.Frequency 是 2435947 ，程序针对的是.NET 4客户端配置文件和编译与C＃4.0，在Windows 7上的Visual Studio 2010 
 
 
解决方案
 
 关于1： 
 
 
 
 堆栈< T> 和列表< T> 的性能是相似也就不足为奇了。我期望他们都使用数组用加倍的策略。这导致了分期常量时间增加
 
 
 
您可以使用列表< T> 到处都可以使用堆栈< T> ，而它会导致更少的代码表现 
 
 
 
 关于2： 
 
 
 < BLOCKQUOTE> 
 
我想我知道为什么列表< T> 不处理前那么好......因为名单，LT ; T> 需要移动整个名单回来，来回做，当
 
  
 
 
这是正确的。插入/开头移除元素是昂贵的，因为它移动的所有元素。 。获取或伊始，另一方面替换元素便宜
 
 
 
 关于3： 
 
 
 
您慢的LinkedList< T> .RemoveLast 值是在基准测试代码错误
 
 
 
删除或者得到一个双向链表的最后一个项目是便宜。在的LinkedList<的情况下，T> 这意味着 RemoveLast 和最后很便宜。
 
 
 
但你不使用最后属性，但LINQ的扩展方法末（）。在没有实现集合的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: http://pastebin.com/k3SWx9kF http://pastebin.com/5Qe22dmK
(The code is too long so I put it there instead of here.)

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屋！