Perché è quicksort meglio di altri algoritmi di ordinamento in pratica?

cs.stackexchange https://cs.stackexchange.com/questions/3

  •  15-10-2019
  •  | 
  •  

Domanda

In algoritmi standard Naturalmente ci viene insegnato che quicksort è di $ O (n \ log n) $ in media, e $ O (n ^ 2) $ nel peggiore dei casi. Allo stesso tempo, altri algoritmi di ordinamento vengono studiati che sono $ O (n \ log n) $ nel peggiore dei casi (come Mergesort e heapsort ), e il tempo persino lineari nel migliore dei casi (come bubblesort ), ma con alcune ulteriori esigenze di memoria.

Dopo una rapida occhiata alla alcune volte di più in esecuzione è naturale dire che Quicksort non dovrebbe essere il più efficiente come gli altri.

Inoltre, ritengono che gli studenti imparano nei corsi di programmazione di base che la ricorsione non è davvero buona, in generale, perché potrebbe utilizzare troppa memoria, ecc Pertanto (e anche se non si tratta di un vero e proprio argomento), questo dà l'idea che quicksort potrebbe non essere veramente buono, perché è un algoritmo ricorsivo.

Perché, allora, quicksort sovraperformare gli altri algoritmi di ordinamento in pratica? Ha a che fare con la struttura di dati del mondo reale ? Ha a che fare con le opere di memoria modo nei computer? So che alcuni ricordi sono il modo più veloce di altri, ma non so se questo è il vero motivo di questa performance poco intuitivo (se confrontato alle stime teoriche).

Aggiornamento 1: una risposta canonica sta dicendo che le costanti coinvolte nel $ O (n \ log n) $ del caso medio sono più piccoli rispetto alle costanti coinvolte in altri $ O (n \ log n) $ algoritmi. Tuttavia, devo ancora vedere un un'adeguata giustificazione di questo, con calcoli precisi, invece di idee intuitive solo.

In ogni caso, sembra che si verifica la vera differenza, come suggeriscono alcune risposte, a livello di memoria, in cui le implementazioni sfruttano la struttura interna dei computer, utilizzando, ad esempio, che la memoria cache è più veloce di RAM. La discussione è già interessante, ma mi piace ancora di vedere più in dettaglio rispetto alla memoria di gestione, poiché è emerso che il risposta ha a che fare con esso.

Aggiornamento 2: Ci sono diverse pagine web che offrono un confronto tra algoritmi di ordinamento, alcuni più elaborato rispetto ad altri (in particolare sorting-algorithms.com ). Altro che presenta un bel aiuto visivo, questo approccio non risponde alla mia domanda.

È stato utile?

Soluzione

Risposta breve

L'argomento efficienza della cache è già stato spiegato in dettaglio. Inoltre, v'è un argomento intrinseca, perché Quicksort è veloce. Se attuata come con due “puntatori” crossing, esempio qui , i cicli interni hanno un corpo molto piccolo. Poiché questo è il codice eseguito più spesso, questo ripaga.

Long risposta

Prima di tutto,

Il caso medio non esiste!

Come meglio e nel peggiore dei casi, spesso sono gli estremi che si verificano raramente, in pratica, l'analisi media caso è fatto. Ma qualsiasi analisi media caso assume alcuna distribuzione di input ! Per l'ordinamento, la scelta tipica è la modello di permutazione casuale (tacitamente assunto su Wikipedia).

Perché $ O $ -Notation?

Scartando costanti nelle analisi degli algoritmi è fatto per una ragione principale: se sono interessato a esattamente i tempi di utilizzo Ho bisogno (relative) costi di tutte le operazioni di base coinvolte (anche ignorando ancora problemi di caching, pipelining nei processori moderni ...). analisi matematica può count la frequenza viene eseguita ogni istruzione, ma tempi di esecuzione delle singole istruzioni dipendono dettagli del processore, per esempio se un numero intero moltiplicazione a 32 bit richiede più tempo aggiunta.

Ci sono due vie d'uscita:

  1. Fissare qualche modello di macchina.

    Questo viene fatto in Don Knuth 's serie di libri “The Art di Computer Programming” per un artificiale‘tipico del computer’inventato dall'autore. Nel volume di 3 a trovare esatto caso medio risultati per molti algoritmi di ordinamento, ad esempio

    • Quicksort: $ 11,667 (n + 1) \ ln (n) -1.74n-18.74 $
    • Mergesort: $ il 12,5 n \ ln (n) $
    • Heapsort: $ 16 n \ ln (n) + 0,01 N $
    • InsertionSort: $ 2.25n ^ 2 + 7.75n-3LN (n) $ Tempi di esecuzione di diversi algoritmi di ordinamento
      [ ]

    Questi risultati indicano che Quicksort è più veloce. Ma, si è dimostrato solo sulla macchina artificiale di Knuth, non implica necessariamente qualcosa per dire il vostro PC x86. Si noti inoltre che gli algoritmi riferiscono diverso per piccoli ingressi:
    Tempi di esecuzione delle diverse algoritmi di ordinamento per i piccoli ingressi
    [ ]

  2. Analizzare astratti le operazioni di base .

    Per fare un confronto basato l'ordinamento, questo di solito è swap e confronti chiave . Nei libri di Robert Sedgewick, per esempio “Algoritmi” , questo approccio è perseguito. Vi si trova

    • Quicksort: $ 2n \ ln (n) $ confronti e $ \ frac13n \ ln (n) $ swap in media
    • Mergesort: $ 1.44n \ ln (n) $ confronti, ma fino a $ 8.66n \ ln (n) $ accessi array (Mergesort non è Swap basa, in modo da non possiamo contare che)
      • .
    • InsertionSort:. $ \ Frac14n ^ 2 $ confronti e $ \ frac14n ^ 2 $ swap in media

    Come potete vedere, questo non consente facilmente il confronto di algoritmi come l'esatta analisi di runtime, ma i risultati sono indipendenti dai dettagli della macchina.

Altre distribuzioni di input

Come osservato in precedenza, casi medi sono sempre rispetto a qualche distribuzione di ingresso, quindi si potrebbe considerare quelle diverse permutazioni casuali. Per esempio. la ricerca è stato fatto per Quicksort con elementi uguali e c'è bell'articolo sul funzione di ordinamento standard Java

Altri suggerimenti

Ci sono diversi punti che possono essere fatte riguardo a questa domanda.

Quicksort è di solito veloce

Sebbene Quicksort trovi caso peggiore $ O (n ^ 2) $ comportamento, di solito è veloce: supponendo selezione perno casuale, c'è una grande possibilità prendiamo qualche numero che separa l'ingresso in due sottoinsiemi di dimensioni simili, che è esattamente ciò che vogliamo avere.

In particolare, anche se prendiamo un perno che crea un 10% -90% diviso ogni 10 divisioni (che è una frazione di meh), ed un elemento di 1 - $ n-1 $ elemento di divisione in caso contrario (che è il peggiore dividere è possibile ottenere), il nostro tempo di esecuzione è ancora $ O (n \ log n) $ (nota che questo sarebbe far saltare in aria le costanti ad un punto che merge sort è probabilmente più veloce però).

Quicksort è solitamente più veloce della maggior parte dei tipi

Quicksort è di solito più veloce di tipi che sono più lento di $ O (n \ log n) $ (diciamo, L'ordinamento per inserzione con la sua $ O (n ^ 2) $ tempo di esecuzione), semplicemente perché per gran $ n $ il loro funzionamento volte esplodono.

Un motivo per cui buona Quicksort è così veloce, in pratica, rispetto alla maggior parte altri $ O (n \ log n) $ algoritmi come Heapsort, è perché è relativamente cache-efficiente. Il suo tempo di esecuzione è in realtà $ O (\ frac {n} {B} \ log (\ frac {n} {B})) $, dove $ B $ è la dimensione del blocco. Heapsort, d'altra parte, non ha un tale aumento di velocità:. Non è affatto la memoria che accede cache-efficiente

La ragione di questa efficienza cache è che scandisce linearmente l'ingresso e pareti linearmente l'ingresso. Questo significa che possiamo sfruttare al massimo ogni carico di cache che facciamo come leggiamo ogni numero di carico che nella cache prima di invertire quella cache per un altro. In particolare, l'algoritmo è cache-ignaro, che dà buone prestazioni della cache per ogni livello di cache, che è un'altra vittoria.

efficienza della cache potrebbe essere ulteriormente migliorato per $ O (\ frac {n} {B} \ log _ {\ frac {M} {B}} (\ frac {n} {B})) $, dove $ M $ è la dimensione della nostra memoria principale, se usiamo $ k $ -way Quicksort. Notare che Mergesort ha anche la stessa cache-efficienza Quicksort, e la sua versione k-way infatti ha prestazioni migliori (attraverso costanti inferiori) se la memoria è un vincolo grave. Questo dà luogo al punto successivo:. Avremo bisogno di confrontare Quicksort per Mergesort su altri fattori

Quicksort è di solito più veloce rispetto Mergesort

Questo confronto è del tutto sui fattori costanti (se consideriamo il caso tipico). In particolare, la scelta è tra una scelta ottimale del perno per Quicksort contro la copia dell'intero ingresso per Mergesort (o la complessità dell'algoritmo necessaria per evitare questa copia). Si scopre che il primo è più efficiente:. Non c'è nessuna teoria alla base di questo, succede solo per essere più veloce

Si noti che Quicksort farà più chiamate ricorsive, ma allocando lo spazio di stack è a buon mercato (quasi priva di fatto, fino a quando non soffiare la pila) e si ri-usa. L'assegnazione di un blocco gigante sul mucchio (o il disco rigido, se $ n $ è davvero di grandi dimensioni) è un po 'più costoso, ma entrambi sono $ O (\ log n) $ spese generali che impallidiscono in rispetto al $ O (n) $ di lavoro di cui sopra.

Infine, nota che Quicksort è leggermente sensibile all'ingresso che sembra essere nel giusto ordine, nel qual caso può saltare alcuni swap. Mergesort non ha tali ottimizzazioni, il che rende anche Quicksort un po 'più veloce rispetto a mergesort.

Usa il tipo che si adatta alle vostre esigenze

In conclusione: nessun algoritmo di ordinamento è sempre ottimale. Scegliere quale si adatta alle vostre esigenze. Se avete bisogno di un algoritmo che è il più veloce per la maggior parte dei casi, e non ti dispiace che potrebbe finire per essere un po 'lento in rari casi, e non hai bisogno di una scuderia sorta, utilizzare Quicksort. In caso contrario, utilizzare l'algoritmo che si adatta alle tue esigenze migliori.

In una delle esercitazioni di programmazione della mia università, abbiamo chiesto agli studenti di confrontare le prestazioni di quicksort, mergesort, insertion sort vs Python incorporato list.sort (chiamato timsort ). I risultati sperimentali mi ha sorpreso profondamente in quanto il built-in list.sort eseguito molto meglio di altri algoritmi di ordinamento, anche con istanze che hanno reso facilmente Quicksort, incidente Mergesort. Quindi è prematuro concludere che il solito implementazione Quicksort è la migliore nella pratica. Ma sono sicuro che ci molto meglio implementazione di quicksort, o qualche versione ibrida di esso là fuori.

Questo è un bel articolo di blog da David R. MacIver spiegando come timsort una forma di Mergesort adattiva.

Credo che uno dei motivi principali per cui QuickSort è così veloce rispetto ad altri algoritmi di ordinamento è perché è cache-friendly. Quando QS elabora un segmento di un array, accede elementi all'inizio e fine del segmento, e si muove verso il centro del segmento.

Quindi, quando si inizia, si accede al primo elemento della matrice e un pezzo di memoria ( “location”) viene caricato nella cache. E quando si tenta di accedere al secondo elemento, è (molto probabilmente) già nella cache, quindi è molto veloce.

Altri algoritmi come heapsort non funzionano in questo modo, saltano nella matrice molto, che li rende più lento.

altri hanno già detto che l'asintotico medio runtime di Quicksort è migliore (nella costante) di quella di altri algoritmi di ordinamento (in certi ambienti).

Che cosa significa? Assumere qualsiasi permutazione è scelto a caso (supponendo distribuzione uniforme). In questo caso, i metodi di selezione tipico perno prevedono perni che in attesa dividere l'elenco / matrice all'incirca a metà; questo è ciò che ci porta fino a $ \ cal {} O (n \ log n) $. Ma, in aggiunta, fusione soluzioni parziali ottenuti per recursing richiede solo tempo costante (al contrario di tempo lineare nel caso di Mergesort). Naturalmente, separando l'ingresso in due liste secondo il perno è in tempo lineare, ma spesso richiede pochi swap reali.

Si noti che ci sono molte varianti di Quicksort (vedi tesi di esempio Sedgewick). Essi svolgono in modo diverso su diverse distribuzioni di input (uniforme, quasi allineati, quasi inversamente ordinato, molti duplicati, ...), e altri algoritmi potrebbero essere meglio per un po '.

Un altro fatto degno di nota è che Quicksort è lento su brevi ingressi rispetto agli algoritmi Simper con meno overhead. Pertanto, buone biblioteche non recurse giù per le liste di lunghezza, ma si utilizzano (per esempio) insertion sort se la lunghezza di ingresso è più piccolo di alcuni $ k \ circa 10 $.

In confronto ad altri algoritmi di ordinamento basato sui confronti con $ O (n \ lg n) $ complessità temporale, quick-sort è spesso considerato migliore rispetto ad altri algoritmi come merge-sort perché è un algoritmo sul posto di smistamento. In altre parole, non abbiamo bisogno di memoria (molto di più) per memorizzare i membri della matrice.

ps: per la precisione, essendo meglio di altri algoritmi è compito dipendente. Per alcuni compiti che potrebbe essere migliore di utilizzare altri algoritmi di ordinamento.

Vedi anche:

Anche se quicksort ha un momento peggiore caso di esecuzione di $ \ Theta (n ^ 2) $, quicksort è considerato il migliore di ordinamento, perché è molto efficiente in media: il suo tempo di esecuzione previsto è di $ \ Theta (n \ log n) $ in cui le costanti sono molto piccole rispetto ad altri algoritmi di ordinamento. Questa è la ragione principale per l'utilizzo rapido sorta rispetto ad altri algoritmi di ordinamento.

La seconda ragione è che si esegue in-place smistamento e funziona molto bene con gli ambienti virtuali di memoria.

UPDATE: : (dopo i commenti di Svick di Janoma e)

Per illustrare meglio questo Vi faccio un esempio che utilizza merge sort (perché merge sort è l'algoritmo di ordinamento successivo ampiamente adottata dopo quick sort, credo) e che vi dica dove le costanti aggiuntivi provengono (al meglio delle mie conoscenze e perché penso rapida tipo è meglio):

Si consideri il seguente seqence: 

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

Se si cura completamente guarda come l'ultima tappa che sta accadendo, prima 12 viene confrontato con 8 e 8 è più piccolo così si va per primo. Ora 12 è di nuovo rispetto al 21 e 12 va successivo e così via e così via. Se si prende l'unione finale vale a dire 4 elementi con 4 altri elementi, si incorre in un sacco di confronti extra come costanti che non sorge in Quick Sort. Questo è il motivo per cui rapido tipo è preferito.

La mia esperienza di lavoro con i dati del mondo reale è che Quicksort è una scelta sbagliata . Quicksort funziona bene con dati casuali, ma i dati del mondo reale è il più delle volte non è casuale.

Nel 2008 ho rintracciato un bug software che pende per l'utilizzo del quicksort. Qualche tempo dopo ho scritto semplici implentations di inserzione, quicksort, mucchio ordinamento e merge sort e testato questi. Il mio merge sort ha superato tutti gli altri mentre si lavora su grandi insiemi di dati.

Da allora, merge sort è il mio algoritmo di ordinamento di scelta. E 'elegante. E 'semplice da implementare. Si tratta di una sorta stabile. Non è così degenerata al comportamento quadratica come quicksort fa. Passo al insertion sort per ordinare piccoli array.

In molte occasioni ho trovato la mia auto di pensare che una data implementazione funziona sorprendentemente bene per Quicksort solo per scoprire che in realtà non è quicksort. Talvolta l'attuazione commuta tra Quicksort e altro algoritmo e talvolta non usa quicksort affatto. Come esempio, le funzioni di qsort glibc () effettivamente usi fondono ordinamento. Solo se l'allocazione dello spazio di lavoro non lo fa ricadere sul posto Quicksort che un codice per il commento chiama "l'algoritmo più lento"

.

Modifica: linguaggi di programmazione come Java, Python e Perl anche usare merge sort, o più precisamente un derivato, come ad esempio timsort o merge sort per grandi insiemi e insertion sort per piccoli insiemi. (Java utilizza anche quicksort dual-perno, che è più veloce di quicksort pianura.)

1 - Breve ordinamento è inplace (. Non ha bisogno memmory in più, di diverso da una quantità costante)

2 -. Breve tipo è più facile da implementare di altri algoritmi di ordinamento efficiente

3 -. rapida ha una sorta piccoli fattori costanti in è il momento di altri algoritmi di ordinamento efficiente esecuzione

Aggiornamento: Per merge sort, è necessario fare un po ' "la fusione", che ha bisogno di serie in più (s) per memorizzare i dati prima di fondersi; ma in quick sort, non lo fai. Ecco perché rapido tipo è sul posto. Ci sono anche alcuni confronti aggiuntivi realizzati per fusione che aumentano i fattori costanti nel merge sort.

In quali condizioni è uno specifico algoritmo di ordinamento in realtà quello più veloce?

1) Quando è implementata in modo parallelo in hardware, non deve necessariamente avere una latenza ragionevolmente basso mentre richiede il minor numero possibile di cancelli? Sì -> usare un sorter bitonico o Batcher pari-dispari Mergesort, la latenza è di $ \ Theta (\ log (n) ^ 2) $ e il numero di comparatori e multiplexer è $ \ Theta (n \ cdot \ log (n) ^ 2) $.

2) Quanti valori diversi può avere ogni elemento? Lattine ogni valore possibile hanno assegnato un posto unico nella memoria o nella cache Sì -> conteggio uso ordinamento o radix sort, quelli di solito hanno un tempo di esecuzione lineare di $ \ Theta (n \ cdot k) $ (count ordinamento) o $ \ Theta (n \ cdot m) $ (bucket sort), ma rallentare per un gran numero di valori diversi, da $ k = 2 ^ {\ # numero \ _OF \ _Possible \ _values} $ e $ m = \ #maximum \ _length \ _OF \ _keys $.

3) Se la struttura dei dati sottostanti sono costituiti da elementi legati? Sì -> allways uso in luogo merge sort. Ci sono sia facili da implementare dimensione fissa o adattiva (aka naturale) bottom-up in atto di unione i tipi di diversi arietà per strutture dati collegate, e dal momento che non richiedono mai copiare tutti i dati in ogni fase e non hanno mai bisogno di ricorsioni sia, sono più veloce di tutti gli altri tipi confronto a base di carattere generale, ancora più veloce rispetto a quick sort.

4) Se la necessità di smistamento sia stabile? Sì -> uso merge sort, sia in luogo o meno, di dimensioni fisse o adattativo, a seconda della struttura dati sottostante e il tipo di dati da aspettarsi, anche nei casi in cui pratica sorta altrimenti essere preferito, come stabilizzare un ordinamento arbitrario algoritmo richiede $ \ Theta (n) $ memoria aggiuntiva nel peggiore dei casi costituito da indici originali, che ha anche bisogno di essere tenuti in sincronia con l'scambio che deve essere eseguita sui dati di input, in modo che ogni guadagno di prestazioni che rapida sorta forza hanno oltre merge sort è probabilmente ostacolato.

5) Può la dimensione dei dati sottostanti essere vincolati ad un piccolo e medie dimensioni? per esempio. È n <10.000 ... 100.000.000 (a seconda della architettura sottostante e la struttura dei dati)? Sì -> utilizzare sorta bitonico o Batcher odd-even Mergesort. Goto 1)

6) Potete risparmiare un altro $ \ Theta (n) $ memoria? Sì -> a) Se i dati di input sono costituiti da grandi pezzi di già ordinato dati sequenziali? -> uso adattivo (aka naturale) merge sort o tim sorta Sì -> b) Se i dati di input sono costituiti per lo più da elementi che sono quasi nel posto giusto? -> uso bubble sort o insertion sort. Se si teme loro $ \ theta (n ^ 2) $ complessità in tempo (che è patologico per i dati quasi ordinato), forse passare ad shell sort con (quasi) sequenza asintoticamente ottimale di lacune, alcune sequenze che il rendimento $ \ theta ( n \ cdot \ log (n) ^ 2) $ momento peggiore caso di esecuzione sono noti, o forse provare a pettine sorta. Non sono sicuro che sia shell sort o comb sort avrei eseguire ragionevolmente buono in pratica.

No -> 7) Si può risparmiare un altro \ Theta (\ log (n)) $ memoria $? Sì -> a) Se la struttura di dati undelying consentire l'accesso sequenziale diretto o meglio? Sì -> Ha consentono solo una singola sequenza di accessi in lettura / scrittura alla volta fino alla fine dei dati è stata raggiunta (accesso al nastro per esempio diretto)? Sì -> i) utilizzo merge sort, ma non v'è alcun modo ovvio per fare questo caso sul posto, quindi potrebbe richiedere ulteriori $ \ Theta (n) $ memoria. Ma se avete tempo e le palle per farlo, c'è un modo per unire 2 matrici in $ \ Theta (n) $ tempo utilizzando solo $ \ Theta (\ log (n)) $ spazio in modo stabile, secondo Donald E. Knuth "The Art of Computer Programming, Volume 3: ordinamento e ricerca", l'esercizio fisico 5.5.3. afferma che esiste un algoritmo di L. Trabb-Pardo che fa così. Tuttavia, dubito che questo sarebbe stato più veloce rispetto alla versione mergesort ingenui o il Quicksort dal caso di cui sopra. No, consente più accessi contemporanei ad una sequenza di dati (ad esempio non è un drive nastro) -> ii) uso Quicksort, per scopi pratici voglio raccomandare o un randomized o uno mediana approssimata. Se si è attenti a $ patologica \ Theta (n ^ 2) $ i casi, è possibile utilizzare intro sorta. Se si è decisa a comportamento deterministico, è possibile utilizzare la mediana-di-mediana algoritmo per selezionare l'elemento di rotazione, richiede $ \ Theta (n) $ tempo e la sua attuazione ingenua richiede $ \ Theta (n) $ spazio (parallelizzabile ), che può essere implementato per richiedere solo $ \ Theta (\ log (n)) $ spazio (non parallelizzabile). Tuttavia, l'algoritmo mediana-di-mediana ti dà un quicksort deterministico che ha worst-case $ \ Theta (n \ cdot \ log (n)) $ run-time. No -> sei fregato (mi dispiace, abbiamo bisogno di almeno 1 modo di accedere a ogni elemento di dati una volta)

No -> 8) Potete risparmiare una piccola quantità costante di memoria? Sì -> La struttura dati sottostante consentire per l'accesso casuale? Sì -> uso heapsort, ha un ottima fase di esecuzione asintotico di $ \ Theta (n \ cdot \ log (n)) $, ma triste coerenza della cache e non parallelizzare bene. No -> si sono avvitati No -> si sono avvitati

suggerimenti di attuazione per il Quicksort:

1) Naive Quicksort binario richiede $ \ Theta (n) $ memoria aggiuntiva, tuttavia, è relativamente facile ridurre che fino a $ \ Theta (\ log (n)) $ riscrivendo l'ultima chiamata ricorsione in un ciclo . Fare lo stesso per quicksorts k-ary per k> 2 richiede $ \ Theta (n ^ {\ log_k (k-1)}) $ spazio (secondo il teorema), in modo da Quicksort binario richiede la minor quantità di memoria, ma sarei lieto di sentire se qualcuno sa se il Quicksort k-ary per k> 2 potrebbe essere più veloce di Quicksort binario su alcuni reale configurazione mondo.

2) Non esiste bottom-up, iterativo varianti di quicksort, ma AFAIK, hanno gli stessi asintotico confini spazio-temporali come un top-down quelli, con gli ulteriori lati verso il basso di essere di difficile applicazione (es esplicitamente gestione coda). La mia esperienza è che per scopi pratici, quelli non sono mai la pena di considerare.

suggerimenti di attuazione per Mergesort:

1) bottum-up Mergesort è sempre più veloce di Mergesort top-down, in quanto richiede nessuna chiamata ricorsione.

2) il Mergesort molto naif può essere accelerato utilizzando un doppio buffer e passare il buffer invece di copiare schiena dati dalla matrice temporale dopo ogni passaggio.

3) Per molti dati del mondo reale, Mergesort adattivo è molto più veloce di un Mergesort di dimensione fissa.

4) l'algoritmo di unione può essere facilmente parallelized suddividendo i dati di ingresso in k parti approssimativamente le stesse dimensioni. Ciò richiederà riferimenti k in dati, ed è una buona cosa per scegliere k tale che tutti i k (o c * k per una piccola costante c> = 1) in forma nella gerarchia di memoria più vicino (di solito L1 cache di dati). Scegliere il più piccolo di k elementi del modo ingenuo (ricerca lineare) batte $ \ Theta (k) $ tempo, mentre la costruzione di un min-heap all'interno di questi k elementi e scegliendo il più piccolo richiede solo ammortizzato $ \ Theta (\ log ( k)) $ tempo (raccogliendo il minimo è $ \ theta (1) $ naturalmente, ma occorre fare una piccola manutenzione come elemento viene rimosso e sostituito con un altro in ogni passaggio). La fusione parallelizzato richiede sempre $ \ Theta (n) $ memoria indipendentemente k.

Da ciò che ho scritto, è chiaro che quicksort spesso non è l'algoritmo più veloce, tranne quando le seguenti condizioni si applicano tutto:

1) ci sono più di un "pochi" possibili valori

2) la struttura di dati sottostante non è collegato

3) non abbiamo bisogno di un ordine stabile

4) i dati è abbastanza grande che il lieve sub-ottimale asintotica run-time di un sorter bitonico o Batcher odd-even Mergesort calci in

5) i dati non quasi allineati e non consiste in grandi parti già ordinati

6) possiamo accedere alla sequenza di dati contemporaneamente da più luoghi

7) { scrive memoria sono particolarmente costosi (perché tale svantaggio principale di mergesort), quanto rallenta l'algoritmo di là probabile scissione sub-ottimale del Quicksort. } o { noipuò avere solo $ \ Theta (\ log (n)) $ memoria aggiuntiva, $ \ Theta (n) $ è troppo (ad esempio archiviazione esterna) }

P.S .: Qualcuno necessità di aiutarmi con la formattazione del testo.

La maggior parte delle cernite metodi devono spostare i dati intorno a passi brevi (ad esempio, merge sort apporta modifiche a livello locale, quindi si fonde questo piccolo pezzo di dati, quindi si fonde uno più grande. ..). Di conseguenza, è necessario molti movimenti di dati se i dati è lontano dalla sua destinazione.

Quicksort, sugli altri tentativi laterali di intercambiare i numeri che si trovano nella prima parte della memoria e sono grandi, con i numeri che si trovano nella seconda parte della matrice e sono di piccole dimensioni (se si ordina $ a \ Le B $, l'argomento è lo stesso in senso inverso), in modo da ottenere rapidamente allocati vicino alla loro destinazione finale.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top