有效地迭代地圖條目

本節提供了十個獨特示例實現的程式碼和基準,這些實現迭代 Map<Integer, Integer> 的條目並生成 Integer 值的總和。所有這些示例都具有Θ(n) 的演算法複雜性,但是,基準測試仍然有助於深入瞭解哪些實現在真實世界環境中更有效。

  1. 使用 IteratorMap.Entry 實現
    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry<Integer, Integer> pair = it.next();
        sum += pair.getKey() + pair.getValue();
    }
  1. 使用 forMap.Entry 實現
    for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
        sum += pair.getKey() + pair.getValue();
    }
  1. 使用 Map.forEach (Java 8+)實現
    map.forEach((k, v) -> sum[0] += k + v);
  1. 使用 Map.keySetfor 實現
    for (Integer key : map.keySet()) {
        sum += key + map.get(key);
    }
  1. 使用 Map.keySetIterator 實現
    Iterator<Integer> it = map.keySet().iterator();
    while (it.hasNext()) {
        Integer key = it.next();
        sum += key + map.get(key);
    }
  1. 使用 forIteratorMap.Entry 實現
    for (Iterator<Map.Entry<Integer, Integer>> entries = 
             map.entrySet().iterator(); entries.hasNext(); ) {
        Map.Entry<Integer, Integer> entry = entries.next();
        sum += entry.getKey() + entry.getValue();
    }
  1. 使用 Stream.forEach (Java 8+)實現
    map.entrySet().stream().forEach(e -> sum += e.getKey() + e.getValue());
  1. 使用 Stream.forEachStream.parallel (Java 8+)實現
    map.entrySet()
       .stream()
       .parallel()
       .forEach(e -> sum += e.getKey() + e.getValue());
  1. 使用實施 IterableMapApache 的集合
    MapIterator<Integer, Integer> mit = iterableMap.mapIterator();
    while (mit.hasNext()) {
        sum += mit.next() + it.getValue();
    }
  1. 使用實施 MutableMapEclipse 的收藏
     mutableMap.forEachKeyValue((key, value) -> {
         sum += key + value;
     });

效能測試Github 上 提供的程式碼
測試環境:Windows 8.1 64 位,Intel i7-4790 3.60GHz,16 GB

  1. 10 次​​試驗的平均效能(100 種元素)最佳:308±21 ns / op

    Benchmark                           Score     Error  Units
    test3_UsingForEachAndJava8            308  ±     21  ns/op
    test10_UsingEclipseMutableMap         309  ±      9  ns/op
    test1_UsingWhileAndMapEntry           380  ±     14  ns/op
    test6_UsingForAndIterator             387  ±     16  ns/op
    test2_UsingForEachAndMapEntry         391  ±     23  ns/op
    test7_UsingJava8StreamAPI             510  ±     14  ns/op
    test9_UsingApacheIterableMap          524  ±      8  ns/op
    test4_UsingKeySetAndForEach           816  ±     26  ns/op
    test5_UsingKeySetAndIterator          863  ±     25  ns/op
    test8_UsingJava8StreamAPIParallel    5552  ±    185  ns/op
    
  2. 10 次​​試驗的平均效能(10000 種元素)最佳:37.606±0.790μs/ op

    Benchmark                           Score     Error  Units
    test10_UsingEclipseMutableMap       37606  ±    790  ns/op
    test3_UsingForEachAndJava8          50368  ±    887  ns/op
    test6_UsingForAndIterator           50332  ±    507  ns/op
    test2_UsingForEachAndMapEntry       51406  ±   1032  ns/op
    test1_UsingWhileAndMapEntry         52538  ±   2431  ns/op
    test7_UsingJava8StreamAPI           54464  ±    712  ns/op
    test4_UsingKeySetAndForEach         79016  ±  25345  ns/op
    test5_UsingKeySetAndIterator        91105  ±  10220  ns/op
    test8_UsingJava8StreamAPIParallel  112511  ±    365  ns/op
    test9_UsingApacheIterableMap       125714  ±   1935  ns/op
    
  3. 10 次​​試驗的平均效能(100000 個元素)最佳:1184.767±332.968μs/ op

    Benchmark                            Score       Error  Units
    test1_UsingWhileAndMapEntry       1184.767  ±  332.968  μs/op
    test10_UsingEclipseMutableMap     1191.735  ±  304.273  μs/op
    test2_UsingForEachAndMapEntry     1205.815  ±  366.043  μs/op
    test6_UsingForAndIterator         1206.873  ±  367.272  μs/op
    test8_UsingJava8StreamAPIParallel 1485.895  ±  233.143  μs/op
    test5_UsingKeySetAndIterator      1540.281  ±  357.497  μs/op
    test4_UsingKeySetAndForEach       1593.342  ±  294.417  μs/op
    test3_UsingForEachAndJava8        1666.296  ±  126.443  μs/op
    test7_UsingJava8StreamAPI         1706.676  ±  436.867  μs/op
    test9_UsingApacheIterableMap      3289.866  ± 1445.564  μs/op
    
  4. 與地圖大小相關的效能變化比較

StackOverflow 文件

       x: Size of Map
    f(x): Benchmark Score (μs/op)

                 100      600     1100     1600     2100
        ---------------------------------------------------
        10  |   0.333    1.631    2.752    5.937    8.024
         3  |   0.309    1.971    4.147    8.147   10.473
         6  |   0.372    2.190    4.470    8.322   10.531
         1  |   0.405    2.237    4.616    8.645   10.707
Tests    2  |   0.376    2.267    4.809    8.403   10.910
 f(x)    7  |   0.473    2.448    5.668    9.790   12.125
         9  |   0.565    2.830    5.952    13.22   16.965
         4  |   0.808    5.012    8.813    13.939  17.407
         5  |   0.81     5.104    8.533    14.064  17.422
         8  |   5.173   12.499   17.351    24.671  30.403