Ordenación de distribución sin tener en cuenta la memoria caché

El algoritmo de ordenación por distribución sin tener en cuenta la memoria caché es un algoritmo de ordenación basado en comparación . Es similar al quicksort , pero es un algoritmo sin tener en cuenta la memoria caché , diseñado para un entorno en el que la cantidad de elementos a ordenar es demasiado grande para caber en una memoria caché donde se realizan las operaciones. En el modelo de memoria externa , la cantidad de transferencias de memoria que necesita para realizar una ordenación de elementos en una máquina con una memoria caché de tamaño y líneas de memoria caché de longitud es , bajo el supuesto de caché alta de que . Se ha demostrado que esta cantidad de transferencias de memoria es asintóticamente óptima para las ordenaciones por comparación. Esta ordenación por distribución también logra la complejidad de tiempo de ejecución asintóticamente óptima de . ${\displaystyle N}$${\displaystyle Z}$${\displaystyle L}$${\displaystyle O({\frac {N}{L}}\log _{Z}N)}$${\displaystyle Z=\Omega (L^{2})}$${\displaystyle \Theta (N\log N)}$

La ordenación por distribución opera sobre una matriz contigua de elementos. Para ordenar los elementos, realiza lo siguiente: ${\displaystyle N}$

1. Particiona la matriz en submatrices contiguas de tamaño y ordena recursivamente cada submatriz.${\displaystyle {\sqrt {N}}}$${\displaystyle {\sqrt {N}}}$
2. Distribuya los elementos de las submatrices ordenadas en contenedores, cada uno de un tamaño como máximo tal que para cada i desde 1 hasta q-1, cada elemento del contenedor no sea mayor que cualquier elemento en Este paso de distribución es el paso principal de este algoritmo y se cubre con más detalle a continuación.${\displaystyle q\leq {\sqrt {N}}}$${\displaystyle B_{1},B_{2},\ldots ,B_{q}}$${\displaystyle 2{\sqrt {N}}}$${\displaystyle B_{i}}$${\displaystyle B_{i+1}.}$
3. Ordenar recursivamente cada contenedor.
4. Muestra la concatenación de los buckets.

Como se mencionó en el paso 2 anterior, el objetivo del paso de distribución es distribuir las submatrices ordenadas en q contenedores . El algoritmo del paso de distribución mantiene dos invariantes. La primera es que cada contenedor tiene un tamaño como máximo en cualquier momento, y cualquier elemento en el contenedor no es más grande que cualquier elemento en el contenedor. La segunda es que cada contenedor tiene un pivote asociado , un valor que es mayor que todos los elementos en el contenedor. ${\displaystyle B_{1},B_{2},\ldots ,B_{q}.}$${\displaystyle 2{\sqrt {N}}}$${\displaystyle B_{i}}$${\displaystyle B_{i+1}.}$

Inicialmente, el algoritmo comienza con un cubo vacío con pivote . A medida que llena los cubos, crea nuevos cubos dividiendo un cubo en dos cuando se llenaría demasiado (al tener al menos elementos colocados en él). La división se realiza ejecutando el algoritmo de búsqueda de mediana de tiempo lineal y particionando en función de esta mediana. El pivote del cubo inferior se establecerá en la mediana encontrada, y el pivote del cubo superior se establecerá en el mismo que el cubo antes de la división. Al final del paso de distribución, todos los elementos están en los cubos y las dos invariantes seguirán siendo válidas. ${\displaystyle \infty }$${\displaystyle (2{\sqrt {N}}+1)}$

Para lograr esto, cada submatriz y contenedor tendrá un estado asociado. El estado de una submatriz consta de un índice next del siguiente elemento que se leerá de la submatriz y un número de contenedor bnum que indica en qué índice de contenedor se debe copiar el elemento. Por convención, si se han distribuido todos los elementos de la submatriz. (Tenga en cuenta que cuando dividimos un contenedor, tenemos que incrementar todos los valores bnum de todas las submatrices cuyo valor bnum sea mayor que el índice del contenedor que se divide). El estado de un contenedor consta del valor del pivote del contenedor y la cantidad de elementos que hay actualmente en el contenedor. ${\displaystyle bnum=\infty }$

Considere la siguiente estrategia básica: itere a través de cada submatriz, intentando copiar su elemento en la posición next . Si el elemento es más pequeño que el pivote del contenedor bnum , colóquelo en ese contenedor, lo que posiblemente genere una división del contenedor. De lo contrario, incremente bnum hasta que se encuentre un contenedor cuyo pivote sea lo suficientemente grande. Aunque esto distribuye correctamente todos los elementos, no muestra un buen rendimiento de caché.

En cambio, el paso de distribución se realiza en un divide y vencerás recursivo. El paso se realizará como una llamada a la función distribuir , que toma tres parámetros i, j y m. distribuir (i, j, m) distribuirá elementos desde el i-ésimo hasta el (i+m-1)-ésimo subarreglo en grupos, comenzando desde . Requiere como condición previa que cada subarreglo r en el rango tenga su . La ejecución de distribuir (i, j, m) garantizará que cada . Todo el paso de distribución es distribuir . El pseudocódigo para la implementación de distribuir se muestra a continuación: ${\displaystyle B_{j}}$${\displaystyle i,\ldots ,i+m-1}$${\displaystyle bnum[r]\geq j}$${\displaystyle bnum[r]\geq j+m}$${\displaystyle (1,1,{\sqrt {N}})}$

def  distribuir ( i ,  j ,  m :  int )  ->  None : 
"""Distribuir mediante divide y vencerás recursivo.""" si m == 1 : copy_elems ( i , j ) de lo contrario : distribuir ( i , j , m / 2 ) distribuir ( i + m / 2 , j , m / 2 ) distribuir ( i , j + m / 2 , m / 2 ) distribuir ( i + m / 2 , j + m / 2 , m / 2 )    
       
         
    
            
                
                
                    

El caso base, donde m = 1, tiene una llamada a la subrutina copy_elems . En este caso base, todos los elementos del subarreglo i que pertenecen al contenedor j se agregan de una sola vez. Si esto hace que el contenedor j tenga demasiados elementos, divide el contenedor con el procedimiento descrito anteriormente.

• Algoritmo que ignora el caché
• Clasificación por embudo
• Clasificación externa

• Harald Prokop. Algoritmos ajenos a la memoria caché. Tesis de maestría, MIT. 1999.