前言
通過本文你可以了解List的五種遍歷方式及各自性能和foreach及Iterator的實(shí)現(xiàn)，加深對ArrayList和LinkedList實(shí)現(xiàn)的了解。下面來一起看看吧。
一、List的五種遍歷方式
1、for each循環(huán)
|
1
2
3
4
|
List<Integer> list = new ArrayList<Integer>();for (Integer j : list) { // use j} |
2、顯示調(diào)用集合迭代器
|
1
2
3
4
|
List<Integer> list = new ArrayList<Integer>();for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) { iterator.next();} |
或
|
1
2
3
4
5
|
List<Integer> list = new ArrayList<Integer>();Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()) { iterator.next();} |
3、下標(biāo)遞增循環(huán)，終止條件為每次調(diào)用size()函數(shù)比較判斷
|
1
2
3
4
|
List<Integer> list = new ArrayList<Integer>();for (int j = 0; j < list.size(); j++) { list.get(j);} |
4、下標(biāo)遞增循環(huán)，終止條件為和等于size()的臨時變量比較判斷
|
1
2
3
4
5
|
List<Integer> list = new ArrayList<Integer>();int size = list.size();for (int j = 0; j < size; j++) { list.get(j);} |
5、下標(biāo)遞減循環(huán)
|
1
2
3
4
|
List<Integer> list = new ArrayList<Integer>();for (int j = list.size() - 1; j >= 0; j--) { list.get(j);} |
List五種遍歷方式的性能測試及對比
以下是性能測試代碼，會輸出不同數(shù)量級大小的ArrayList和LinkedList各種遍歷方式所花費(fèi)的時間。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
package cn.trinea.java.test;import java.text.DecimalFormat;import java.util.ArrayList;import java.util.Calendar;import java.util.Iterator;import java.util.LinkedList;import java.util.List;/** * JavaLoopTest * * @author www.trinea.cn 2013-10-28 */public class JavaLoopTest { public static void main(String[] args) { System.out.print("compare loop performance of ArrayList"); loopListCompare(getArrayLists(10000, 100000, 1000000, 9000000)); System.out.print("\r\n\r\ncompare loop performance of LinkedList"); loopListCompare(getLinkedLists(100, 1000, 10000, 100000)); } public static List<Integer>[] getArrayLists(int... sizeArray) { List<Integer>[] listArray = new ArrayList[sizeArray.length]; for (int i = 0; i < listArray.length; i++) { int size = sizeArray[i]; List<Integer> list = new ArrayList<Integer>(); for (int j = 0; j < size; j++) { list.add(j); } listArray[i] = list; } return listArray; } public static List<Integer>[] getLinkedLists(int... sizeArray) { List<Integer>[] listArray = new LinkedList[sizeArray.length]; for (int i = 0; i < listArray.length; i++) { int size = sizeArray[i]; List<Integer> list = new LinkedList<Integer>(); for (int j = 0; j < size; j++) { list.add(j); } listArray[i] = list; } return listArray; } public static void loopListCompare(List<Integer>... listArray) { printHeader(listArray); long startTime, endTime; // Type 1 for (int i = 0; i < listArray.length; i++) { List<Integer> list = listArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); for (Integer j : list) { // use j } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, listArray.length, "for each", endTime - startTime); } // Type 2 for (int i = 0; i < listArray.length; i++) { List<Integer> list = listArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); // Iterator<Integer> iterator = list.iterator(); // while(iterator.hasNext()) { // iterator.next(); // } for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) { iterator.next(); } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, listArray.length, "for iterator", endTime - startTime); } // Type 3 for (int i = 0; i < listArray.length; i++) { List<Integer> list = listArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); for (int j = 0; j < list.size(); j++) { list.get(j); } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, listArray.length, "for list.size()", endTime - startTime); } // Type 4 for (int i = 0; i < listArray.length; i++) { List<Integer> list = listArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); int size = list.size(); for (int j = 0; j < size; j++) { list.get(j); } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, listArray.length, "for size = list.size()", endTime - startTime); } // Type 5 for (int i = 0; i < listArray.length; i++) { List<Integer> list = listArray[i]; startTime = Calendar.getInstance().getTimeInMillis(); for (int j = list.size() - 1; j >= 0; j--) { list.get(j); } endTime = Calendar.getInstance().getTimeInMillis(); printCostTime(i, listArray.length, "for j--", endTime - startTime); } } static int FIRST_COLUMN_LENGTH = 23, OTHER_COLUMN_LENGTH = 12, TOTAL_COLUMN_LENGTH = 71; static final DecimalFormat COMMA_FORMAT = new DecimalFormat("#,###"); public static void printHeader(List<Integer>... listArray) { printRowDivider(); for (int i = 0; i < listArray.length; i++) { if (i == 0) { StringBuilder sb = new StringBuilder().append("list size"); while (sb.length() < FIRST_COLUMN_LENGTH) { sb.append(" "); } System.out.print(sb); } StringBuilder sb = new StringBuilder().append("| ").append(COMMA_FORMAT.format(listArray[i].size())); while (sb.length() < OTHER_COLUMN_LENGTH) { sb.append(" "); } System.out.print(sb); } TOTAL_COLUMN_LENGTH = FIRST_COLUMN_LENGTH + OTHER_COLUMN_LENGTH * listArray.length; printRowDivider(); } public static void printRowDivider() { System.out.println(); StringBuilder sb = new StringBuilder(); while (sb.length() < TOTAL_COLUMN_LENGTH) { sb.append("-"); } System.out.println(sb); } public static void printCostTime(int i, int size, String caseName, long costTime) { if (i == 0) { StringBuilder sb = new StringBuilder().append(caseName); while (sb.length() < FIRST_COLUMN_LENGTH) { sb.append(" "); } System.out.print(sb); } StringBuilder sb = new StringBuilder().append("| ").append(costTime).append(" ms"); while (sb.length() < OTHER_COLUMN_LENGTH) { sb.append(" "); } System.out.print(sb); if (i == size - 1) { printRowDivider(); } }} |
PS：如果運(yùn)行報異常in thread “main” java.lang.OutOfMemoryError: Java heap space，請將main函數(shù)里面list size的大小減小。
其中getArrayLists函數(shù)會返回不同size的ArrayList，getLinkedLists函數(shù)會返回不同size的LinkedList。
loopListCompare函數(shù)會分別用上面的遍歷方式1-5去遍歷每一個list數(shù)組(包含不同大小list)中的list。
print開頭函數(shù)為輸出輔助函數(shù)。
測試環(huán)境為Windows7 32位系統(tǒng) 3.2G雙核CPU 4G內(nèi)存，Java 7，Eclipse -Xms512m -Xmx512m
最終測試結(jié)果如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
compare loop performance of ArrayList-----------------------------------------------------------------------list size | 10,000 | 100,000 | 1,000,000 | 10,000,000-----------------------------------------------------------------------for each | 1 ms | 3 ms | 14 ms | 152 ms -----------------------------------------------------------------------for iterator | 0 ms | 1 ms | 12 ms | 114 ms -----------------------------------------------------------------------for list.size() | 1 ms | 1 ms | 13 ms | 128 ms -----------------------------------------------------------------------for size = list.size() | 0 ms | 0 ms | 6 ms | 62 ms -----------------------------------------------------------------------for j-- | 0 ms | 1 ms | 6 ms | 63 ms ----------------------------------------------------------------------- compare loop performance of LinkedList-----------------------------------------------------------------------list size | 100 | 1,000 | 10,000 | 100,000-----------------------------------------------------------------------for each | 0 ms | 1 ms | 1 ms | 2 ms -----------------------------------------------------------------------for iterator | 0 ms | 0 ms | 0 ms | 2 ms -----------------------------------------------------------------------for list.size() | 0 ms | 1 ms | 73 ms | 7972 ms -----------------------------------------------------------------------for size = list.size() | 0 ms | 0 ms | 67 ms | 8216 ms -----------------------------------------------------------------------for j-- | 0 ms | 1 ms | 67 ms | 8277 ms ----------------------------------------------------------------------- |
第一張表為ArrayList對比結(jié)果，第二張表為LinkedList對比結(jié)果。
表橫向?yàn)橥槐闅v方式不同大小list遍歷的時間消耗，縱向?yàn)橥籰ist不同遍歷方式遍歷的時間消耗。
PS：由于首次遍歷List會稍微多耗時一點(diǎn)，for each的結(jié)果稍微有點(diǎn)偏差，將測試代碼中的幾個Type順序調(diào)換會發(fā)現(xiàn)，for each耗時和for iterator接近。
遍歷方式性能測試結(jié)果分析
1、foreach介紹
foreach是Java SE5.0引入的功能很強(qiáng)的循環(huán)結(jié)構(gòu)，for (Integer j : list)應(yīng)讀作for each int in list。
for (Integer j : list)實(shí)現(xiàn)幾乎等價于
|
1
2
3
4
|
Iterator<Integer> iterator = list.iterator();while(iterator.hasNext()) { Integer j = iterator.next();} |
foreach代碼書寫簡單，不必關(guān)心下標(biāo)初始值和終止值及越界等，所以不易出錯
2、ArrayList遍歷方式結(jié)果分析
a. 在ArrayList大小為十萬之前，五種遍歷方式時間消耗幾乎一樣
b. 在十萬以后，第四、五種遍歷方式快于前三種，get方式優(yōu)于Iterator方式，并且
|
1
2
3
4
|
int size = list.size();for (int j = 0; j < size; j++) { list.get(j);} |
用臨時變量size取代list.size()性能更優(yōu)。我們看看ArrayList中迭代器Iterator和get方法的實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } ……} public E get(int index) { rangeCheck(index); return elementData(index);} |
從中可以看出get和Iterator的next函數(shù)同樣通過直接定位數(shù)據(jù)獲取元素，只是多了幾個判斷而已。
c. 從上可以看出即便在千萬大小的ArrayList中，幾種遍歷方式相差也不過50ms左右，且在常用的十萬左右時間幾乎相等，考慮foreach的優(yōu)點(diǎn)，我們大可選用foreach這種簡便方式進(jìn)行遍歷。
3、LinkedList遍歷方式結(jié)果分析
a. 在LinkedList大小接近一萬時，get方式和Iterator方式就已經(jīng)差了差不多兩個數(shù)量級，十萬時Iterator方式性能已經(jīng)遠(yuǎn)勝于get方式。
我們看看LinkedList中迭代器和get方法的實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
private class ListItr implements ListIterator<E> { private Node<E> lastReturned = null; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } ……} public E get(int index) { checkElementIndex(index); return node(index).item;} /** * Returns the (non-null) Node at the specified element index. */Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }} |
從上面代碼中可以看出LinkedList迭代器的next函數(shù)只是通過next指針快速得到下一個元素并返回。而get方法會從頭遍歷直到index下標(biāo)，查找一個元素時間復(fù)雜度為哦O(n)，遍歷的時間復(fù)雜度就達(dá)到了O(n2)。
所以對于LinkedList的遍歷推薦使用foreach，避免使用get方式遍歷。
4、ArrayList和LinkedList遍歷方式結(jié)果對比分析
從上面的數(shù)量級來看，同樣是foreach循環(huán)遍歷，ArrayList和LinkedList時間差不多，可將本例稍作修改加大list size會發(fā)現(xiàn)兩者基本在一個數(shù)量級上。
但ArrayList get函數(shù)直接定位獲取的方式時間復(fù)雜度為O(1)，而LinkedList的get函數(shù)時間復(fù)雜度為O(n)。
再結(jié)合考慮空間消耗的話，建議首選ArrayList。對于個別插入刪除非常多的可以使用LinkedList。
結(jié)論總結(jié)
通過上面的分析我們基本可以總結(jié)下：
- 無論ArrayList還是LinkedList，遍歷建議使用foreach，尤其是數(shù)據(jù)量較大時LinkedList避免使用get遍歷。
- List使用首選ArrayList。對于個別插入刪除非常多的可以使用LinkedList。
- 可能在遍歷List循環(huán)內(nèi)部需要使用到下標(biāo)，這時綜合考慮下是使用foreach和自增count還是get方式。
總結(jié)
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家學(xué)習(xí)或者使用Java的時候能有所幫助，如果有疑問大家可以留言交流。
