Perché è che ho per lo più sentito parlare Quicksort essere il più veloce algoritmo di ordinamento globale quando timsort (secondo wikipedia) sembrano svolgere molto meglio? Google non sembra aver trovato alcun tipo di confronto.Confronto tra timsort e Quicksort
timsort è altamente ottimizzazione Mergesort, è stabile e più veloce di vecchia mergesort.
quando si confrontano con Quicksort, esso presenta due vantaggi:
Per essere onesto, non credo che il # 1 sia un vantaggio, ma mi ha impressionato.
Ecco vantaggi del Quicksort
Attualmente, Java 7 SDK implementa timsort e una nuova variante di quicksort: ovvero Dual Pivot QuickSort.
Se hai bisogno di un ordinamento stabile, prova il timsort, altrimenti inizia con quicksort.
# 1 * può * essere un enorme vantaggio. Se si mantiene un elenco di dati che è necessario riordinare frequentemente (poiché gli elementi vengono inseriti, aggiunti o modificati), con un algoritmo che consente di riordinare in modo molto economico i dati estremamente utili. Se è utile dipende dalla situazione, certo, ma in alcuni casi è enorme e sembra anche ovvio: le liste quasi ordinate non dovrebbero essere difficili da ordinare. –
@JeremyWest: se si sa che i dati sono già ordinati, è necessario utilizzare la ricerca binaria per inserire nuovi valori. Non ordinarlo più e più volte. –
@EricDuminil La ricerca binaria è veloce, ma gli inserimenti nel mezzo di un array non lo sono. Esistono molte applicazioni in cui la soluzione più semplice (e spesso la più efficiente) consiste nel riordinare una lista prevalentemente ordinata quando ne hai bisogno per essere ordinata, ma per farla diventare altrimenti non ordinata. O casi in cui leggi dati che sono per lo più ordinati, e quindi devi ordinarli. Non sto suggerendo che questa sia * sempre * la soluzione migliore, ma che a volte lo è. Ed è una delle ragioni per cui gli ordinamenti che funzionano bene su liste prevalentemente ordinate sono preferibili, in particolare per le librerie standard. –
Più o meno, ha a che fare con il fatto che Timsort è un algoritmo di ordinamento ibrido. Ciò significa che mentre i due tipi sottostanti che utilizza (Mergesort e Insertion sort) sono entrambi peggiori di Quicksort per molti tipi di dati, Timsort li utilizza solo quando è vantaggioso farlo.
Su un livello leggermente più profondo, come gli stati Patrick87, quicksort è l'algoritmo O (n.) peggiore. La scelta di un buon pivot non è hard, ma garantire un quicksort O (n log n) ha un costo di ordinamento generalmente più lento in media.
Per ulteriori dettagli su timsort, vedere this answer, e il post sul blog collegato. Fondamentalmente si presuppone che la maggior parte dei dati sia già parzialmente ordinata e costruisce "esecuzioni" di dati ordinati che consentono fusioni efficienti mediante mergesort.
In generale quicksort è il miglior algoritmo per la matrice primitiva. Ciò è dovuto alla memoria locale e alla cache.
JDK7 utilizza TimSort per l'array Oggetto. La matrice di oggetti contiene solo riferimento all'oggetto. L'oggetto stesso è memorizzato in Heap. Per confrontare l'oggetto, abbiamo bisogno di leggere l'oggetto dall'heap. È come leggere da una parte dell'heap per un oggetto, quindi leggere in modo casuale l'oggetto da un'altra parte dell'heap. Ci sarà un sacco di cache miss. Immagino per questo motivo che la località di memoria non sia più importante. Questo potrebbe essere il motivo per cui JDK utilizza solo l'array TimSort per l'oggetto, se l'array primitivo.
Questa è solo la mia ipotesi.
Ecco i numeri di riferimento della mia macchina (i7-6700 CPU, 3.4GHz, Ubuntu 16.04, GCC 5.4.0, parametri: SIZE = 100000 e corre = 3):
$ ./demo
Running tests
stdlib qsort time: 12246.33 us per iteration
##quick sort time: 5822.00 us per iteration
merge sort time: 8244.33 us per iteration
...
##tim sort time: 7695.33 us per iteration
in-place merge sort time: 6788.00 us per iteration
sqrt sort time: 7289.33 us per iteration
...
grail sort dyn buffer sort time: 7856.67 us per iteration
Il benchmark deriva dal progetto di Swenson sort in cui ha attuato diversi algoritmi di ordinamento in C. Presumibilmente, le sue implementazioni sono buone abbastanza per essere rappresentativo , ma non li ho investigati.
Quindi davvero non si può dire. I numeri di riferimento rimangono rilevanti per almeno due anni e quindi è necessario ripeterli. Forse, timsort ha battuto qsort waaay nel 2011 quando è stata fatta la domanda, ma i tempi sono cambiati. Oppure qsort era sempre il più veloce, ma il timsort lo batteva su dati non casuali. O il codice di Swenson non è così buono e un programmatore migliore cambierà le sorti in favore di Timsort. O forse faccio schifo e non ho usato il codice corretto CFLAGS durante la compilazione del codice. Oppure ... hai capito il punto.
Con un po 'più di pensiero e di alcuni riferimenti, questo potrebbe essere una buona domanda. –
Perché le persone scelgono di ignorare che quicksort è O (n^2) nel caso peggiore. – Patrick87
Una possibile risposta potrebbe essere: tu parli alle persone sbagliate. Ma come un'altra risposta implicava già: qsort è molto più vecchio, quindi è usato in molte più librerie - e tu sai: non toccare mai un sistema in esecuzione. Se il tempo medio di esecuzione (che significa: nei casi d'uso delle persone che lo usano) non è molto peggiore del tempo di esecuzione di un algoritmo diverso (come timsort) le persone sono troppo pigre (o hanno cose migliori da fare) che cambiare qualcosa, che fa lo stesso nello stesso tempo. E in alcune applicazioni (sembra ad esempio python) il timsort è già predefinito. – flolo