default Tipo di raccolta

Question

Si supponga di dover archiviare/recuperare gli articoli in un Collection, non si preoccupi dell'ordinazione e sono consentiti duplicati, che tipo di Collection usi?

Per impostazione predefinita, ho sempre utilizzato ArrayList, ma ricordo di aver letto/sentito da qualche parte che un'implementazione di Queue potrebbe essere una scelta migliore. A consente di aggiungere/recuperare/rimuovere articoli in posizioni arbitrarie, il che comporta una penalizzazione delle prestazioni. Siccome uno Queue non fornisce questa funzione, dovrebbe in teoria essere più veloce quando questa funzione non è richiesta.

Mi rendo conto che tutte le discussioni sulle prestazioni sono alquanto prive di significato, l'unica cosa che conta davvero è la misurazione. Tuttavia, sono interessato a sapere cosa altri usano per un Collection, quando non si preoccupano di ordinare, e sono consentiti i duplicati, e perché?

Answer 1

Come impostazione predefinita, io preferisco lo LinkedList a ArrayList. Ovviamente, li uso non attraverso l'interfaccia List, ma piuttosto attraverso l'interfaccia Collection.

Nel corso del tempo, ho effettivamente scoperto che quando ho bisogno di una raccolta generica, è più o meno che inserire alcune cose, quindi scorrere su di essa. Se ho bisogno di un comportamento più evoluto (ad esempio controllo dell'accesso casuale, controllo di ordinamento o unicità), cambierò l'implementazione utilizzata, ma prima cambierò l'interfaccia utilizzata nel modo più appropriato. In questo modo, posso garantire che la funzionalità venga fornita prima di concentrarsi sull'ottimizzazione e l'implementazione.

Answer 2

ArrayList contiene fondamentalmente una matrice all'interno (è per questo che si chiama ArrayList). E operazioni come addd/remove su posizioni arbitrarie vengono eseguite in modo semplice, quindi se non le usi, non c'è alcun danno alle prestazioni.

Answer 3

Se l'ordinazione e duplicati non è un problema e caso è solo per la conservazione,

Io uso ArrayList, come implementa tutte le operazioni di lista. Non ho mai sentito problemi di prestazioni con queste operazioni (non ho mai avuto alcun impatto sui miei progetti). In realtà l'utilizzo di queste operazioni ha un utilizzo semplice & Non ho bisogno di preoccuparmi di come è gestito internamente.

Solo se più thread accedono a questo elenco, utilizzo Vector perché i suoi metodi sono sincronizzati.

Anche ArrayList e Vector sono raccolte che impari prima :).

Answer 4

"Dipende". La domanda a cui devi rispondere per prima cosa è "Per cosa voglio usare la collezione?"

Se si inseriscono/rimuovono spesso elementi su una delle estremità (inizio, fine), uno Queue sarà migliore di uno ArrayList. Tuttavia in molti casi crei una raccolta per leggerne solo la parte. In questo caso, un ArrayList è molto più efficiente: poiché è implementato come array, è possibile eseguire iterazioni piuttosto efficienti (lo stesso vale per lo LinkedList). Tuttavia un LinkedList utilizza riferimenti per collegare insieme singoli elementi. Quindi, se non hai bisogno di rimozioni casuali di elementi (nel mezzo), un ArrayList è migliore: un ArrayList utilizzerà meno memoria in quanto gli elementi non necessitano della memoria per il riferimento all'elemento successivo/precedente.

Per riassumere:

ArrayList = buono se si inserisce una volta e leggere spesso (ad accesso casuale o sequenziale)

LinkedList = buono se si inserisce/rimuove spesso in posizioni casuali e di sola lettura sequenziale

ArrayDeque (solo java6) = buono se si inserisce/rimuove a inizio/fine e leggere casuale o sequenziale

Answer 5

dipende da ciò che si sa su di esso.

Se non ho idea, tendo ad andare su una lista collegata, poiché la penalità per l'aggiunta/rimozione alla fine è costante. Se ho un'idea approssimativa della dimensione massima, vado per un arraylist con la capacità specificata, perché è più veloce se la stima è buona. Se conosco veramente le dimensioni esatte, tendo ad andare per un normale array; anche se questo non è proprio un tipo di collezione.

Answer 6

Mi rendo conto che tutte le discussioni sulle prestazioni sono alquanto prive di significato, l'unica cosa che conta davvero è la misurazione.

Questo non è necessariamente vero.

Se la tua conoscenza di come funzionerà l'applicazione dice a che alcune raccolte saranno molto grandi, allora è una buona idea scegliere il giusto tipo di raccolta. Ma il tipo di raccolta corretto dipende da , in particolare, su come verranno utilizzate le raccolte; cioè sugli algoritmi.

Ad esempio, se l'applicazione rischia di essere dominato da testare se una collezione in possesso di un determinato oggetto, il fatto che Collection.contains(Object) è O(N) sia per LinkedList<T> e ArrayList<T>forza significa che nessuno dei due è un tipo di raccolta appropriato. Invece, forse dovresti rappresentare la collezione come HashMap<T, Integer>, dove il Integer rappresenta il numero di occorrenze di uno T nella "collezione". Questo ti darà il test e la rimozione di O(1), a costo di più overheads di spazio e più lento (anche se ancora O(1)) inserimento.

Ma la cosa da sottolineare è che se è probabile che si tratti di raccolte molto grandi, non ci dovrebbe essere un tipo di raccolta "predefinito". Devi pensare alla collezione nel contesto degli algoritmi. (E il rovescio della medaglia è che se le collezioni saranno sempre piccole, probabilmente farà poca differenza quale tipo di raccolta si sceglie.)