java遍歷機制性能的比較詳解

更新時間：2019年06月10日 09:36:07 作者：cartoony

這篇文章主要給大家介紹了關(guān)于java遍歷機制性能比較的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用java具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧

緣由

近段時間在寫leetcode的Lemonade Change時候，發(fā)現(xiàn)了for循環(huán)與forEach循環(huán)的耗時是不一致的，在提交記錄上面差了一倍......

平常開發(fā)絕大部分業(yè)務(wù)邏輯的實現(xiàn)都需要遍歷機制的幫忙，雖說也有注意到各數(shù)據(jù)結(jié)構(gòu)操作的性能比較，但是忽視了遍歷機制性能的差異。原本前兩天就開始動手寫，拖延癥......

正文

現(xiàn)階段我所知道JAVA遍歷機制有三種

for循環(huán)
forEach循環(huán)
Iterator循環(huán)

JAVA數(shù)據(jù)結(jié)構(gòu)千千萬，但是大部分都是對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的封裝，比較HashMap依賴于Node數(shù)組，LinkedList底層是鏈表，ArrayList對數(shù)組的再封裝......扯遠了

總結(jié)來說，JAVA的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，我覺得有兩種

數(shù)組
鏈表

如果是加上Hash(Hash的操作與數(shù)組以及鏈表不太一致)，就是三種

因為平常開發(fā)大部分都優(yōu)先選擇包裝后的數(shù)據(jù)結(jié)構(gòu)，所以下面我會使用

ArrayList(包裝后的數(shù)組)
LinkedList(包裝后的鏈表)
HashSet(包裝后的Hash類型數(shù)組)

這三種數(shù)據(jù)結(jié)構(gòu)在遍歷機制不同的時候時間的差異

可能有人對我為什么不對比HashMap呢，因為JAVA設(shè)計中，是先實現(xiàn)了Map，再實現(xiàn)Set。如果你有閱讀過源碼就會發(fā)現(xiàn):每個Set子類的實現(xiàn)中，都有一個序列化后的Map對應(yīng)屬性實現(xiàn)，而因為Hash的查找時間復(fù)雜度為O(1)，得出key后查找value的時間大致是一致的，所以我不對比HashMap。

題外話

我在閱讀《瘋狂JAVA》讀到:JAVA的設(shè)計者將Map的內(nèi)部entry數(shù)組中的value設(shè)為null進而實現(xiàn)了Set。因為我是以源碼以及官方文檔為準(zhǔn)，具體我不清楚正確與否，但是因為Hash中的key互不相同，Set中元素也互不相同，所以我認(rèn)為這個觀點是正確的。

為了測試的公平性，我會采取以下的限定

每種數(shù)據(jù)結(jié)構(gòu)的大小都設(shè)置三種量級

10
100
1000

元素都采用隨機數(shù)生成

遍歷進行操作都為輸出當(dāng)前元素的值

注:時間開銷受本地環(huán)境的影響，可能測量值會出現(xiàn)變化，但是總體上比例是正確的

ArrayList的比較

代碼

public class TextArray {

  private static Random random;

  private static List<Integer> list1;

  private static List<Integer> list2;

  private static List<Integer> list3;

  public static void execute(){
    random=new Random();
    initArray();
    testForWith10Object();
    testForEachWith10Object();
    testIteratorWith10Object();
    testForWith100Object();
    testForEachWith100Object();
    testIteratorWith100Object();
    testForWith1000Object();
    testForEachWith1000Object();
    testIteratorWith1000Object();
  }

  private static void testForWith10Object(){
    printFor(list1);
  }

  private static void testForWith100Object(){
    printFor(list2);
  }

  private static void testForWith1000Object(){
    printFor(list3);
  }

  private static void testForEachWith10Object(){
    printForeach(list1);
  }

  private static void testForEachWith100Object(){
    printForeach(list2);
  }

  private static void testForEachWith1000Object(){
    printForeach(list3);
  }

  private static void testIteratorWith10Object() {
    printIterator(list1);
  }

  private static void testIteratorWith100Object() {
    printIterator(list2);
  }

  private static void testIteratorWith1000Object() {
    printIterator(list3);
  }

  private static void printFor(List<Integer> list){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int i=0,length=list.size();i<length;i++){
      System.out.print(list.get(i)+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("for for "+list.size()+":"+(end-start)+"ms");
  }

  private static void printForeach(List<Integer> list){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int temp:list){
      System.out.print(temp+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("foreach for "+list.size()+":"+(end-start)+"ms");
  }

  private static void printIterator(List<Integer> list){
    System.out.println();
    System.out.print("data:");
    Iterator<Integer> it=list.iterator();
    long start=System.currentTimeMillis();
    while(it.hasNext()){
      System.out.print(it.next()+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("iterator for "+list.size()+":"+(end-start)+"ms");
  }

  private static void initArray(){
    list1=new ArrayList<>();
    list2=new ArrayList<>();
    list3=new ArrayList<>();
    for(int i=0;i<10;i++){
      list1.add(random.nextInt());
    }
    for(int i=0;i<100;i++){
      list2.add(random.nextInt());
    }
    for(int i=0;i<1000;i++){
      list3.add(random.nextInt());
    }
  }
}

輸出(忽略對元素的輸出)

for for 10:1ms
foreach for 10:0ms
iterator for 10:2ms

for for 100:5ms
foreach for 100:4ms
iterator for 100:12ms

for for 1000:33ms
foreach for 1000:7ms
iterator for 1000:16ms

	10	100	1000
for	1ms	5ms	33ms
forEach	0ms	4ms	7ms
Iterator	2ms	12ms	16ms

結(jié)論

for的性能最不穩(wěn)定，foreach次之，Iterator最好

使用建議

在數(shù)據(jù)量不明確的情況下(可能1w,10w或其他)，建議使用Iterator進行遍歷
在數(shù)據(jù)量明確且量級小的時候，優(yōu)先使用foreach
需要使用索引時，使用遞增變量的開銷比for的要小

LinkedList的比較

代碼

public class TextLinkedList {

  private static Random random;

  private static List<Integer> list1;

  private static List<Integer> list2;

  private static List<Integer> list3;

  public static void execute(){
    random=new Random();
    initList();
    testForWith10Object();
    testForEachWith10Object();
    testIteratorWith10Object();
    testForWith100Object();
    testForEachWith100Object();
    testIteratorWith100Object();
    testForWith1000Object();
    testForEachWith1000Object();
    testIteratorWith1000Object();
  }

  private static void testForWith10Object() {
    printFor(list1);
  }

  private static void testForEachWith10Object() {
    printForeach(list1);
  }

  private static void testIteratorWith10Object() {
    printIterator(list1);
  }

  private static void testForWith100Object() {
    printFor(list2);
  }

  private static void testForEachWith100Object() {
    printForeach(list2);
  }

  private static void testIteratorWith100Object() {
    printIterator(list2);
  }

  private static void testForWith1000Object() {
    printFor(list3);
  }

  private static void testForEachWith1000Object() {
    printForeach(list3);
  }

  private static void testIteratorWith1000Object() {
    printIterator(list3);
  }

  private static void printFor(List<Integer> list){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int i=0,size=list.size();i<size;i++){
      System.out.print(list.get(i));
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("for for "+list.size()+":"+(end-start)+"ms");
  }

  private static void printForeach(List<Integer> list){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int temp:list){
      System.out.print(temp+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("foreach for "+list.size()+":"+(end-start)+"ms");
  }

  private static void printIterator(List<Integer> list){
    System.out.println();
    System.out.print("data:");
    Iterator<Integer> it=list.iterator();
    long start=System.currentTimeMillis();
    while(it.hasNext()){
      System.out.print(it.next()+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("iterator for "+list.size()+":"+(end-start)+"ms");
  }


  private static void initList() {
    list1=new LinkedList<>();
    list2=new LinkedList<>();
    list3=new LinkedList<>();
    for(int i=0;i<10;i++){
      list1.add(random.nextInt());
    }
    for(int i=0;i<100;i++){
      list2.add(random.nextInt());
    }
    for(int i=0;i<1000;i++){
      list3.add(random.nextInt());
    }
  }
}

輸出(忽略對元素的輸出)

for for 10:0ms
foreach for 10:1ms
iterator for 10:0ms

for for 100:1ms
foreach for 100:0ms
iterator for 100:3ms

for for 1000:23ms
foreach for 1000:25ms
iterator for 1000:4ms

	10	100	1000
for	0ms	1ms	23ms
forEach	1ms	0ms	25ms
Iterator	0ms	3ms	4ms

結(jié)論

foreach的性能最不穩(wěn)定，for次之，Iterator最好

使用建議

盡量使用Iterator進行遍歷
需要使用索引時，使用遞增變量的開銷比for的要小

HashSet的比較

注：因Hash遍歷算法與其他類型不一致，所以取消了for循環(huán)的比較

代碼

public class TextHash {

  private static Random random;

  private static Set<Integer> set1;

  private static Set<Integer> set2;

  private static Set<Integer> set3;

  public static void execute(){
    random=new Random();
    initHash();
    testIteratorWith10Object();
    testForEachWith10Object();
    testIteratorWith100Object();
    testForEachWith100Object();
    testIteratorWith1000Object();
    testForEachWith1000Object();
  }

  private static void testIteratorWith10Object() {
    printIterator(set1);
  }

  private static void testForEachWith10Object() {
    printForeach(set1);
  }

  private static void testIteratorWith100Object() {
    printIterator(set2);
  }

  private static void testForEachWith100Object() {
    printForeach(set2);
  }

  private static void testIteratorWith1000Object() {
    printIterator(set3);
  }

  private static void testForEachWith1000Object() {
    printForeach(set3);
  }

  private static void initHash() {
    set1=new HashSet<>();
    set2=new HashSet<>();
    set3=new HashSet<>();
    for(int i=0;i<10;i++){
      set1.add(random.nextInt());
    }
    for(int i=0;i<100;i++){
      set2.add(random.nextInt());
    }
    for(int i=0;i<1000;i++){
      set3.add(random.nextInt());
    }
  }

  private static void printIterator(Set<Integer> data){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    Iterator<Integer> it=data.iterator();
    while (it.hasNext()){
      System.out.print(it.next()+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("iterator for "+data.size()+":"+(end-start)+"ms");
  }

  private static void printForeach(Set<Integer> data){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int temp:data){
      System.out.print(temp+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("foreach for "+data.size()+":"+(end-start)+"ms");
  }
}

輸出(忽略對元素的輸出)

iterator for 10:0ms
foreach for 10:0ms

iterator for 100:6ms
foreach for 100:0ms

iterator for 1000:30ms
foreach for 1000:9ms

	10	100	1000
foreach	0ms	0ms	9ms
Iterator	0ms	6ms	30ms

結(jié)論

foreach性能遙遙領(lǐng)先于Iterator

使用建議

以后就選foreach了，性能好，寫起來也方便。

總結(jié)

for循環(huán)性能在三者的對比中總體落于下風(fēng)，而且開銷遞增幅度較大。以后即使在需要使用索引時我寧愿使用遞增變量也不會使用for了。
Iterator的性能在數(shù)組以及鏈表的表現(xiàn)都是最好的，應(yīng)該是JAVA的設(shè)計者優(yōu)化過了。在響應(yīng)時間敏感的情況下(例如web響應(yīng))，優(yōu)先考慮。
foreach的性能屬于兩者之間，寫法簡單，時間不敏感的情況下我會盡量選用。

以上就是我對常見數(shù)據(jù)結(jié)構(gòu)遍歷機制的一點比較，雖然只是很初步，但是從中我也學(xué)到了很多東西，希望你們也有所收獲。

好了，以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，謝謝大家對腳本之家的支持。

您可能感興趣的文章: