java - poll - ArrayDeque vs ArrayList para implementar una pila

que es un deque en java

Question

La documentación para ArrayDeque dice:

Es probable que esta clase sea más rápida que la Pila cuando se usa como una pila, y más rápida que la Lista Vinculada cuando se usa como una cola.

No se menciona la diferencia entre usar un ArrayDeque como una pila y usar un ArrayList . Puede utilizar un ArrayList como una pila de la siguiente manera.

list.add(object);                      // push
object = list.remove(list.size() - 1); // pop

Descubrí que cuando solo utilizaba un ArrayList de esta manera, su rendimiento es peor que el de ArrayDeque . ¿Qué explica esta diferencia? Seguramente, ¿no pueden ser solo las llamadas a size() ? Internamente, tanto ArrayList como ArrayDeque se implementan utilizando un Object[] que se reemplaza por una matriz más grande cuando es necesario, por lo que, seguramente, el rendimiento debería ser más o menos igual.

Answer 1

La principal diferencia entre ambas implementaciones es la estrategia de redimensionamiento.

• ArrayList se redimensiona a un nuevo tamaño de oldCapacity + (oldCapacity >> 1) , lo que resulta en un incremento de ~ 50%. La capacidad por defecto es 10, lo que resulta en una capacidad después de cambiar el tamaño de 15,22,33,49,73,109,163,244,366 ...

• ArrayDeque siempre se redimensiona a una potencia de 2. Al redimensionar, la capacidad se duplica. A partir del valor predeterminado de 16, las capacidades de resolución después del cambio de tamaño son 32,64,128,256, ...

Por lo tanto, ArrayDeque alcanza mayores capacidades con mucho menos operación de cambio de tamaño, que son costosas debido a la copia de matriz. Es decir, para almacenar 256 en ArrayList de tamaño predeterminado, requiere 9 llamadas de cambio de tamaño, mientras que ArrayDeque solo necesita 4. La copia de la matriz puede ser rápida, pero también puede requerir un GC para liberar espacio para los nuevos conjuntos de datos, además de la memoria costos de copia (donde ArrayDeque también podría tener un mejor rendimiento debido a su alineación con la potencia de 2).

Ambas estructuras de datos tienen la complejidad del mejor caso de O (1) para empujar y abrir a través del acceso directo en la head y tail (ArrayDequeue) respectivamente agregar y eliminar (Último) size (ArrayList)