Qual è la migliore implementazione Elenco per elenchi di grandi dimensioni in java

Question

Devo creare un elenco di n elementi (potrebbe essere fino a 100.000). ogni elemento nella lista è un numero intero equivalente all'indice della lista. Dopo questo devo chiamare Collections.shuffle su questo elenco. La mia domanda è, quale implementazione lista (collezioni java o collezioni apache) dovrebbe essere utilizzata. Il mio istinto è che ArrayList può essere usato qui. Tutti i pensieri sono apprezzati. Grazie!

Grazie per gli ingressi. Penso di stare attaccato alla ArrayList. Attualmente sto usando il costruttore ArrayList con il parametro initialCapacity e passo la dimensione della lista. Quindi se l'elenco originale è 100000, creo questo nuovo elenco con il nuovo ArrayList (100000); Quindi penso di non aver creato un array e di fare una lista perché non ci sarà alcun ridimensionamento. Inoltre, la maggior parte delle raccolte di apache Elenca come GrowthList & LazyList non implementa RandomAccess. Questo sicuramente rallenterebbe lo shuffle (come per javadocs). FastArrayList implementa RandomAccess ma apache ha una nota per questa classe che dice "Questa classe non è multipiattaforma.Utilizzarla può causare errori imprevisti su alcune architetture".

Answer 1

ArrayList ha la maggior parte probabilmente il meno overhead per elemento della lista, quindi dovrebbe essere la scelta migliore. Potrebbe essere una scelta peggiore se hai spesso bisogno di cancellare gli elementi nel mezzo della lista.

Answer 2

ArrayList<T> probabilmente sarebbe bene, sì - ma quali criteri stai usando per "migliore" in ogni caso? E quanto è bello essere comunque? Quali sono i tuoi compromessi tra complessità e "bontà" in tutti quei criteri?

Answer 3

Citato da javadoc Collections.shuffle:

Questo metodo viene eseguito in tempo lineare. Se l'elenco specificato non implementa l'interfaccia RandomAccess ed è di grandi dimensioni, questa implementazione scarica l'elenco specificato in un array prima di mischiarlo, e scarica l'array shuffled nella lista. Ciò evita il comportamento quadratico che risulterebbe dal mischiare un elenco di "accesso sequenziale" sul posto.

Quindi, se non ci sono altri bisogni, andrei con ArrayList che implementa RandomAccess.

Answer 4

ArrayList sarà la migliore lista per questo. Poiché il supporto dell'array sarà molto efficace per lo scambio di elementi utilizzati in shuffle.

Ma se si sta davvero considerando la performance, si potrebbe voler considerare l'uso di un int [] o di un elenco personalizzato basato su int [] come con tutte le implementazioni standard di List ed List che saranno boxing e unboxing inti di Integers.

Questo non sarà un problema sul suffle in quanto questo sarà solo riordinando i puntatori, ma vi sarà la creazione di 100.000 oggetti quando non potrebbe essere necessario. Supponendo che tu conosca le dimensioni della tua lista prima della creazione, puoi facilmente creare una nuova classe List che avvolge una matrice primitiva. Se utilizzato come java.util.List, sarà comunque necessario inserire il valore restituito da qualsiasi metodo get.

Answer 5

La creazione di un array Integer e il suo avvolgimento con Arrays.asList forniscono un sovraccarico ancora inferiore rispetto a un normale ArrayList.

List<Integer> makeList(int size){ 
    if (size < 0) throw new IllegalArgumentException(); 
    Integer[] arr = new Integer[size]; 
    for (int i = 0; i < arr.length; ++i) arr[i] = i; 
    List<Integer> list = Arrays.asList(arr); 
    Collection.shuffle(list); 
    return list; 
} 

Si salva un intero int vale la pena di spazio (... che devo ammettere che è assolutamente nulla in questo contesto), ma lo fa eseguire un minor numero di test di ricezione del "reale" ArrayList, quindi accesso sarà leggermente più veloce.Probabilmente nulla di ciò che si nota, però :)

Answer 6

Javolution afferma di avere l'implementazione List più veloce in java. Ma non ho trovato alcuna implementazione shuffle in questa libreria, quindi dovrai farlo a mano.

Answer 7

La libreria di Google Guava ha una gestione primitiva molto piacevole, incluso un metodo Ints.asList() che restituisce un elenco che può essere mescolato.

Il progetto Guava è ancora in una fase preliminare di distribuzione, anche se il codice è stato attentamente rivisto e ampiamente utilizzato da Google. Dovrai recuperare il codice da SVN e creare le classi com.google.common.primitive.

Answer 8

È inoltre possibile utilizzare l'implementazione di elenchi basati su file mappati in memoria. In tale implementazione l'elenco non è completamente presente in memoria ma solo una sezione dell'enorme lista sarà attiva in memoria. Se si sta raggiungendo la limitazione dello spazio dell'heap (principalmente nella jvm a 32 bit) potrebbe essere necessario fare in modo che l'elenco spinga i dati senza interruzioni utilizzando un file mappato in memoria che sarà più veloce del normale I/O di file. Una tale implementazione è descritta in questo google code e spiegata in questo link.

Answer 9

C'è una nuova implementazione di lista chiamata GlueList che è molto veloce di ArrayList e LinkedList.