ArrayList和LinkedList地幾種循環(huán)遍歷方式及性能對比分析報告報告材料

1、主要介紹ArrayList和LinkedList 這兩種list的五種循環(huán)遍歷方式，各種方式的性能測試 對比，根據(jù)ArrayList 和LinkedList的源碼實現(xiàn)分析性能結果，總結結論。通過本文你可以了解(1)List的五種遍歷方式及各自性能(2)foreach及Iterator的實現(xiàn) 加深對ArrayList和LinkedList實現(xiàn)的了解。閱讀本文前希望你已經(jīng)了解ArrayList順序存儲和LinkedList鏈式的結構，本文不對此進行介紹。相關：HashMap循環(huán)遍歷方式及其性能對比1. List的五種遍歷方式下面只是簡單介紹各種遍歷示例 (以ArrayList為例)，各自優(yōu)劣會在本

2、文后面進行分析給出 結論。(1) for each 循環(huán)Java1川乳專律勢魏幣船lF1 List list = new ArrayList();2 for (Integer j : list) 3 / use j4 (2) 顯示調(diào)用集合迭代器Javad I矗鑒經(jīng)勲 J1 List list = new ArrayList();2 for (lterator iterator = list.iterator(); iterator.hasNext();) 3 iterator.next();4 或Java| 1： ：1 Listlist = newArrayList();2 Iteratori

3、terator=list.iterator();3 while (iterator.hasNext()4iterator.next();5 (3) 下標遞增循環(huán)，終止條件為每次調(diào)用size()函數(shù)比較判斷Java1 I 滝勰當聰 /1 List list = new ArrayList();2 for (int j = 0; j list.size(); j+)3 list.get(j);4 (4) 下標遞增循環(huán)，終止條件為和等于 size()的臨時變量比較判斷Java1 List list = new ArrayList();2 int size = list.size();3 for (i

4、nt j = 0; j size; j+)4 list.get(j);5 (5) 下標遞減循環(huán)Javad 1幕J1 List list = new ArrayList();2 for (int j = list.size() - 1; j = 0; j-) 3 list.get(j);4 在測試前大家可以根據(jù)對ArrayList和LinkedList數(shù)據(jù)結構及Iterator的了解，想想上面五種遍歷方式哪個性能更優(yōu)。2、List五種遍歷方式的性能測試及對比以下是性能測試代碼，會輸出不同數(shù)量級大小的ArrayList和LinkedList各種遍歷方式所花費的時間。ArrayList和Linked

5、List循環(huán)性能對比測試代碼PS:如果運行報異常 in thread “ main ” java .Ian g.OutOfMemoryError: Java heap space，請將 main函數(shù)里面list size 的大小減小。其中getArrayLists 函數(shù)會返回不同 size的ArrayList ,getLinkedLists函數(shù)會返回不同 size的 LinkedList。loopListCompare函數(shù)會分別用上面的遍歷方式1-5去遍歷每一個list數(shù)組（包含不同大小list）中的 list oprint開頭函數(shù)為輸出輔助函數(shù)。測試環(huán)境為 Windows7 32 位系統(tǒng) 3

6、.2G 雙核 CPU 4G 內(nèi)存，Java 7 , Eclipse -Xms512m -Xmx512m最終測試結果如下：list size| 10,000 |100,000| 1,000,000| 10,000,000for each| 1 ms|3 ms|14 ms| 152 msfor iterator| 0 ms|1 ms|12 ms| 114 msfor list.size()|1 ms|1 ms |13 ms|128 ms2 3456789for size = list.size() | 0 ms |0 ms |6ms|62 ms1 1 for j-|0 ms |1 ms |6 ms

7、 |63 ms1 21 compare loop performance of LinkedList2 1 list size|100| 1,000| 10,000|100,0003 1 for each| 0 ms |1 ms |1 ms |2 ms4 1 for iterator| 0 ms |0 ms |0 ms |2 ms5 1 for list.size() |0 ms |1 ms |73 ms | 7972 ms6 1 for size = list.size() | 0 ms |0 ms |67 ms | 8216 ms7 1 for j-|0 ms |1 ms |67 ms |

8、 8277 ms8 20212223242526272829第一張表為ArrayList對比結果，第二張表為LinkedList 對比結果。表橫向為同一遍歷方式不同大小list遍歷的時間消耗，縱向為同一 list不同遍歷方式遍歷的時間消耗。PS:由于首次遍歷 List會稍微多耗時一點，for each的結果稍微有點偏差，將測試代碼中的幾個Type順序調(diào)換會發(fā)現(xiàn)，for each 耗時和for iterator 接近。3、遍歷方式性能測試結果分析(1) foreach 介紹foreach 是Java SE5.0引入的功能很強的循環(huán)結構，for (Integer j : list) 應讀作for

9、each int in list。for (In teger j : list)實現(xiàn)幾乎等價于Java1 lterator iterator = list.iterator();2 while(iterator.hasNext() 3 Integer j = iterator.next();4 下面的分析會將foreach和顯示調(diào)用集合迭代器兩種遍歷方式歸類為Iterator方式，其他三種稱為get方式遍歷。這時我們已經(jīng)發(fā)現(xiàn)foreach的一大好處，簡單一行實現(xiàn)了四行的功能，使得代碼簡潔美觀，另一大好處是相對于下標循環(huán)而言的，foreach不必關心下標初始值和終止值及越界等，所以不易出錯。Ef

10、fective-Java中推薦使用此種寫法遍歷，本文會驗證這個說法。使用foreach結構的類對象必須實現(xiàn)了Iterable 接口，Java的Collection繼承自此接口，List實現(xiàn)了 Collection，這個接口僅包含一個函數(shù)，源碼如下：Java23 import java.util.Iterator;4/*Implementingthis interface allows an objecttobe the target ofthe foreachstatement.param the type of elements returnedbythe iteratorsince 1.5

11、*/public interfaceIterable /* Returnsaniterator over aset of elementsoftype T.* returnan Iterator.*/lteratoriterator。;7181920iterator()用于返回一個Iterator，從foreach的等價實現(xiàn)中我們可以看至U,數(shù)得到Iterator，再通過Iterator的next()得到下一個元素,hasNext()會調(diào)用這個函判斷是否還有更多元素。Iterator 源碼如下:Java1 public interface Iterator 2 boolean hasNext(

12、);34 E next();55 void remove();6 (2) ArrayList遍歷方式結果分析2list size| 10,000 |100,000| 1,000,000| 10,000,000for each| 1 ms|3 ms|14 ms| 152 msfor iterator| 0 ms|1 ms|12 ms| 114 msfor list.size()|1 ms |1 ms |13 ms| 128 msfor size =list.size() | 0 ms|0 ms|6 ms|62 msfor j-|0 ms |1 ms |6 ms |63 ms56789101112

13、1compare loop performance of ArrayListPS:由于首次遍歷 List會稍微多耗時一點，for each的結果稍微有點偏差，將測試代碼中 的幾個Type順序調(diào)換會發(fā)現(xiàn)，for each 耗時和for iterator 接近。從上面我們可以看出：a. 在ArrayList大小為十萬之前，五種遍歷方式時間消耗幾乎一樣b. 在十萬以后，第四、五種遍歷方式快于前三種，get方式優(yōu)于Iterator方式，并且Java3d IMMfprivate class Itr implements Iterator int cursor; / index of next eleme

14、nt to return int lastRet = -1; / index of last element returned;-1 if no such int expectedModCount = modCount; public boolean hasNext() return cursor != size; 1SuppressWarnings(unchecked)0public E next() 1checkForComodification();1int i = cursor;1 if (i = size)2 throw new NoSuchElementException();1O

15、bject elementData= ArrayList.this.elementData; 3 if (i = elementData.length)1throw new ConcurrentModificationException();4 cursor = i + 1;1return (E) elementDatalastRet = i; 5 1 int size = list.size();2 for (int j = 0; j size; j+) 3 list.get(j);4 用臨時變量size取代list.size()性能更優(yōu)。我們看看ArrayList中迭代器Iterator和

16、get方法的實現(xiàn)Java6 17 public E get(int index) 1rangeCheck(index);81 return elementData(index);8 20212223242526272829只是多了幾個50ms左右，foreach 這種簡從中可以看出get和Iterator的next函數(shù)同樣通過直接定位數(shù)據(jù)獲取元素， 判斷而已。c .從上可以看出即便在千萬大小的ArrayList中，幾種遍歷方式相差也不過且在常用的十萬左右時間幾乎相等，考慮foreach的優(yōu)點，我們大可選用便方式進行遍歷。(3) Lin kedList遍歷方式結果分析compare loop p

17、erformance of LinkedListlist size| 100 |1,000 |10,000| 100,000for each| 0 ms|1 ms|1 ms|2 msfor iterator| 0 ms|0 ms|0 ms|2 msfor list.size()|0 ms |1 ms |73 ms| 7972 msfor size =list.size() | 0 ms|0 ms| 67ms| 8216for j-|0 ms |1 ms |67 ms| 8277 ms678910121ms11PS:由于首次遍歷 List會稍微多耗時一點，for each的結果稍微有點偏差，將測

18、試代碼中的幾個Type順序調(diào)換會發(fā)現(xiàn)，for each 耗時和for iterator 接近。從上面我們可以看出：a在LinkedList大小接近一萬時，get方式和Iterator方式就已經(jīng)差了差不多兩個數(shù)量級, 十萬時Iterator方式性能已經(jīng)遠勝于get方式。我們看看LinkedList中迭代器和get方法的實現(xiàn)Java1d I SM /1 private class ListItr implements Listlterator 23456789101112131415161718192021222324252627privateNode lastReturned=null;priv

19、ateNode next;privateint nextIndex;privateint 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 NoS

20、uchElementException();lastReturned = next; next = next.next; nextIndex+;return lastReturned.item;public E get(int index) checkElementIndex(index); return node(index).item;/*index.* Returns the (non-null) Node at the specified element */Node node(int index) / assert isElementIndex(index);if (index 1) Node x = first;for (int i = 0; i index; i+) x = x.next;return x; else Node x = last;index; i-)fo