In che modo Quicksort è correlato alla cache?

Question

Ho visto molti posti dicono quicksort è un bene perché si adatta al roba cache-correlati, come ha detto in wiki

Inoltre, i riferimenti di memoria sequenziali e localizzate del Quicksort funzionano bene con una cache

http://en.wikipedia.org/wiki/Quicksort

Qualcuno potrebbe darmi qualche informazione su questo reclamo? In che modo Quicksort è correlato alla cache? Normalmente cosa significa la cache nella dichiarazione? Perché quicksort è migliore per una cache?

Grazie

Answer 1

quicksort cambia l'array in posizione - nell'array su cui sta lavorando [a differenza dell'ordinamento di merge, ad esempio, che crea un array diverso per questo]. Pertanto, applica il principio di locality of reference.

Cache beneficia di più accessi allo stesso posto nella memoria, dal momento che solo il primo accesso deve essere effettivamente preso dalla memoria - il resto degli accessi sono presi dalla cache, che è molto più veloce l'accesso alla memoria.

Unisci ordinamento per esempio - richiede molto più spazio di memoria [RAM] - poiché ogni array accessorio che crei - accede nuovamente alla RAM.

Gli alberi sono anche peggio - dal momento che 2 accessi sequenziali in un albero non sono probabilmente vicini l'uno all'altro. [La cache è piena di blocchi, quindi per accessi sequenziali - solo il primo byte nel blocco è un "miss" e gli altri sono un "hit"].

Answer 2

ciò che accade nella cache è determinato da algoritmi che più o meno indovinare che cosa hai intenzione di utilizzare presto in base a ciò che si sta richiedendo. Questo di solito significa blocchi di memoria vicini tra loro, come gli array.

Dopo alcune iterazioni, quicksort funzionerà con blocchi che si adattano completamente alla cache e questo aumenta notevolmente le prestazioni. (Confronta con, diciamo, seleziona l'ordinamento, che può accedere a posizioni di memoria molto distanti con la maggior parte delle operazioni.)

Answer 3

Quicksort è un algoritmo di ordinamento sul posto. Sposta gli elementi a sinistra e a destra del pivot usando gli swap. Ogni volta che si verifica uno scambio, è probabile che la linea della cache sia caricata e lo swap successivo si verifichi dalla stessa riga della cache.