Perché le diverse raccolte java hanno una diversa capacità predefinita?

11

Guardando ai diversi costruttori di collezioni mi viene in mente la domanda. Perché ArrayList () costruire una lista vuota con una capacità iniziale di dieci e ArrayDeque () costruisce un deque array vuoto con una capacità iniziale sufficiente a contenere 16 elementi.

    
posta Old Badman Grey 01.08.2013 - 05:08
fonte

3 risposte

17

Risposta breve

Perché la capacità ArrayDeque deve essere una potenza di due, e 16 è la potenza minima di due che è almeno di 10.

ArrayDeque ha bisogno di usare un sacco di% di operazioni ovunque per avvolgere un array lineare che finge di essere circolare.

a % b può essere espresso come a & (b - 1) se b è una potenza di due. L'AND bit a bit è molto più veloce in modo che la capacità di ArrayDeque sia limitata alla potenza di due. Tutte le operazioni della% vengono eseguite con la bitmap anziché la% effettiva dell'implementazione.

Questo è anche perché la nuova HashMap non usa le dimensioni delle tabelle dei numeri primi ma la potenza di due , di nuovo perché l'operazione% deve essere eseguita così spesso e il bit per bit è molto più veloce.

Quindi se la linea di base è 10, allora le strutture che hanno potere di due limitazioni dovrebbero usare 16 perché è la più piccola potenza di due che sia almeno 10.

    
risposta data 01.08.2013 - 22:12
fonte
3

Non escludere la possibilità che non vi sia alcun motivo specifico.

Potrebbe essere che queste due raccolte siano state scritte da diversi team. Entrambi hanno scelto un numero limitato come capacità predefinita, ma la prima squadra ha pensato decimamente e ha scelto 10, mentre la seconda squadra ha pensato binario e ha scelto 16.

    
risposta data 01.08.2013 - 18:31
fonte
1

@ La risposta di Esailija è buona per questo caso specifico.

Più generalmente però, è un compromesso che dipende da molti fattori. Farò alcuni esempi:

  • In che modo viene utilizzata la struttura dei dati di solito? Le strutture dati utilizzate come buffer di dati in genere preferiscono una capacità molto più elevata rispetto alle strutture dati utilizzate per le tuple piccole, ad esempio.
  • Quale dimensione predefinita dei dati si adatta a una linea della cache sulla piattaforma CPU di destinazione? Può fare una grande differenza per le prestazioni se l'impostazione predefinita si adatta alla riga della cache. La scelta di 10 come default in Java potrebbe essere dovuta al fatto che un array di 10 parole a 32 bit più il sovraccarico di array / oggetto si adatta a una linea di cache a 64 byte.
  • Quanto apprezzi spazio rispetto all'efficienza di runtime ? Se desideri prestazioni di runtime migliori, in genere è preferibile assegnare una maggiore quantità di spazio per evitare ulteriori ridistribuzioni in un secondo momento.

Come risultato di questi compromessi, è del tutto comprensibile che diverse implementazioni di raccolta possano avere una diversa capacità di default ottimale.

    
risposta data 17.12.2013 - 17:17
fonte

Leggi altre domande sui tag