Quale raccolta Java è più efficiente se ho bisogno di tenere un elemento la maggior parte del tempo, e occasionalmente di più?

Question

Quale raccolta Java è più efficiente se ho bisogno di tenere un elemento la maggior parte del tempo, e occasionalmente di più?

#1 da (6 voti)
#2 da (0 voti)

-1

Ho una collezione in cui sto inserendo elementi in base a una sorta di input. Circa il 90% delle volte, ci sarà un solo elemento in questa collezione. Possono esserci più elementi, ma ogni elemento oltre il primo ha una probabilità di apparire in modo esponenziale decrescente. Quindi potrebbe avere 2 elementi il 9% delle volte, 3 elementi 0,9%, 4 elementi 0,09%, ecc.

Quale struttura dati è più efficiente qui? Le mie due idee sono una ArrayList con una dimensione iniziale di 1, o qualche altro numero molto piccolo (forse 2 o 3?), O una LinkedList, che avrà sempre il sovraccarico dei puntatori testa / coda, ma non perderà tempo / spazio per allocare memoria aggiuntiva.

Mi rendo conto che qualsiasi cosa scegliamo probabilmente non è terribilmente importante, ma mi sono imbattuto in questa situazione più volte e sono interessato se c'è una convenzione stabilita.

java design-patterns

posta codebreaker 25.11.2017 - 19:31

fonte

2 risposte

Leggi altre domande sui tag java design-patterns

È bello che i setter chiamanti seguano lo stesso ordine degli elementi XSD? [chiuso] Come elencare le parole composte da un dizionario [chiuso]

score 6 · Answer 1

Per raccolte tanto brevi quanto le tue, non ha senso usare sofisticate strutture di dati. L'unico aspetto che potrebbe importare è il consumo di memoria.

E come altri già hanno commentato, quello che stai facendo sembra una prematura micro-ottimizzazione. Ma non è sempre male.

Vorrei usare new ArrayList(2) . Perché?

Non diminuisce la leggibilità del tuo codice in un secondo momento, usando la collezione.
Alloca un array abbastanza grande per il 99 percento dei casi.
Non mette a rischio la correttezza del tuo codice.
Non rallenterà la tua applicazione (sicuramente meno di una percentuale, se l'aggiunta alla raccolta avviene la maggior parte del tempo).
Riduce il consumo di memoria.

Forse una dimensione iniziale di 1 o 3 sarebbe meglio, ma dovresti passare del tempo solo se lo hai trovato necessario.

In una parte simile di un'applicazione a tenuta di memoria, dopo aver profilato i modelli di consumo della memoria, ho trovato il seguente schema:

Ho avuto molte raccolte di elementi singoli, spesso molte contenenti lo stesso elemento.
Per le raccolte di elementi singoli, ho condiviso singleton creati con Collections.singletonList() .
Solo quando "aggiungo" l'elemento successivo, l'ho sostituito con un ArrayList.

Questo ha un costo:

Rende il codice meno leggibile: invece di aggiungere semplicemente, avevo bisogno di supportare lo scambio di elenchi.
Ha creato il rischio di introdurre un bug lì.

Ma nel mio caso, ha dato un miglioramento significativo della memoria.

score 0 · Answer 2

Se hai dubbi sulla concorrenza, questo è un buon caso per un CopyOnWriteArrayList . Il loro principale svantaggio è che ricreano copie ogni volta che aggiungi un elemento, ma ciò non accade spesso nel tuo caso! Inoltre non stai sprecando troppa memoria e GC dato che le tue liste sono minuscole.
Garantiscono un'ottima sicurezza del thread.

Memoria / tempo sono leggermente meno efficienti di ArrayList come suggerito da Ralf, ma se si blocca su di essi, avvolgendo in synchronizedList() , ecc., probabilmente sarebbero più efficienti.