江苏龙网

  1. 首页 > 生活 > >

LinkedList 和 ArrayDeque的性能分析

找到答案了，还是谷歌大法好http://java-performance.info/linkedlist-performance/java.util.LinkedList performanceLeave a replyby Mikhail Vorontsov
We will discuss LinkedList performance in this article. Generally, it is a bad idea to use it in performance-critical code. But, sometimes you may need it…
LinkedList is a list implementation with each node having pointers to previous and next nodes. Such implementation allows to add/remove/update elements fast, but only if:
Either they are first/last elements orYou have scrolled to required element using ListIteratorIn all other cases list modification is O(n) complexity operation. Access to list elements (get) is also O(n) operation (actually, list will scroll either from head or from tail, so it would take no more than size() / 2 operations to access any LinkedList node.
Author is aware of only two cases when you could use a LinkedList:
You are implementing a FIFO buffer and you don’t need to add/remove elements to the middle of the buffer (or rarely need to do it). Adding/removing from LinkedList head/tail is very fast. Nevertheless, consider using java.util.ArrayDeque in this case. It is also optimized for fast head/tail operations (more on this later).You need to add/remove elements from the middle of the list too often.LinkedList and ArrayDeque as FIFO bufferLet’s see how fast can be a FIFO queue if it uses LinkedList or ArrayDeque. We will prefill an instance of both classes with a number of values and when add 5 elements to the head of the lists and when remove 5 elements from the tail. Adding/removing will be done 100M times in a loop:
final int PREFILL_COUNT = 100_000;final int LOOP_COUNT = 100_000_000;final LinkedList\u0026lt;Integer\u0026gt; lst = new LinkedList\u0026lt;Integer\u0026gt;();final Integer val = 1;for ( int i = 0; i \u0026lt; PREFILL_COUNT; ++i ) lst.add( 35 );//start measuring time here\u0026lt;br/\u0026gt;for ( int i = 0; i \u0026lt; LOOP_COUNT; ++i ){ for ( int j = 0; j \u0026lt; 5; ++j ) lst.addFirst( val ); for ( int j = 0; j \u0026lt; 5; ++j ) lst.removeLast();} Results are quite interesting. LinkedList performance in theory doesn’t depend on the number of prefilled elements. In practice, each add operation creates a node (4 Objects – node itself, previous and next pointers and the value) and each remove operation cleans these objects, thus creating quite a noticeable amount of garbage to collect. The bigger is memory footprint of your application, the slower would be these garbage collections. ArrayDeque objects don’t create their own garbage as long as collection size would stabilize, so its performance doesn’t really depend on the current size.
LinkedList, 10 elems prefilledLinkedList, 100K elems prefilledLinkedList, 1M elems prefilledArrayDeque, 10 elems prefilledArrayDeque, 100K elems prefilledArrayDeque, 1M elems prefilledJava 67.533 sec7.879 sec9.461 sec2.323 sec2.422 sec2.446 secJava 76.004 sec6.493 sec7.945 sec2.035 sec2.160 sec2.343 secHow to use LinkedList properlyThe main property of LinkedList to remember – it offers only sequential access to its elements instead of random access of ArrayList. So, don’t try to adapt logic you’ve previously written withArrayList in mind for the LinkedList – yes, they are both lists, but they are implemented too differently.


推荐阅读


上一篇：印刷电商咋做，买系统还是自己团队开发好

下一篇：小米有溢价权嘛，如果有例如小米六可以定价提升多少