Complexité temporelle des collections Java

1. Vue d'ensemble

Dans ce didacticiel, nous parlerons des performances de différentes collections de l'API Java Collection . Lorsque nous parlons de collections, nous pensons généralement aux structures de données List, Map et Set et à leurs implémentations communes.

Tout d'abord, nous examinerons les informations sur la complexité de Big-O pour les opérations courantes, puis nous montrerons les nombres réels de certaines opérations de collecte.

2. Complexité temporelle

Habituellement, lorsque nous parlons de complexité temporelle, nous nous référons à la notation Big-O . En termes simples, la notation décrit comment le temps d'exécution de l'algorithme augmente avec la taille de l'entrée.

Des articles utiles sont disponibles pour en savoir plus sur la théorie de la notation Big-O ou des exemples pratiques de Java.

3. Liste

Commençons par une simple liste - qui est une collection ordonnée.

Ici, nous allons jeter un œil à une vue d'ensemble des performances des implémentations ArrayList, LinkedList et CopyOnWriteArrayList .

3.1. Liste des tableaux

Le ArrayList en Java est soutenu par un tableau . Cela permet de comprendre la logique interne de sa mise en œuvre. Un guide plus complet pour ArrayList est disponible dans cet article.

Alors, concentrons-nous d'abord sur la complexité temporelle des opérations courantes, à un niveau élevé:

  • add () - prend O (1) temps
  • ajouter (indice, élément) - en moyenne en séries O (n) temps
  • get () - est toujours uneopération O (1) à temps constant
  • remove () - s'exécute en temps linéaire O (n) . Nous devons parcourir tout le tableau pour trouver l'élément pouvant être supprimé
  • indexOf () - s'exécute également en temps linéaire. Il parcourt le tableau interne et vérifie chaque élément un par un. La complexité temporelle de cette opération nécessite donc toujours O (n) temps
  • contains () - l'implémentation est basée sur indexOf () . Ainsiil sera également fonctionner en O (n) temps

3.2. CopyOnWriteArrayList

Cette implémentation de l' interface List est très utile lorsque vous travaillez avec des applications multithreads . C'est thread-safe et bien expliqué dans ce guide ici.

Voici la présentation de la notation Big-O des performances pour CopyOnWriteArrayList :

  • add () - dépend de la position que nous ajoutons de la valeur, donc la complexité est O (n)
  • get () - estune opération à temps constant O (1)
  • remove () - prend O (n) temps
  • contient () - de même, la complexité est O (n)

Comme nous pouvons le voir, l'utilisation de cette collection est très coûteuse en raison des caractéristiques de performance de la méthode add () .

3.3. LinkedList

LinkedList est une structure de données linéaire qui se compose de nœuds contenant un champ de données et une référence à un autre nœud . Pour plus defonctionnalités et de capacités LinkedList , consultez cet article ici.

Présentons l'estimation moyenne du temps dont nous avons besoin pour effectuer certaines opérations de base:

  • add () - prend en charge l'insertion à temps constant O (1) à n'importe quelle position
  • get () - la recherche d'un élément prend O (n) temps
  • remove () - la suppression d'un élément nécessite également l'opération O (1) , car nous fournissons la position de l'élément
  • contient () - a également unecomplexité temporelle O (n)

3.4. Préchauffage de la JVM

Maintenant, pour prouver la théorie, jouons avec des données réelles. Pour être plus précis, nous présenterons les résultats du test JMH (Java Microbenchmark Harness) des opérations de collecte les plus courantes .

Si vous n'êtes pas familier avec l'outil JMH, consultez ce guide utile.

Tout d'abord, nous présentons les principaux paramètres de nos tests de référence:

@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) @Warmup(iterations = 10) public class ArrayListBenchmark { }

Ensuite, nous définissons le nombre d'itérations de préchauffage sur 10 . De plus, nous souhaitons voir la durée moyenne de fonctionnement de nos résultats affichée en microsecondes.

3.5. Tests de référence

Il est maintenant temps d'exécuter nos tests de performances. Tout d'abord, nous commençons par la ArrayList :

@State(Scope.Thread) public static class MyState { List employeeList = new ArrayList(); long iterations = 100000; Employee employee = new Employee(100L, "Harry"); int employeeIndex = -1; @Setup(Level.Trial) public void setUp() { for (long i = 0; i < iterations; i++) { employeeList.add(new Employee(i, "John")); } employeeList.add(employee); employeeIndex = employeeList.indexOf(employee); } }

À l'intérieur de notre ArrayListBenchmark , nous ajoutons la classe State pour contenir les données initiales.

Ici, nous créons une ArrayList d' objets Employee . Ensuite, nous l'initialisons avec 100.000 éléments à l'intérieur de la méthode setUp () . Le @State indique que les @Benchmark essais ont accès aux variables déclarées en elle dans le même fil.

Enfin, il est temps d'ajouter les tests de référence pour les méthodes add (), contains (), indexOf (), remove () et get () :

@Benchmark public void testAdd(ArrayListBenchmark.MyState state) { state.employeeList.add(new Employee(state.iterations + 1, "John")); } @Benchmark public void testAddAt(ArrayListBenchmark.MyState state) { state.employeeList.add((int) (state.iterations), new Employee(state.iterations, "John")); } @Benchmark public boolean testContains(ArrayListBenchmark.MyState state) { return state.employeeList.contains(state.employee); } @Benchmark public int testIndexOf(ArrayListBenchmark.MyState state) { return state.employeeList.indexOf(state.employee); } @Benchmark public Employee testGet(ArrayListBenchmark.MyState state) { return state.employeeList.get(state.employeeIndex); } @Benchmark public boolean testRemove(ArrayListBenchmark.MyState state) { return state.employeeList.remove(state.employee); }

3.6. Résultats de test

Tous les résultats sont présentés en microsecondes:

Benchmark Mode Cnt Score Error ArrayListBenchmark.testAdd avgt 20 2.296 ± 0.007 ArrayListBenchmark.testAddAt avgt 20 101.092 ± 14.145 ArrayListBenchmark.testContains avgt 20 709.404 ± 64.331 ArrayListBenchmark.testGet avgt 20 0.007 ± 0.001 ArrayListBenchmark.testIndexOf avgt 20 717.158 ± 58.782 ArrayListBenchmark.testRemove avgt 20 624.856 ± 51.101

From the results we can learn, that testContains() and testIndexOf() methods run in approximately the same time. We can also clearly see the huge difference between the testAdd(), testGet() method scores from the rest of the results. Adding an element takes 2.296 microseconds and getting one is 0.007-microsecond operation.

While searching or removing an element roughly costs 700 microseconds. These numbers are the proof of the theoretical part, where we learned that add(), and get() has O(1) time complexity and the other methods are O(n). n=10.000 elements in our example.

Likewise, we can write the same tests for CopyOnWriteArrayList collection. All we need is to replace the ArrayList in employeeList with the CopyOnWriteArrayList instance.

Here are the results of the benchmark test:

Benchmark Mode Cnt Score Error CopyOnWriteBenchmark.testAdd avgt 20 652.189 ± 36.641 CopyOnWriteBenchmark.testAddAt avgt 20 897.258 ± 35.363 CopyOnWriteBenchmark.testContains avgt 20 537.098 ± 54.235 CopyOnWriteBenchmark.testGet avgt 20 0.006 ± 0.001 CopyOnWriteBenchmark.testIndexOf avgt 20 547.207 ± 48.904 CopyOnWriteBenchmark.testRemove avgt 20 648.162 ± 138.379

Here, again, the numbers confirm the theory. As we can see, testGet() on average runs in 0.006 ms which we can consider as O(1). Comparing to ArrayList, we also notice the significant difference between testAdd() method results. As we have here O(n) complexity for the add() method versus ArrayList's O(1).

We can clearly see the linear growth of the time, as performance numbers are 878.166 compared to 0.051.

Now, it's LinkedList time:

Benchmark Cnt Score Error testAdd 20 2.580 ± 0.003 testContains 20 1808.102 ± 68.155 testGet 20 1561.831 ± 70.876 testRemove 20 0.006 ± 0.001

We can see from the scores, that adding and removing elements in LinkedList are quite fast.

Furthermore, there's a significant performance gap between add/remove and get/contains operations.

4. Map

With the latest JDK versions, we're witnessing significant performance improvement for Map implementations, such as replacing the LinkedList with the balanced tree node structure in HashMap, LinkedHashMap internal implementations. This shortens the element lookup worst-case scenario from O(n) to O(log(n)) time during the HashMap collisions.

However, if we implement proper .equals() and .hashcode() methods collisions are unlikely.

To learn more about HashMap collisions check out this write-up. From the write-up, we can also learn, that storing and retrieving elements from the HashMap takes constant O(1) time.

4.1. Testing O(1) Operations

Let's show some actual numbers. First, for the HashMap:

Benchmark Mode Cnt Score Error HashMapBenchmark.testContainsKey avgt 20 0.009 ± 0.002 HashMapBenchmark.testGet avgt 20 0.011 ± 0.001 HashMapBenchmark.testPut avgt 20 0.019 ± 0.002 HashMapBenchmark.testRemove avgt 20 0.010 ± 0.001

As we see, the numbers prove the O(1) constant time for running the methods listed above. Now, let's do a comparison of the HashMap test scores with the other Map instance scores.

For all of the listed methods, we have O(1) for HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap and ConcurrentHashMap.

Let's present the results of the remaining test scores in form of one table:

Benchmark LinkedHashMap IdentityHashMap WeakHashMap ConcurrentHashMap testContainsKey 0.008 0.009 0.014 0.011 testGet 0.011 0.109 0.019 0.012 testPut 0.020 0.013 0.020 0.031 testRemove 0.011 0.115 0.021 0.019

From the output numbers, we can confirm the claims of O(1) time complexity.

4.2. Testing O(log(n)) Operations

For the tree structure TreeMap and ConcurrentSkipListMap the put(), get(), remove(), containsKey() operations time is O(log(n)).

Here, we want to make sure that our performance tests will run approximately in logarithmic time. For that reason, we initialize the maps with n=1000, 10,000, 100,000, 1,000,000 items continuously.

In this case, we're interested in the total time of execution:

items count (n) 1000 10,000 100,000 1,000,000 all tests total score 00:03:17 00:03:17 00:03:30 00:05:27 

When n=1000 we have the total of 00:03:17 milliseconds execution time. n=10,000 the time is almost unchanged 00:03:18 ms. n=100,000 has minor increase 00:03:30. And finally, when n=1,000,000 the run completes in 00:05:27 ms.

After comparing the runtime numbers with the log(n) function of each n, we can confirm that the correlation of both functions matches.

5. Set

Generally, Set is a collection of unique elements. Here, we're going to examine the HashSet, LinkedHashSet, EnumSet, TreeSet, CopyOnWriteArraySet, and ConcurrentSkipListSet implementations of the Set interface.

To better understand the internals of the HashSet, this guide is here to help.

Now, let's jump ahead to present the time complexity numbers. For HashSet, LinkedHashSet, and EnumSet the add(), remove() and contains() operations cost constant O(1) time. Thanks to the internal HashMap implementation.

Likewise, the TreeSet has O(log(n)) time complexity for the operations listed for the previous group. That's because of the TreeMap implementation. The time complexity for ConcurrentSkipListSet is also O(log(n)) time, as it is based in skip list data structure.

For CopyOnWriteArraySet, the add(), remove() and contains() methods have O(n) average time complexity.

5.1. Test Methods

Now, let's jump to our benchmark tests:

@Benchmark public boolean testAdd(SetBenchMark.MyState state) { return state.employeeSet.add(state.employee); } @Benchmark public Boolean testContains(SetBenchMark.MyState state) { return state.employeeSet.contains(state.employee); } @Benchmark public boolean testRemove(SetBenchMark.MyState state) { return state.employeeSet.remove(state.employee); }

Furthermore, we leave the remaining benchmark configurations as they are.

5.2. Comparing the Numbers

Let's see the behavior of the runtime execution score for HashSet and LinkedHashSet having n = 1000; 10,000; 100,000 items.

For the HashSet, the numbers are:

Benchmark 1000 10,000 100,000 .add() 0.026 0.023 0.024 .remove() 0.009 0.009 0.009 .contains() 0.009 0.009 0.010

Similarly, the results for LinkedHashSet are:

Benchmark 1000 10,000 100,000 .add() 0.022 0.026 0.027 .remove() 0.008 0.012 0.009 .contains() 0.008 0.013 0.009

Comme on le voit, les scores restent quasiment les mêmes pour chaque opération. Encore plus, lorsque nous les comparons avec les sorties de test HashMap , elles se ressemblent également.

En conséquence, nous confirmons que toutes les méthodes testées fonctionnent en temps constant O (1) .

6. Conclusion

Dans cet article, nous présentons la complexité temporelle des implémentations les plus courantes des structures de données Java.

Séparément, nous montrons les performances d'exécution réelles de chaque type de collection via les tests de référence JVM. Nous avons également comparé les performances des mêmes opérations dans différentes collections. En conséquence, nous apprenons à choisir la bonne collection qui correspond à nos besoins.

Comme d'habitude, le code complet de cet article est disponible à l'adresse over sur GitHub.