Quicksort dual pivot di fronte a costosi swap

Has anyone tested dual pivot quicksort performance with expensive-to-swap elements? It seems that in this case, it should massively underperform compared to standard quicksort.

...

During some research I also came upon dual pivot quicksort, which is the current implementation of quicksort in Java standard library. Generally it claims that it is always at least as good as standard quicksort, and empirical testing seemed to support it. (Which is the reason it is the current implementation.)

Fai attenzione a interpretare queste affermazioni. Molte volte, il confronto è contro un'implementazione quicksort a "pivot" a singolo pivot (solitamente chiamata "classico" (o come dici tu, "standard") quicksort) che usa un pivot casuale. Questo a volte viene anche mascherato usando notazioni insolite. Per esempio. riportando 2 N ln N confronti per quicksort "single-pivot". Ciò si traduce in confronti di 1.386 N log (base 2) N, che è caratteristico della selezione di un singolo elemento casuale come pivot. La selezione casuale dei pivot non solo ha scarse prestazioni (anche la peggiore esecuzione dell'implementazione quicksort a pivot singolo di qsort in uso diffuso è più vicina a 1,15 log N (base 2) N confronti), ma porta a difficoltà- per mantenere il codice (si desidera replicare un bug, quale implementazione della generazione di numeri casuali è stata utilizzata e qual era il suo stato al momento in cui si è verificato il bug?).

However, it seems that no STL implementation uses dual pivot quicksort for the quicksort phase of introsort, which made me wonder why. After more research I found this paper. It says that while dual pivot quicksort performs on average 5% less comparisons, it performs significantly more swaps. (Approximately 80% more) Obviously, since Java has only primitives and reference types, swapping is always cheap. (Even so, it uses this sort only for primitives, because it is not stable)

Ancora una volta, fai attenzione con questi confronti. "5% in meno" in quali condizioni specifiche ? Nelle migliori condizioni possibili (zero-costo, "perfetto" pivot (mediana per single-pivot, terzili per dual-pivot)) e input casuale uniformemente distribuito, quicksort dual-pivot utilizzerà più del 5% more confronti rispetto a quicksort single-pivot (5/3 N log (base 3) N ~~ 1.052 N log (base 2) N vs. 1 N log (base 2) N. Lo swap dipende anche dall'implementazione. pivot quicksort (condizioni come sopra specificato) prevede l'utilizzo di 0,25 N log (base 2) N swap se implementato in modo efficiente Un'implementazione dual-pivot potrebbe teoricamente raggiungere 1/3 N log (base 3) N ~~ 0.21 N log (base 2) N swaps (16% in meno), ma richiede una grande quantità di contabilità, più tipico sarebbe 0,28 N log (base 2) N (12% in più). Si noti che ci sono molti modi a basso costo, altamente efficaci per approssimare la mediana (cioè pseudomediano) per quicksort a perno singolo. Non tanto per i terzili.

Probabilmente non si vorrebbe usare l'introsort di Musser (limite di profondità della ricorsione) con uno schema multi-pivot. La profondità di ricorsione non è ben definita in questo caso (si consideri che dual-pivot può comportarsi come un singolo pivot se i due pivot hanno valori vicini, quindi si dovrebbe confrontare con qualche multiplo del logaritmo di base 2 o di base 3 di dimensione dell'array?). L'introsort di Valois (che mescola in modo casuale gli elementi) ha altri problemi (vedi sopra ripetere i bug).

It also seems that at least part of the advantage of dual pivot quicksort is in its improved cache behaviour (Because it divides into smaller subarray that can fit into cache faster).

Questo è stato congetturato, ma non definitivamente dimostrato. Potrebbe essere una falsa pista; quicksort è per lo più cache-ignaro in quanto gli accessi tendono ad essere sequenziali.

So I wanted to see whether someone already tested standard quicksort vs dual pivot quicksort when elements are expensive to swap and has the numbers (and possibly source) lying around, or whether I will have to test this myself.

Il codice (in C) incluso un framework di test al link e i problemi multi-pivot sono discussi in dettaglio in link . Il codice include due implementazioni dual-pivot e molte implementazioni single-pivot. Un'implementazione dual-pivot altamente sintonizzata è in effetti un po 'più di 1.052 confronti N log N asintoticamente, e diverse implementazioni single-pivot sono inferiori, più vicine ai confronti 1 N log N (il documento include diversi grafici delle prestazioni). Non ho tentato di minimizzare gli swap nel codice dual-pivot; la contabilità necessaria è davvero onerosa, e poiché i confronti superano gli swaps, gli swap dovrebbero essere veramente costosi per essere un fattore, e in tal caso si potrebbe probabilmente usare l'indirezione (ridisporre i puntatori ai dati). / p>     

Probabilmente la risposta no, perché è abbastanza ovvio che non avrebbe importanza se non in rari casi.

Supponiamo che la ragione per cui gli swaps siano costosi è che si stanno ordinando oggetti di grandi dimensioni, contenuti in un database o accessibili tramite un'API. Indipendentemente da ciò, questi oggetti hanno le chiavi e (secondo la tua dichiarazione) le chiavi contengono abbastanza informazioni da poter essere confrontate a basso costo.

Assicurati semplicemente che ogni chiave contenga un riferimento all'oggetto sottostante. Se necessario, collega un puntatore o un indice a ciascun tasto. Quindi ordina per qualsiasi metodo disponibile - ovviamente non importa perché gli swap sono la parte costosa.

Ora esegui uno scambio chase-the-tail sui dati ordinati. Inizia con la prima chiave, scambialo nella prima posizione, scambia l'oggetto che era lì nella sua posizione e così via. Avrai eseguito esattamente il numero minimo di swap richiesto per ordinare i dati.

In altre parole, per gli swap costosi esiste un semplice algoritmo che garantisce l'esecuzione degli swap minimi, che funziona indipendentemente dall'algoritmo di ordinamento. Gli unici algoritmi di ordinamento che ci interessa analizzare sono quelli in cui i confronti sono costosi.