performance della Classe Collection in Java

Question

Tutti,

Mi sono state andando attraverso un sacco di siti che pubblicano sulle prestazioni di varie classi di raccolta per le varie azioni ovvero l'aggiunta di un elemento, cercare e cancellare. Ma noto anche che tutti forniscono ambienti diversi in cui è stato condotto il test, cioè sistema operativo, memoria, thread in esecuzione ecc.

La mia domanda è, se c'è qualche sito/materiale che fornisce le stesse informazioni sulle prestazioni al test migliore base ambientale? cioè, le configurazioni non dovrebbero essere un problema o un catalizzatore per le scarse prestazioni di una specifica struttura di dati.

[Aggiornato]: Esempio, HashSet e LinkedHashSet hanno entrambi una complessità di O (1) per l'inserimento di un elemento. Tuttavia, il test di Bruce Eckel afferma che l'inserimento richiederà più tempo per LinkedHashSet che per HashSet [http://www.artima.com/weblogs/viewpost.jsp?thread=122295]. Quindi dovrei ancora passare per la notazione Big-Oh?

Answer 1

Ecco i miei consigli:

1. Prima di tutto, non ottimizzare :) Non quello Ti sto dicendo di progettare software di crap, ma solo di concentrarmi sul design e sulla qualità del codice più che sull'ottimizzazione prematura. Supponendo che hai fatto, e ora si ha realmente bisogno di preoccuparsi per le quali la raccolta è meglio al di là ragioni puramente concettuali, passiamo al punto 2
2. Really, don't optimize yet (circa rubato da M. A. Jackson)
3. fine. Quindi il tuo problema è che anche se hai formule teoriche di complessità temporale per casi migliori, casi peggiori e casi medi, hai notato che le persone dicono cose diverse e che le impostazioni pratiche sono una cosa molto diversa dalla teoria. Quindi gestisci i tuoi benchmark! Puoi solo leggere così tanto e, mentre lo fai, il tuo codice non scrive da solo. Una volta che hai finito con la teoria, scrivi il tuo benchmark - per la tua applicazione reale, non una mini-applicazione irrilevante a scopo di test - e guarda cosa succede realmente al tuo software e perché. Quindi scegli il miglior algoritmo. È empirico, potrebbe essere considerato una perdita di tempo, ma è l'unico modo che funziona in modo impeccabile (fino al prossimo punto).
4. Ora che hai fatto ciò, hai l'app più veloce di sempre. Fino al prossimo aggiornamento della JVM. O di alcuni componenti sottostanti del sistema operativo da cui dipende il particolare collo di bottiglia delle prestazioni. Indovina un po? Forse i tuoi clienti ne hanno di diversi. Ecco il divertimento: devi essere sicuro che il tuo benchmark sia valido per gli altri o nella maggior parte dei casi (o divertiti a scrivere codice per casi diversi). È necessario raccogliere dati dagli utenti. MOLTE. E poi hai bisogno di farlo più e più volte per vedere cosa succede e se è ancora vero. E poi ri-scrivere il codice di conseguenza più e più volte (The - ormai terminata -. Engineering Windows 7 blog è in realtà un buon esempio di come la raccolta dei dati utente aiuta a prendere decisioni consapevoli per migliorare l'esperienza degli utenti

Oppure si può .. . si sa ... NON ottimizzare piattaforme e compilatori cambieranno, ma un buon progetto dovrebbe - in media - svolgere abbastanza bene

Altre cose si può anche fare:..

• Date un'occhiata alla Il codice sorgente di JVM. È molto educativo e scopri una mandria di cose nascoste (non sto dicendo che a devi usarli ...)
• Vedi quell'altra cosa sulla tua lista TODO su cui devi lavorare?Sì, quello vicino alla cima ma che salti sempre perché è troppo difficile o non abbastanza divertente. Quello lì. Bene, vai da solo e lascia da solo l'ottimizzazione: è il figlio malvagio di un vaso di Pandora e una banda di Moebius. Non ne uscirai mai, e ti pentirai profondamente di aver provato a farcela.

Detto, non so il motivo per cui è necessario il miglioramento delle prestazioni in modo forse hai un molto motivo valido.

E non sto dicendo che scegliere la raccolta giusta non ha importanza. Proprio quelli che sai quale scegliere per un particolare problema, e che hai guardato le alternative, allora hai fatto il tuo lavoro senza doversi sentire in colpa. Le collezioni hanno solitamente un significato semantico, e finché lo rispettate starai bene.

Answer 2

A mio parere, tutto ciò che serve sapere su una struttura dati è il Big-O delle operazioni su di esso, non le misure soggettive di architetture diverse. Collezioni diverse hanno scopi diversi.

Map s sono dizionari
Set s affermano unicità
List s forniscono raggruppamento e preservano iterazione ordine
Tree s forniscono ordine economico e ricerche rapide sui contenuti variabili dinamicamente che richiedono costante ordinato

Redatta a includere la dichiarazione di bwawok sul caso d'uso delle strutture ad albero

Aggiornamento
Dalla tabella hash javadoc on LinkedHashSet

e l'attuazione lista collegata dell'interfaccia Set, con ordine di iterazione prevedibile.

...

prestazioni è probabile che sia solo leggermente inferiore a quello del HashSet, causa la spesa aggiuntiva di mantenere la lista collegata, con una sola eccezione: l'iterazione su un LinkedHashSet richiede tempo proporzionale alla dimensione della impostato, indipendentemente dalla sua capacità. È probabile che l'iterazione su un HashSet sia più costosa e richiede tempo proporzionale alla sua capacità.

ora siamo passati dal caso molto generale della scelta di un interfaccia dati-struttura adeguata al caso più specifico della quale implementazione da utilizzare. Tuttavia, alla fine arriviamo alla conclusione che implementazioni specifiche siano adatte per applicazioni specifiche basate sull'invariando unico e sottile offerto da ciascuna implementazione.

Answer 3

Che cosa è necessario sapere su di loro e perché? La ragione per cui i benchmark mostrano un dato JDK e l'hardware è così che potrebbero (in teoria) essere riprodotti. Quello che dovresti ottenere dai benchmarks è un'idea di come funzioneranno le cose. Per un numero ASSOLUTO, dovrai eseguirlo contro il tuo codice facendo le tue cose.

La cosa più importante da sapere è il runtime Big O di varie raccolte.Sapendo che ottenere un elemento da un ArrayList non ordinato è O (n), ma ottenerlo da una HashMap è O (1) è ENORME.

Se si utilizza già la raccolta corretta per un dato lavoro, si è al 90% del percorso. I tempi in cui devi preoccuparti di quanto velocemente puoi, ad esempio, ottenere elementi da una HashMap dovrebbero essere dannatamente rari.

Una volta che si lascia una terra con thread singolo e si sposta in una terra a più thread, sarà necessario iniziare a preoccuparsi di cose come ConcurrentHashMap vs Collections.synchronized hashmap. Finché non si è multi-thread, non ci si può preoccupare di questo tipo di cose e concentrarsi su quale collezione per quale uso.

Update per HashSet vs LinkedHashSet

non ho mai trovato un caso d'uso in cui avevo bisogno di un hash Set Linked (perché se mi preoccupo ordine che tendono ad avere una lista, se mi preoccupo O (1) ottiene, tendo ad usare un HashSet.In realtà, la maggior parte del codice utilizzerà ArrayList, HashMap o HashSet.Se hai bisogno di altro, sei in un caso "edge"

Answer 4

Se dovessi ordinare milioni di righe, proverei a trovare un modo diverso. Forse potrei migliorare il mio SQL, migliorare il mio algoritmo, o forse scrivere gli elementi sul disco e utilizzare il comando di ordinamento del sistema operativo.

Non ho mai avuto un caso in cui le raccolte in cui la causa dei miei problemi di prestazioni.

Answer 5

Le diverse classi di raccolta hanno diverse prestazioni Big-O, ma tutto ciò che ti dice è come si scala quando diventano grandi. Se il tuo set è abbastanza grande, quello con O (1) supererà quello con O (N) o O (logN), ma non c'è modo di dire quale valore di N è il punto di pareggio, eccetto per esperimento.

In genere, uso solo la cosa più semplice possibile, e poi se diventa un "collo di bottiglia", come indicato dalle operazioni su quella struttura dati che richiede molto tempo, allora passerò a qualcosa con una migliore O-grande valutazione. Molto spesso, il numero di elementi nella raccolta non si avvicina mai al punto di pareggio, oppure esiste un altro modo semplice per risolvere il problema delle prestazioni.

Answer 6

Entrambe HashSet e LinkedHashSet hanno prestazioni O (1). Lo stesso con HashMap e LinkedHashMap (in realtà i primi sono implementati in base al successivo). Questo ti dice solo in che modo questi algoritmi scala, non come essi effettivamente eseguono. In questo caso, lo LinkHashSet fa lo stesso lavoro di HashSet ma deve sempre aggiornare anche un puntatore precedente e successivo per mantenere l'ordine. Ciò significa che la costante (questo è un valore importante anche quando si parla delle prestazioni dell'algoritmo reale) per HashSet è inferiore a LinkHashSet.

Così, dal momento che questi due hanno la stessa Big-O, che scalare la stessa sostanza - cioè come n cambiamenti, entrambi hanno lo stesso cambiamento prestazioni e con O (1) le prestazioni, in media, fa non cambiare.

Quindi ora la vostra scelta si basa sulla funzionalità e sulle vostre esigenze (che in realtà dovrebbero essere quelle che prima considerate comunque). Se hai solo bisogno di un veloce aggiungi e ottenere le operazioni, dovresti sempre scegliere HashSet. Se hai anche bisogno di un ordine coerente, come l'ultimo accesso o l'ordine di inserimento, allora lo deve utilizzare anche la versione della classe Linked ....

Ho utilizzato la classe "collegata" nelle applicazioni di produzione, ovvero LinkedHashMap.L'ho usato in un caso per un simbolo come un tavolo, quindi volevo un rapido accesso ai simboli e alle informazioni correlate. Ma volevo anche trasmettere le informazioni in almeno un contesto nell'ordine in cui l'utente ha definito quei simboli (ordine di inserimento). Ciò rende l'output più amichevole per l'utente poiché può trovare le cose nello stesso ordine in cui sono state definite.

Answer 7

Ho creato la mia propria sperimentazione con HashSet e LinkedHashSets. Per add() e contiene il tempo di esecuzione è O (1), non prendendo in considerazione per un sacco di collisioni. Nel metodo add() per un linkedhashset, inserisco l'oggetto in una tabella hash creata dall'utente che è O (1) e poi metto l'oggetto in una lista separata per tenere conto dell'ordine. Quindi, il tempo di esecuzione per rimuovere un elemento da un linkedhashset, è necessario trovare l'elemento nella tabella hash e quindi cercare nella lista collegata che ha l'ordine. Quindi il tempo di esecuzione è O (1) + O (n), rispettivamente, che è O (n) per remove()