Utilizzo di alberi neri rossi per l'ordinamento

Question

Il tempo di esecuzione nel caso peggiore di un red-black tree è O(lg n) e se eseguo un in-order walk nell'albero, in sostanza visita ogni nodo, quindi il runtime totale nel caso peggiore per stampare la raccolta ordinata sarebbe O (n lg n)

sono curioso, perché sono red-black trees non preferire per l'ordinamento sopra quick sort (il cui caso medio tempo di esecuzione è O(n lg n).

vedo che forse perché red-black trees non sono ordinate in- posto, ma non sono sicuro, quindi forse qualcuno potrebbe aiutare.

Answer 1

Sapendo che algoritmo di ordinamento comporta meglio realmente dipendono i dati e situazione.

Se si sta parlando in termini generali/pratici,

Quicksort (quella in cui si seleziona il perno in modo casuale/Basta scegliere uno fisso, rendendo peggiore caso Omega (n^2)) potrebbe essere migliore di Red- Black Trees perché (non necessariamente in ordine di importanza)

• Quicksort è sul posto. Tiene basso l'ingombro della memoria. Diciamo che questa routine quicksort faceva parte di un programma che si occupa di molti dati. Se continuassi a utilizzare grandi quantità di memoria, il tuo sistema operativo potrebbe iniziare a scambiare la memoria del processo e distruggere il tuo perf.

• Gli accessi alla memoria di Quicksort sono localizzati. Questo funziona bene con il caching/swapping.

• Quicksort può essere facilmente parallelizzato (probabilmente più rilevante in questi giorni).

• Se si tentasse di ottimizzare l'ordinamento di alberi binari (utilizzando un albero binario senza bilanciamento) utilizzando invece una matrice, si finirà per fare qualcosa come Quicksort!

• Gli alberi di colore rosso-nero hanno overhead di memoria. Devi allocare i nodi possibilmente più volte, i tuoi requisiti di memoria con gli alberi sono doppi/tripli rispetto agli array.

• Dopo aver ordinato, diciamo che volevi il 1045 (ad esempio) elemento, dovrai mantenere le statistiche degli ordini nell'albero (costo extra di memoria a causa di questo) e avrai tempo di accesso O (logn)!

alberi

• rosso-nero ha overheads solo per accedere all'elemento successivo (ricerche puntatore)

alberi

• rosso-nero non giocare bene con la cache e gli accessi puntatore potrebbero indurre più swapping.

• La rotazione in alberi rosso-neri aumenta il fattore costante in O (nlogn).

• Forse il motivo più importante (ma non valido se si dispone di lib etc disponibile), Quicksort è molto semplice da comprendere e implementare. Anche un bambino delle scuole può capirlo!

Direi che provi a misurare entrambe le implementazioni e vedere cosa succede!

Inoltre, Bob Sedgewick ha fatto una tesi su quicksort! Potrebbe valere la pena leggerlo.

Answer 2

Ci sono molti algoritmi di ordinamento che sono il caso peggiore O(n log n) - per esempio, unisci l'ordinamento. La ragione per cui quicksort è preferito è perché è più veloce nella pratica, anche se algoritmicamente potrebbe non essere buono come altri algoritmi.

Spesso gli ordinamenti incorporati utilizzano una combinazione di vari metodi in base ai valori di n.

Answer 3

Le misure di complessità del tempo Big-O generalmente non prendono in considerazione i fattori scalari, ad esempio O (2n) e O (4n) vengono generalmente ridotti a O (n). L'analisi della complessità del tempo si basa su fasi operative a livello algoritmico, non a un livello di programmazione rigoroso, cioè senza codice sorgente o considerazioni di istruzione macchina nativa.

Quicksort è generalmente più veloce dell'ordinamento basato su albero poiché (1) i metodi hanno la stessa complessità media temporale algoritmica e (2) le operazioni di ricerca e scambio richiedono meno comandi di programma e accessi ai dati quando si lavora con array semplici rispetto a quelli rossi - Alberi neri, anche se l'albero utilizza un'implementazione basata su array sottostante. La manutenzione dei vincoli dell'albero rosso-nero richiede passaggi operativi aggiuntivi, memorizzazione/accesso del valore del campo dati (colori dei nodi), ecc. Rispetto alle semplici fasi di scambio delle partizioni dell'array di un quicksort.

Il risultato netto è che gli alberi rosso-neri hanno coefficienti scalari superiori rispetto Quicksort non che vengono oscurata dal O standard (n log n) tempo medio risultato dell'analisi della complessità.

Alcune altre considerazioni pratiche sono collegati architetture di macchina sono brevemente discusse nel Quicksort article on Wikipedia

Answer 4

In genere, le rappresentazioni degli algoritmi di O (nlgn) possono essere espanse in A * nlgn + B dove A e B sono costanti. Esistono molte prove algoritmiche che mostrano che i coefficienti per quicksort sono inferiori a quelli di altri algoritmi. Questo è nel migliore dei casi (l'ordinamento rapido si comporta in modo orribile sui dati ordinati).

Answer 5

Ciao, il modo migliore per spiegare la differenza tra tutte le routine di smistamento secondo me è. (La mia risposta è per le persone che sono confuse su come l'ordinamento rapido è più veloce nella pratica di un altro algoritmo di ordinamento).

"Penso che stiate correndo su un computer molto lento".

1. Per prima cosa un'operazione di confronto richiede 1 ora.
2. Un'operazione di cambio richiede 2 ore.

"Sto usando l'ora solo per far capire alla gente quanto sia importante il tempo".

Ora da tutte le operazioni di smistamento, l'ordinamento rapido ha molto meno confronti e molto meno scambio di elementi.

L'ordinamento rapido è più veloce per questo motivo principale.

Answer 6

Ci sono molti casi in cui gli alberi rossi non sono male per l'ordinamento. Il mio test ha mostrato, rispetto a merge naturali sorta, che gli alberi rosso-neri Excel in cui:

Gli alberi sono migliori per Dups: Tutti i test in cui hanno bisogno di essere eleminated dups, algoritmo di albero è meglio.Questo non è sorprendente, dal momento che l'albero può essere mantenuto molto piccolo fin dall'inizio, per cui gli algoritmi progettati per l'ordinamento di array in linea potrebbero passare intorno a segmenti più grandi per un tempo più lungo.

Gli alberi sono migliori per Casuale: Tutti i test con algoritmo ad albero casuale sono migliori. Anche questo non è sorprendente, poiché in una distanza tra gli alberi gli elementi sono più corti e lo spostamento non è necessario. Quindi l'inserimento ripetuto in un albero potrebbe richiedere meno sforzo rispetto all'ordinamento di un array.

Quindi abbiamo l'impressione che l'ordinamento di unione naturale eccelle solo in casi speciali ascendenti e discendenti. Che non si può nemmeno dire per un ordinamento rapido.

Sintesi con i casi di test here.

P.S .: si noti che l'uso di alberi per l'ordinamento non è banale. Uno non deve solo fornire una routine di inserimento ma anche una routine che può linearizzare l'albero in un array. Attualmente stiamo usando una routine get_last e una predecessore, che non ha bisogno di uno stack. Ma queste routine non sono O (1) poiché contengono loop.