Java Language Itérer efficacement les entrées de carte


Exemple

Cette section fournit des codes et des tests d'évaluation pour dix implémentations d'exemples uniques qui parcourent les entrées d'une Map<Integer, Integer> et génèrent la somme des valeurs Integer . Tous les exemples ont une complexité algorithmique de Θ(n) , cependant, les tests de performances sont toujours utiles pour fournir des informations sur les implémentations les plus efficaces dans un environnement "réel".

  1. Implémentation utilisant Iterator avec Map.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. Implémentation à l'aide for avec Map.Entry
    for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
        sum += pair.getKey() + pair.getValue();
    }
  1. Implémentation à l'aide de Map.forEach (Java 8+)
    map.forEach((k, v) -> sum[0] += k + v);
  1. Implémentation à l'aide de Map.keySet avec for
    for (Integer key : map.keySet()) {
        sum += key + map.get(key);
    }
  1. Implémentation à l'aide de Map.keySet avec Iterator
    Iterator<Integer> it = map.keySet().iterator();
    while (it.hasNext()) {
        Integer key = it.next();
        sum += key + map.get(key);
    }
  1. Implémentation utilisant for avec Iterator et Map.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. Implémentation à l'aide de Stream.forEach (Java 8+)
    map.entrySet().stream().forEach(e -> sum += e.getKey() + e.getValue());
  1. Implémentation à l'aide de Stream.forEach avec Stream.parallel (Java 8+)
    map.entrySet()
       .stream()
       .parallel()
       .forEach(e -> sum += e.getKey() + e.getValue());
  1. Implémentation à l'aide d' IterableMap des collections Apache
    MapIterator<Integer, Integer> mit = iterableMap.mapIterator();
    while (mit.hasNext()) {
        sum += mit.next() + it.getValue();
    }
  1. Implémentation à l'aide de MutableMap des collections Eclipse
     mutableMap.forEachKeyValue((key, value) -> {
         sum += key + value;
     });

Tests de performance ( code disponible sur Github )
Environnement de test: Windows 8.1 64 bits, Intel i7-4790 3,60 GHz, 16 Go

  1. Performance moyenne de 10 essais (100 éléments) Meilleur: 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. Performance moyenne de 10 essais (10000 éléments) Meilleur: 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. Rendement moyen de 10 essais (100 000 éléments) Meilleur: 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. Une comparaison des variations de performance en fonction de la taille de la carte

Graphique des tests de performance

       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