ArrayDeque vs ArrayList per implementare uno stack

Question

La documentazione per ArrayDeque dice:

Questa classe è probabile che sia più veloce di stack quando usato come una pila, e più veloce di LinkedList quando viene utilizzato come una coda.

non si fa menzione della differenza tra l'utilizzo di un ArrayDeque come una pila e utilizzando un ArrayList. È possibile utilizzare uno ArrayList come stack come segue.

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

ho scoperto che quando ho usato un ArrayList in questo modo solo, le sue prestazioni è peggio di ArrayDeque. Che cosa spiega questa differenza? Sicuramente non possono essere solo le chiamate a size()? Internamente, sia ArrayList sia ArrayDeque vengono implementati utilizzando un Object[] che viene sostituito da un array più grande quando richiesto, quindi sicuramente le prestazioni dovrebbero essere all'incirca le stesse?

Answer 1

La differenza principale tra i due implementazione è la strategia di ridimensionamento

• ArrayList è ridimensionata per un nuovo formato di oldCapacity + (oldCapacity >> 1), con un conseguente increse del ~ 50%. La capacità di default è 10, con un conseguente capacità dopo ridimensionamento di 15,22,33,49,73,109,163,244,366 ...

• ArrayDeque è sempre ridimensionati a una potenza di 2. In ridimensionamento, la capacità viene raddoppiata. A partire con il default di 16 anni, le capacità resuling dopo ridimensionamento sono 32,64,128,256, ...

Così l'ArrayDeque raggiunge capacità più elevate con molto meno ridimensionare il funzionamento, che sono costose a causa della copia matrice. Cioè per archiviare 256 in ArrayList di dimensioni predefinite, richiede 9 chiamate di ridimensionamento, mentre ArrayDeque richiede solo 4. La copia di array potrebbe essere veloce, ma potrebbe anche richiedere un GC per liberare spazio per i nuovi set di dati, oltre alla memoria costi di copia (dove ArrayDeque potrebbe anche avere prestazioni migliori grazie al suo allineamento alla potenza di 2).

Entrambe le strutture di dati abbiano la migliore complessità nel caso di O (1) per il push e pop attraverso l'accesso diretto su entrambi i head & tail (ArrayDequeue), rispettivamente, aggiungere e rimuovere (Last) size (ArrayList)