11/18
2013

Performance comparison for loops of List in java

Introduce five loop ways for both ArrayList and LinkedList, the performance test comparing different ways, Analysis of performance results according to the source code of ArrayList and LinkedList, summarize conclusions.

Through this article you can learn (1) Five traversal methods and their performance of List (2) foreach and Iterator implementation (3) understand of ArrayList and LinkedList implementation.
Before reading this article I hope you have learned sequential storage of ArrayList and chain structure of LinkedList.

Related: Performance comparison of different ways to iterate over HashMap

 

1. Five loop ways for List
Here is a brief example of a variety of traversal (in case of ArrayList) , the respective advantages and disadvantages will be analyzed later in this conclusion is given .
(1) for each loop

 

(2) obvious call iterator

or

 

(3) use get() with index increase, termination condition call size () function

 

(4) use get() with index increase, termination condition use temp variablereplace size () function

 

(5) use get() with index decrease

Before the test we can think about which performance is better of the five kinds of traversal above, based on the data structure of the List and understanding of Iterator .

 

2、Performance testing of five kinds of traversal above and contrast
The following is the source code of performance test, it will print time spent for different magnitude and different way of ArrayList and LinkedList loop.

PS: If you run the code with exception in thread “main” java.lang.OutOfMemoryError: Java heap space, reduce the size of list in main function.

getArrayLists fuction is used to return Arraylist of different size, getLinkedLists fuction is used to return LinkedList of different size。
loopListCompare function will loop list array use loop ways above.
Function begin with print are used to help print。

 

Test environment is is Windows7 32bits, 3.2G dual core cpu,  4G memory,  Java 7,  Eclipse -Xms512m -Xmx512m
Final test results are as follows :

The first table show the compare results for the ArrayList, second table shows the compare result of LinkedList.

Row represents time spent for different size of list with same loop way, Column represents  time spent for different  loop way with same list.

PS: As for the first loop time will be a little more time consuming, result for loop way use for each is a little deviation.You can change the order of different loop way in the test code, you will find time-consuming with loop way use for each  is close to loop way use for iterator.

 

3、Analysis performance test results
(1) foreach
foreach is a loop structure, introduced in Java SE5.0, for (Integer j: list) should be readed as for each int in list.
for (Integer j : list) almost equivalent to

The following analysis will classified obvious call iterator and for each as loop way of Iterator, the other three are classified as loop way of get.

We have found that one of the major benefits of foreach, the simple line to achieve a four-line features, that make the code simple and beautiful, the other big advantage is relative to loop way of get, foreach no need to care about index out of bound, so you will not go wrong. Effective-Java recommended use foreach instead of index loop, we will verify this statement.

 

class which can use foreach must implement the Iterable interface, Java’s Collection inherit from interfaces already, List implements Collection. The Iterable interface contains only one function, source code is as follows:

iterator () is used to return an Iterator. from implementation of foreach we can see , it will call this function to get Iterator, and then get the next element through the next() function of Iterator, hasNext() determine whether there are more elements. Iterator source as follows:

 

(2) Analysis performance test results of ArrayList

PS: As for the first loop time will be a little more time consuming, result for loop way use for each is a little deviation.You can change the order of different loop way in the test code, you will find time-consuming with loop way use for each  is close to loop way use for iterator.

From the above we can see that :

a. the time-consuming is about same when size of arrayList size is one hundred thousand or less.
b. when size of arrayList size is bigger than one hundred thousand, loop use Iterator cost more time than loop use get, but just abount 50ms. use temp variable is better than list.size() function.

following are implements of Iterator and get() function in ArrayList

As you see above, both get() function of ArrayList and next() function of Iterator use index to get element directly, just a few more judgments in next().

c. We can see cost 50ms more even when size of ArrayList is 10,000,000.  The time-consuming is about same when size of arrayList size is one hundred thousand or less,  and it’s more commmon this situation, so we can choose foreach consider about the advantage of foreach.

 

(3) Analysis performance test results of LinkedList

PS: As for the first loop time will be a little more time consuming, result for loop way use for each is a little deviation.You can change the order of different loop way in the test code, you will find time-consuming with loop way use for each  is close to loop way use for iterator.

From the above we can see that :
a. loop way by get() is slower than loop wary by Iterator almost 100 times when size of LinkedList is close to 10,000. loop way by get() is about 8 seconds when size of LinkedList is 100,000.
following are implements of Iterator and get() function in LinkedList:

As we can see above, the next() function get element by next pointer of last element, the time complexity of traversing use Iterator is O(n). but get() get element from the first index every time, find an element of time complexity is O(n), the time complexity of traversing use get() reached O(n2).

So loop LinkedList recommend using foreach, avoid using get().

 

(4) Compare performance test results of ArrayList  and LinkedList
Through the above results we can see. time-comsuming is almost same for ArrayList and LinkedList when loop by foreach, but the time complexity of get() for LinkedList is O(n), and just O(1) for ArrayList, and ArrayList cost less memory, so we recommended using ArrayList first when choose List.

 

4、Summarize Conclusions
Through the analysis above, we can basically summarize:

(1) Whether ArrayList or LinkedList, loop it recommended foreach. avoid loop LinkedList by get() especially when size is big.
(2) Preferred using ArrayList when choose List. We can use LinkedList For situations there are more operations of insert and delete.
(3) There is situation we need the index of List when loop, this time we should consider use get() or foreach and count++ according necceary. If LinkedList, recommended use foreach and count++.

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

One thought on “Performance comparison for loops of List in java