Quale elenco < Object > l'implementazione sarà la più veloce per un passaggio scrivere, leggere, quindi distruggere?

Question

Qual è l'implementazione dell'elenco più veloce (in Java) in uno scenario in cui l'elenco verrà creato un elemento alla volta e in un secondo momento verrà letto un elemento alla volta? Le letture verranno eseguite con un iteratore e quindi l'elenco verrà distrutto.
So che la notazione Big O per get è O (1) e add è O (1) per un ArrayList, mentre LinkedList è O (n) per get e O (1) per add. L'iteratore si comporta con la stessa notazione Big O?

Answer 1

Dipende in gran parte dal fatto che tu conosca la dimensione massima di ciascun elenco in anticipo.

Se lo fai, usa ArrayList ; sarà sicuramente più veloce.

Altrimenti, probabilmente dovrai creare un profilo. Mentre l'accesso a ArrayList è O (1), crearlo non è così semplice, a causa del ridimensionamento dinamico.

Un altro punto da considerare è che il compromesso spazio-temporale non è ben definito. Ogni oggetto Java ha un certo sovraccarico. Mentre un ArrayList può sprecare spazio sugli slot in eccesso, ogni slot ha solo 4 byte (o 8 su una JVM a 64 bit). Ogni elemento di un LinkedList è probabilmente di circa 50 byte (forse 100 in una JVM a 64 bit). Quindi è necessario disporre di alcuni slot sprecati in un ArrayList prima che un LinkedList vinca effettivamente il presunto vantaggio di spazio. Anche la località di riferimento è un fattore, e ArrayList è preferibile anche lì.

In pratica, uso quasi sempre ArrayList .

Answer 2

Primi pensieri:

• Rifattorizza il tuo codice per non aver bisogno dell'elenco.
• Semplifica i dati fino a un tipo di dati scalare, quindi usa: int[[
• O semplicemente usa una matrice di qualunque oggetto tu abbia: Oggetto [] - John Gardner
• Inizializza l'elenco a dimensione intera: new ArrayList (123);

Ovviamente, come menzionano tutti gli altri, eseguono test delle prestazioni, dimostrano che la tua nuova soluzione è un miglioramento.

Answer 3

L'iterazione attraverso un elenco collegato è O (1) per elemento.

Il tempo di esecuzione di Big O per ciascuna opzione è lo stesso. Probabilmente ArrayList sarà più veloce a causa della migliore localizzazione della memoria, ma dovresti misurarlo per sapere con certezza. Scegli quello che rende il codice più chiaro.

Answer 4

Nota che iterare attraverso un'istanza di LinkedList può essere O (n ^ 2) se fatto in modo ingenuo. In particolare:

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

Questo è assolutamente orribile in termini di efficienza a causa del fatto che l'elenco deve essere attraversato fino a i due volte per ogni iterazione. Se usi LinkedList , assicurati di usare un Iterator o il migliorato di Java 5 per -loop:

for (Object o : list) {
    // ...
}

Il codice sopra è O (n), poiché l'elenco viene attraversato in modo statico sul posto.

Per evitare tutte le seccature di cui sopra, basta usare ArrayList . Non è sempre la scelta migliore (in particolare per quanto riguarda l'efficienza dello spazio), ma di solito è una scommessa sicura.

Answer 5

Suggerisco di confrontarlo. Una cosa è leggere l'API, ma fino a quando non la provi da solo, sarebbe accademico.

Dovrebbe essere abbastanza facile da testare, assicurati solo di fare operazioni significative, o che l'hotspot ti renderà super intelligente e ottimizzerà tutto su un NO-OP :)

Answer 6

Quasi sicuramente vuoi un ArrayList . Sia l'aggiunta che la lettura sono "tempo costante ammortizzato" (ovvero O (1)) come specificato nella documentazione (nota che questo è vero anche se l'elenco deve aumentare le sue dimensioni - è progettato in questo modo vedi http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html ). Se si conosce approssimativamente il numero di oggetti che verranno memorizzati, viene eliminato anche l'incremento delle dimensioni di ArrayList.

L'aggiunta alla fine di un elenco collegato è O (1), ma il moltiplicatore costante è più grande di ArrayList (poiché di solito si crea un oggetto nodo ogni volta). La lettura è praticamente identica a ArrayList se si utilizza un iteratore.

È una buona regola usare sempre la struttura più semplice che puoi, a meno che non ci sia una buona ragione per non farlo. Qui non esiste tale motivo.

La citazione esatta dalla documentazione per ArrayList è: " L'operazione di aggiunta viene eseguita in un tempo costante ammortizzato, cioè l'aggiunta di n elementi richiede O (n) tempo. Tutte le altre operazioni vengono eseguite in un tempo lineare (approssimativamente parlando). Il fattore costante è basso rispetto a quello per l'implementazione di LinkedList. & Quot;

Answer 7

Esiste una nuova implementazione dell'elenco chiamata GlueList che è più veloce di tutte le implementazioni dell'elenco classico.

Answer 8

Ho effettivamente iniziato a pensare che qualsiasi uso di strutture di dati con comportamento non deterministico, come ArrayList o HashMap, dovrebbe essere evitato, quindi direi di usare ArrayList solo se puoi limitarne le dimensioni; qualsiasi elenco illimitato usa LinkedList. Questo perché codifico principalmente sistemi con requisiti quasi in tempo reale.

Il problema principale è che qualsiasi allocazione di memoria (che potrebbe avvenire in modo casuale con qualsiasi operazione di aggiunta) potrebbe anche causare una garbage collection e qualsiasi garbage collection può farti perdere un target. Maggiore è l'allocazione, maggiore è la probabilità che si verifichi e ciò si complica anche se si utilizza il collector CMS. Il CMS non è compatto, quindi trovare spazio per un nuovo nodo elenco collegato sarà generalmente più semplice che trovare spazio per un nuovo array di 10.000 elementi.

Più rigoroso è il tuo approccio alla programmazione, più puoi avvicinarti al tempo reale con una JVM di serie. Ma la scelta di sole strutture di dati con comportamento deterministico è uno dei primi passi che dovresti fare.