java - ¿Por qué ArrayDeque es mejor que LinkedList?

linked-list (7)

Estoy tratando de entender por qué Java''s ArrayDeque es mejor que LinkedList de Java, ya que ambos implementan la interfaz Deque.

Apenas veo a alguien usando ArrayDeque en su código. Si alguien arroja más luz sobre cómo se implementa ArrayDeque, sería útil.

Si lo entiendo, estaré más seguro usándolo. No pude entender claramente la implementación de JDK en cuanto a la forma en que maneja las referencias de cabeza y cola.

Creo que el cuello de botella de rendimiento principal en LinkedList es el hecho de que cada vez que presionas hacia cualquier extremo del deque, detrás de la escena, la implementación asigna un nuevo nodo de lista enlazado, que esencialmente involucra JVM / OS, y eso es costoso. Además, cada vez que aparece desde cualquier lado, los nodos internos de LinkedList vuelven elegibles para la recolección de basura y eso es más trabajo detrás de la escena. Además, dado que los nodos de la lista vinculada se asignan aquí y allá, el uso de la memoria caché de la CPU no proporcionará muchos beneficios.

Si podría ser de interés, tengo una prueba de que al agregar un elemento a ArrayList o ArrayDeque ejecuta en tiempo constante amortizado; referirse a this

El acceso a un elemento en ArrayDeque siempre es más rápido en comparación con LinkedList con O (1) para acceder a los elementos. En la lista Vinculada, tomará O (N) para encontrar el último elemento.

ArrayDeque es eficiente desde el punto de vista de la memoria, ya que no es necesario realizar un seguimiento del siguiente nodo, a diferencia de la Lista vinculada.

Incluso según la documentación de Java, se ha citado que

ArrayDeque es una implementación de matriz de tamaño variable de la interfaz Deque. Deques de matriz no tienen restricciones de capacidad; crecen según sea necesario para apoyar el uso. No son seguros para subprocesos; en ausencia de sincronización externa, no admiten el acceso simultáneo por múltiples hilos. Los elementos nulos están prohibidos. Es probable que esta clase sea más rápida que Stack cuando se usa como una pila, y más rápida que LinkedList cuando se utiliza como una cola.

Benchmarking de estos dos demuestra que ArrayDeque es más rápido.

La complejidad del tiempo para ArrayDeque para acceder a un elemento es O (1) y para LinkList es O (N) para acceder al último elemento. ArrayDeque no es seguro para subprocesos, por lo que la sincronización manual es necesaria para que pueda acceder a ella a través de varios subprocesos y para que sean más rápidos.

Las estructuras vinculadas son posiblemente la peor estructura para iterar con una falta de caché en cada elemento. Además de eso, consumen mucho más memoria.

Si necesita agregar / eliminar ambos extremos, ArrayDeque es significativamente mejor que una lista vinculada. El acceso aleatorio de cada elemento también es O (1) para una cola cíclica.

La única operación mejor de una lista vinculada es eliminar el elemento actual durante la iteración.

Toda la gente que critica una LinkedList , piensa en cualquier otro tipo que haya usado List en Java, probablemente usa ArrayList y LinkedList mayoría de las veces porque han estado antes de Java 6 y porque esos son los que se enseñan como inicio en la mayoría de los libros .

Pero eso no significa que tomaría ciegamente el lado de LinkedList o ArrayDeque . Si desea saber, eche un vistazo al punto de referencia a continuación hecho por Brian .

La configuración de la prueba considera:

Cada objeto de prueba es una Cadena de 500 caracteres. Cada cadena es un objeto diferente en la memoria.
El tamaño de la matriz de prueba variará durante las pruebas.
Para cada combinación de tamaño de matriz / implementación de cola, se ejecutan 100 pruebas y se calcula el tiempo promedio por prueba.
Cada prueba consiste en llenar cada cola con todos los objetos y luego eliminarlos.
Mida el tiempo en términos de milisegundos.

Resultado de la prueba:

Por debajo de 10.000 elementos, tanto las pruebas LinkedList como ArrayDeque promediaron a un nivel inferior a 1 ms.
A medida que los conjuntos de datos se hacen más grandes, las diferencias entre los tiempos de prueba promedio ArrayDeque y LinkedList se hacen más grandes.
En el tamaño de prueba de 9,900,000 elementos, el enfoque LinkedList tomó ~ 165% más que el enfoque ArrayDeque.

Grafico:

Para llevar:

Si su requisito es almacenar 100 o 200 elementos, no sería muy diferente usar cualquiera de las Colas.
Sin embargo, si está desarrollando en dispositivos móviles, es posible que desee utilizar una ArrayList o una ArrayDeque con una buena estimación de la capacidad máxima que la lista puede requerir debido a la estricta restricción de memoria.
Existe una gran cantidad de código, escrito usando LinkedList así que piénselo con cuidado cuando decida usar un ArrayDeque especialmente porque NO implementa la interfaz de la List (creo que es una razón lo suficientemente grande). Puede ser que su base de código se ArrayDeque extensamente con la interfaz de la Lista, lo más probable es que decida ArrayDeque con un ArrayDeque . Usarlo para implementaciones internas puede ser una buena idea ...

aunque ArrayDeque<E> y LinkedList<E> han implementado la interfaz Deque<E> , pero ArrayDeque básicamente usa la matriz de objetos E[] para mantener los elementos dentro de su objeto, por lo que generalmente usa un índice para ubicar los elementos de cabeza y cola.

En una palabra, simplemente funciona como Deque (con todo el método de Deque), sin embargo usa la estructura de datos de la matriz. En cuanto a cuál es mejor, depende de cómo y dónde los use.

ArrayDeque es nuevo con Java 6, por lo que una gran cantidad de código (especialmente los proyectos que intentan ser compatibles con versiones anteriores de Java) no lo usan.

Es "mejor" en algunos casos porque no está asignando un nodo para cada elemento para insertar; en su lugar, todos los elementos se almacenan en una matriz gigante, que se redimensiona si se llena.