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

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

2、文后面進(jìn)行分析給出 結(jié)論。(1) for each 循環(huán)Java1川乳專律勢(shì)魏幣船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) 下標(biāo)遞增循環(huán)，終止條件為每次調(diào)用size()函數(shù)比較判斷Java1 I 滝勰當(dāng)聰 /1 List list = new ArrayList();2 for (int j = 0; j list.size(); j+)3 list.get(j);4 (4) 下標(biāo)遞增循環(huán)，終止條件為和等于 size()的臨時(shí)變量比較判斷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) 下標(biāo)遞減循環(huán)Javad 1幕J1 List list = new ArrayList();2 for (int j = list.size() - 1; j = 0; j-) 3 list.get(j);4 在測(cè)試前大家可以根據(jù)對(duì)ArrayList和LinkedList數(shù)據(jù)結(jié)構(gòu)及Iterator的了解，想想上面五種遍歷方式哪個(gè)性能更優(yōu)。2、List五種遍歷方式的性能測(cè)試及對(duì)比以下是性能測(cè)試代碼，會(huì)輸出不同數(shù)量級(jí)大小的ArrayList和LinkedList各種遍歷方式所花費(fèi)的時(shí)間。ArrayList和Linked

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

6、.2G 雙核 CPU 4G 內(nèi)存，Java 7 , Eclipse -Xms512m -Xmx512m最終測(cè)試結(jié)果如下：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對(duì)比結(jié)果，第二張表為L(zhǎng)inkedList 對(duì)比結(jié)果。表橫向?yàn)橥槐闅v方式不同大小list遍歷的時(shí)間消耗，縱向?yàn)橥?list不同遍歷方式遍歷的時(shí)間消耗。PS:由于首次遍歷 List會(huì)稍微多耗時(shí)一點(diǎn)，for each的結(jié)果稍微有點(diǎn)偏差，將測(cè)試代碼中的幾個(gè)Type順序調(diào)換會(huì)發(fā)現(xiàn)，for each 耗時(shí)和for iterator 接近。3、遍歷方式性能測(cè)試結(jié)果分析(1) foreach 介紹foreach 是Java SE5.0引入的功能很強(qiáng)的循環(huán)結(jié)構(gòu)，for (Integer j : list) 應(yīng)讀作for

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

10、fective-Java中推薦使用此種寫法遍歷，本文會(huì)驗(yàn)證這個(gè)說法。使用foreach結(jié)構(gòu)的類對(duì)象必須實(shí)現(xiàn)了Iterable 接口，Java的Collection繼承自此接口，List實(shí)現(xiàn)了 Collection，這個(gè)接口僅包含一個(gè)函數(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()用于返回一個(gè)Iterator，從foreach的等價(jià)實(shí)現(xiàn)中我們可以看至U,數(shù)得到Iterator，再通過Iterator的next()得到下一個(gè)元素,hasNext()會(huì)調(diào)用這個(gè)函判斷是否還有更多元素。Iterator 源碼如下:Java1 public interface Iterator 2 boolean hasNext(

12、);34 E next();55 void remove();6 (2) ArrayList遍歷方式結(jié)果分析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會(huì)稍微多耗時(shí)一點(diǎn)，for each的結(jié)果稍微有點(diǎn)偏差，將測(cè)試代碼中 的幾個(gè)Type順序調(diào)換會(huì)發(fā)現(xiàn)，for each 耗時(shí)和for iterator 接近。從上面我們可以看出：a. 在ArrayList大小為十萬之前，五種遍歷方式時(shí)間消耗幾乎一樣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 用臨時(shí)變量size取代list.size()性能更優(yōu)。我們看看ArrayList中迭代器Iterator和

16、get方法的實(shí)現(xiàn)Java6 17 public E get(int index) 1rangeCheck(index);81 return elementData(index);8 20212223242526272829只是多了幾個(gè)50ms左右，foreach 這種簡(jiǎn)從中可以看出get和Iterator的next函數(shù)同樣通過直接定位數(shù)據(jù)獲取元素， 判斷而已。c .從上可以看出即便在千萬大小的ArrayList中，幾種遍歷方式相差也不過且在常用的十萬左右時(shí)間幾乎相等，考慮foreach的優(yōu)點(diǎn)，我們大可選用便方式進(jìn)行遍歷。(3) Lin kedList遍歷方式結(jié)果分析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會(huì)稍微多耗時(shí)一點(diǎn)，for each的結(jié)果稍微有點(diǎn)偏差，將測(cè)

18、試代碼中的幾個(gè)Type順序調(diào)換會(huì)發(fā)現(xiàn)，for each 耗時(shí)和for iterator 接近。從上面我們可以看出：a在LinkedList大小接近一萬時(shí)，get方式和Iterator方式就已經(jīng)差了差不多兩個(gè)數(shù)量級(jí), 十萬時(shí)Iterator方式性能已經(jīng)遠(yuǎn)勝于get方式。我們看看LinkedList中迭代器和get方法的實(shí)現(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