¿Cómo se relaciona el quicksort con el caché?

Question

he visto muchos lugares dicen ordenación rápida es buena ya que se ajusta a cosas relacionadas con la memoria caché, tal como se dice en el wiki

Además, las referencias a memoria secuenciales y localizados de quicksort trabajar bien con un caché

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

¿Alguien podría darme alguna información sobre este reclamo? ¿Cómo se relaciona el quicksort con el caché? Normalmente, ¿qué significa esa caché en la declaración? ¿Por qué el quicksort es mejor para un caché?

Gracias

Answer 1

quicksort cambia la matriz in place - en la matriz en la que está trabajando [a diferencia de la clase de fusión, por ejemplo - que crea una matriz diferente para él]. Por lo tanto, aplica el principio de locality of reference.

La memoria caché se beneficia de múltiples accesos al mismo lugar en la memoria, ya que solo el primer acceso debe tomarse de la memoria; el resto de los accesos se toman de la memoria caché, que es mucho más rápido.

Combinar, por ejemplo, necesita mucha más memoria Los accesos a la memoria RAM (RAM), ya que cada conjunto de accesorios que cree, está accediendo nuevamente a la RAM.

Los árboles son aún peores, ya que es probable que 2 accesos secuenciales en un árbol no estén cerca el uno del otro. [La memoria caché se rellena en bloques, por lo que para los accesos secuenciales: solo el primer byte en el bloque es un "error" y los otros son un "acierto"].

Answer 2

lo que entra en la caché se determina mediante algoritmos que más o menos adivinar lo que va a utilizar en breve sobre la base de lo que está solicitando actualmente. Esto generalmente significa bloques de memoria que están cerca uno del otro, como matrices.

Después de algunas iteraciones, quicksort trabajará con bloques que encajan completamente en la memoria caché, y esto aumenta sustancialmente el rendimiento. (Compare con, digamos, seleccione ordenar, que puede acceder a las ubicaciones de memoria que están muy separadas con la mayoría de las operaciones).

Answer 3

Quicksort es un algoritmo de clasificación in situ. Mueve elementos a la izquierda y a la derecha del pivote mediante el uso de swaps. Cada vez que se produce un intercambio, es probable que la línea de caché se cargue y el intercambio subsiguiente ocurra desde la misma línea de caché.