Complejidad temporal de las colecciones de Java

Programación

1. Información general

En este tutorial, hablaremos sobre el rendimiento de diferentes colecciones de la API de colección de Java . Cuando hablamos de colecciones, normalmente pensamos en las estructuras de datos List, Map y Set y sus implementaciones comunes.

En primer lugar, analizaremos los conocimientos de complejidad de Big-O para operaciones comunes y, después, mostraremos los números reales de algunas operaciones de recolección en tiempo de ejecución.

2. Complejidad del tiempo

Por lo general, cuando hablamos de complejidad temporal, nos referimos a la notación Big-O . En pocas palabras, la notación describe cómo el tiempo para realizar el algoritmo crece con el tamaño de la entrada.

Hay escritos útiles disponibles para aprender más sobre la teoría de notación Big-O o ejemplos prácticos de Java.

3. Lista

Comencemos con una lista simple, que es una colección ordenada.

Aquí, veremos una descripción general del rendimiento de las implementaciones ArrayList, LinkedList y CopyOnWriteArrayList .

3.1. Lista de arreglo

El ArrayList en Java está respaldado por una matriz . Esto ayuda a comprender la lógica interna de su implementación. En este artículo hay disponible una guía más completa para ArrayList .

Entonces, centrémonos primero en la complejidad temporal de las operaciones comunes, a un alto nivel:

  • add () - toma O (1) tiempo
  • añadir (índice, elemento) - en carreras medio en O (n) tiempo
  • get () - es siempre unaoperación detiempo constante O (1)
  • remove () : se ejecuta en tiempo lineal O (n) . Tenemos que iterar toda la matriz para encontrar el elemento que califica para su eliminación
  • indexOf () : también se ejecuta en tiempo lineal. Repite la matriz interna y verifica cada elemento uno por uno. Entonces, la complejidad del tiempo para esta operación siempre requiere O (n) tiempo
  • contiene () : la implementación se basa en indexOf () . Por lo que también se ejecutará en O (n) tiempo

3.2. CopyOnWriteArrayList

Esta implementación de la interfaz List es muy útil cuando se trabaja con aplicaciones multiproceso . Es seguro para subprocesos y se explica bien en esta guía aquí.

Aquí está la descripción general de la notación Big-O de rendimiento para CopyOnWriteArrayList :

  • add () - depende de la posición en la que agregamos valor, por lo que la complejidad es O (n)
  • get () - es O (1) operación de tiempo constante
  • remove () - toma O (n) tiempo
  • contiene () - del mismo modo, la complejidad es O (n)

Como podemos ver, usar esta colección es muy costoso debido a las características de rendimiento del método add () .

3.3. Lista enlazada

LinkedList es una estructura de datos lineal que consta de nodos que contienen un campo de datos y una referencia a otro nodo . Para obtener máscaracterísticas y capacidades de LinkedList , consulte este artículo aquí.

Presentamos la estimación promedio del tiempo que necesitamos para realizar algunas operaciones básicas:

  • add () : admite lainserción de tiempo constante O (1) en cualquier posición
  • get () - buscar un elemento lleva O (n) tiempo
  • remove () : eliminar un elemento también requiere laoperación O (1) , ya que proporcionamos la posición del elemento
  • contiene () - también tienecomplejidad de tiempo O (n)

3.4. Calentando la JVM

Ahora, para probar la teoría, juguemos con datos reales. Para ser más precisos, presentaremos los resultados de la prueba JMH (Java Microbenchmark Harness) de las operaciones de recolección más comunes .

En caso de que no esté familiarizado con la herramienta JMH, consulte esta guía útil.

Primero, presentamos los principales parámetros de nuestras pruebas comparativas:

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

Luego, establecemos el número de iteraciones de calentamiento en 10 . Además, deseamos ver el tiempo de ejecución promedio de nuestros resultados en microsegundos.

3.5. Pruebas comparativas

Ahora es el momento de ejecutar nuestras pruebas de rendimiento. Primero, comenzamos con 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); } }

Dentro de nuestro ArrayListBenchmark , agregamos la clase State para contener los datos iniciales.

Aquí, creamos una ArrayList de objetos Employee . Después, lo inicializamos con 100.000 elementos dentro del método setUp () . El @State indica que las pruebas de @Benchmark tienen acceso completo a las variables declaradas en él dentro del mismo hilo.

Finalmente, es hora de agregar las pruebas comparativas para los métodos add (), contains (), indexOf (), remove () y 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. Resultados de la prueba

Todos los resultados se presentan en microsegundos:

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

Como vemos, las puntuaciones siguen siendo casi las mismas para cada operación. Aún más, cuando los comparamos con los resultados de la prueba HashMap , también se ven iguales.

Como resultado, confirmamos que todos los métodos probados se ejecutan en un tiempo constante O (1) .

6. Conclusión

En este artículo, presentamos la complejidad temporal de las implementaciones más comunes de las estructuras de datos de Java.

Por separado, mostramos el rendimiento real en tiempo de ejecución de cada tipo de colección a través de las pruebas de referencia de JVM. También hemos comparado el desempeño de las mismas operaciones en diferentes colecciones. Como resultado, aprendemos a elegir la colección adecuada que se adapte a nuestras necesidades.

Como de costumbre, el código completo de este artículo está disponible en GitHub.