歡迎光臨
每天分享高質量文章

高效遍歷 Java 容器

(點選上方公眾號,可快速關註)


來源:ImportNew – yizhe ,

透過本文,你可以更深入的學習 Java 語言中 forEach 語法的知識,以及它和 C 語言形式的 for 迴圈、 Steam API 的對比。

簡介

Java 程式員經常使用容器,比如 ArrayList 和 HashSet。Java 8 中的 lambda 語法和 steaming API 可以讓我們更方便的使用容器。大部分情況下,我們僅僅處理幾千個元素,也不會去考慮效能問題。但是,在一些極端場景下,如果我們需要遍歷上百萬個元素,效能問題就凸顯出來了。

本文將採用 JMH 計算每塊程式碼的執行時間。

forEach vs. C Style vs. Stream API

遍歷是一個基本的功能。所有程式語言都提供了簡單的語法,讓程式員去遍歷容器。Steam API 以一種非常直接的形式來遍歷容器。

public List streamSingleThread(BenchMarkState state){

    List result = new ArrayList<>(state.testData.size());

    state.testData.stream().forEach(item -> {

        result.add(item);

    });

    return result;

}

public List streamMultiThread(BenchMarkState state){

    List result = new ArrayList<>(state.testData.size());

    state.testData.stream().parallel().forEach(item -> {

        result.add(item);

    });

    return result;

}

forEach 迴圈也很簡單:

public List forEach(BenchMarkState state){

  List result = new ArrayList<>(state.testData.size());

  for(Integer item : state.testData){

    result.add(item);

  }

  return result;

}

C 語言形式的 for 迴圈囉嗦一些,不過依然很緊湊:

public List forCStyle(BenchMarkState state){

  int size = state.testData.size();

  List result = new ArrayList<>(size);

  for(int j = 0; j < size; j ++){

    result.add(state.testData.get(j));

  }

  return result;

}

以下是效能報告:

Benchmark                               Mode  Cnt   Score   Error  Units

TestLoopPerformance.forCStyle           avgt  200  18.068 ± 0.074  ms/op

TestLoopPerformance.forEach             avgt  200  30.566 ± 0.165  ms/op

TestLoopPerformance.streamMultiThread   avgt  200  79.433 ± 0.747  ms/op

TestLoopPerformance.streamSingleThread  avgt  200  37.779 ± 0.485  ms/op

使用 C 語言形式的 for 迴圈,JVM 每次僅僅增加一個數字,然後直接從記憶體裡讀出資料。這使得它非常迅速。但是 forEach 就大不一樣,根據 StackOverFlow 的這篇回答,和 Oracle 的文章,JVM 需要把 forEach 轉換成一個 iterator,然後每個元素都呼叫一次 hasNext() 方法。這就是 forEach 比 C 語言的形式慢一些的原因。

這篇回答

https://stackoverflow.com/questions/85190/how-does-the-java-for-each-loop-work/85206#85206

文章

https://docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html

哪一個是遍歷 Set 最高效的方法呢?

我們先定義測試資料集:

@State(Scope.Benchmark)

public static class BenchMarkState {

    @Setup(Level.Trial)

    public void doSetup() {

        for(int i = 0; i < 500000; i++){

            testData.add(Integer.valueOf(i));

        }

    }

    @TearDown(Level.Trial)

    public void doTearDown() {

        testData = new HashSet<>(500000);

    }

    public Set testData = new HashSet<>(500000);

}

Java 中的 Set 也支援 Steam API 和 forEach 迴圈。參考之前的測試,如果我們把 Set 轉換成 ArrayList,然後遍歷 ArrayList,或許效能會好一些?

public List forCStyle(BenchMarkState state){

    int size = state.testData.size();

    List result = new ArrayList<>(size);

    Integer[] temp = (Integer[]) state.testData.toArray(new Integer[size]);

    for(int j = 0; j < size; j ++){

        result.add(temp[j]);

    }

    return result;

}

如果把 iterator 和 C 語言形式結合起來呢?

public List forCStyleWithIteration(BenchMarkState state){

    int size = state.testData.size();

    List result = new ArrayList<>(size);

    Iterator iteration = state.testData.iterator();

        for(int j = 0; j < size; j ++){

            result.add(iteration.next());

        }

    return result;

}

或者,簡單的遍歷怎麼樣?

public List forEach(BenchMarkState state){

    List result = new ArrayList<>(state.testData.size());

    for(Integer item : state.testData) {

        result.add(item);

    }

    return result;

}

這個主意不錯,不過它的效率也不高,因為初始化一個新的 ArrayList 同樣需要消耗資源。

Benchmark                                   Mode  Cnt  Score   Error  Units

TestLoopPerformance.forCStyle               avgt  200  6.013 ± 0.108  ms/op

TestLoopPerformance.forCStyleWithIteration  avgt  200  4.281 ± 0.049  ms/op

TestLoopPerformance.forEach                 avgt  200  4.498 ± 0.026  ms/op

HashMap (使用 HashMap 的 HashSet) 不是為遍歷所有元素設計的。遍歷一個 HashMap 最快的方法是把 Iterator 和 C 語言形式結合起來,這樣 JVM 就不會去呼叫 hasNext()。

結論

Foreach 和 Steam API 用來處理集合是很方便的。你可以更快的寫程式碼。不過,如果你的系統很穩定,效能是一個主要的考量,你應該考慮一下重寫你的迴圈。

【關於投稿】


如果大家有原創好文投稿,請直接給公號傳送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章連結

② 示例:
【投稿】《不要自稱是程式員,我十多年的 IT 職場總結》:http://blog.jobbole.com/94148/

③ 最後請附上您的個人簡介哈~



看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,提升Java技能

贊(0)

分享創造快樂