Come Cache Oblivious è l'ordinamento rapido?

Question

Nel documento Burst sort, l'autore della carta afferma che l'ordinamento rapido non è un algoritmo di ordinamento efficiente per la cache. Come autore menzionato

Tuttavia, alcuni degli svantaggi di quicksort sono ancora carattere present.Each è ispezionato più volte, fino a quando è in una stringa partition.Each pari a perno è ri-letta ogni volta che un personaggio it viene ispezionato e, dopo il primo partizionamento, questi accessi sono in modo casuale. Per un ampio set di stringhe, la percentuale di errori della cache è probabilmente alta.

Ho anche trovato ppt che dice quick sort e merge sort sono cache di algoritmo Incurante ma Wikipedia e few paper affermazione che rapida sorta di cache è molto efficiente.

Non sono in grado di capire i casi in cui l'ordinamento rapido ottiene la mancanza della cache oltre alla mancanza obbligatoria per i dati interi. Qualcuno può spiegare la mancanza rapida della cache di ordinamento in dettaglio?

Answer 1

Il passaggio che hai citato parla principalmente di problemi durante l'ordinamento delle stringhe. Se una serie di stringhe durante quicksort è memorizzata come array come puntatori (che è fondamentalmente l'unico modo semplice per farlo), dopo il primo passaggio di quicksort è possibile che i puntatori memorizzati nelle posizioni vicine nell'array puntino alla memoria posizioni distanti tra loro, anche se la matrice originale di stringhe è stata allocata nella memoria consecutiva. Sembra plausibile che le stringhe di ordinamento possano essere trattate come un problema speciale e che gli algoritmi specializzati possano essere più efficienti in termini di cache.

Se invece si sta ordinando un array di, per esempio, numeri interi, si sta effettivamente confrontando e scambiando i dati nell'array durante il quicksort, e quindi quando si accede a posizioni vicine nell'array si otterranno benefici della cache. In questo caso, la mia comprensione è la stessa di quella che hai trovato su wikipedia e altrove, ovvero, quicksort è abbastanza efficiente nella cache. Fondamentalmente questo è perché ogni passaggio di quicksort elabora la sua porzione dell'array in modo molto locale.