Quanto costa chiamare size() su List o Map in Java?

Question

Quanto costa chiamare size() su List o Map in Java? oppure è meglio salvare il valore di size() in una variabile se si accede frequentemente?

Answer 1

La risposta è che dipende dalla classe di implementazione effettiva. Per alcune classi Map e Collection, size() è un'operazione a tempo costante a basso costo. Per altri, può comportare il conteggio dei membri.

Il Java Collections Cheatsheet (V2) è normalmente una buona fonte per questo tipo di informazioni, ma il server host è attualmente un po 'malato.

Il dominio "coderfriendly.com" non esiste più, ma ho rintracciato una copia di the cheat-sheet su scribd.com.

Il costo di size() sarà anche evidente guardando il codice sorgente. (E questo è un "dettaglio implementativo", che è più o meno garantito di non cambiare ... per le classi di raccolta standard.)

FOLLOWUP

Purtroppo, il bigino documenta solo la complessità del size per la coda implementazioni.Penso che sia perché è O(1) per tutte le altre raccolte; vedi la risposta di @ seanizer.

Answer 2

per ArrayList l'attuazione è come

public int size() { 
     return lastIndex - firstIndex; 
    } 

Quindi non sopra la testa

È possibile controllare il codice sorgente per informazioni dettagliate per la vostra richiesta Impl.

Nota: La fonte è data da OpenJDK

Answer 3

Non ci si deve preoccupare più di tanto. Le implementazioni elenco tengono traccia delle dimensioni. Il costo della chiamata è solo O (1). Se sei molto curioso, puoi leggere il codice sorgente per le implementazioni delle classi concrete di Collection e vedere lì il metodo size().

Answer 4

L'implementazione ottiene da una variabile privata pre-calcolata quindi non è costoso.

Answer 5

Non è necessario archiviare.Non è affatto costoso.Controllare la sorgente di ArrayList e HashMap.

Answer 6

Implementalo, quindi testalo. Se è lento, dai un'occhiata più da vicino.

"L'ottimizzazione prematura è la radice di tutto il male." - D. Knuth

Inoltre: non è necessario richiedere alcune funzionalità di implementazione, specialmente se sono in scatola nera. Cosa succede se si sostituisce quell'elenco con un elenco concorrente in un secondo momento? Cosa succede se Oracle decide di riscrivere l'elenco? Sarà ancora veloce? Non lo sai.

Answer 7

Penso che alcune implementazioni di LinkedList contino il totale per ogni chiamata. La chiamata a un metodo in sé può essere un po 'onerosa, ma solo se stiamo parlando di iterazioni di grandi dimensioni o di codifica dei driver per l'hardware sarebbe davvero un problema.

In entrambi i casi, se lo si salva su una variabile locale, non ci saranno problemi.

Answer 8

List e Map sono interfacce, quindi è impossibile dire. Per le implementazioni nell'API Java Standard, le dimensioni sono generalmente mantenute in un campo e quindi non rilevanti per le prestazioni.

Answer 9

Per la maggior parte delle raccolte, chiamare size() è un'operazione a tempo costante. Ci sono tuttavia alcune eccezioni. Uno è ConcurrentLinkedQueue. Dal Javadoc di the size() method:

Attenzione che, a differenza nella maggior parte delle collezioni, questo metodo non è un'operazione a tempo costante. A causa della natura asincrona di queste code, la determinazione del numero corrente di elementi richiede una traversata O (n).

Quindi temo che non ci sia una risposta generica, è necessario controllare la documentazione della singola raccolta che si sta utilizzando.