Bitwise LSD Sort (clasificación de radix)

Recientemente publiqué muchos artículos sobre varios algoritmos de clasificación y su comparación, decidí hacer mis propios cinco centavos.

Quiero hablar sobre mi algoritmo favorito para la ordenación por bits de LSD (dígito menos significativo - primero el bit menos significativo) con el conteo (clasificación por radix). El algoritmo clásico fue repensado de alguna manera por el autor hacia algunas optimizaciones a favor de la aceleración y la simplicidad.

Entonces, la clasificación propuesta es sostenible. Ordenaremos los números enteros de 32 bits. Para trabajar, necesita ~ (n + 4KB) de memoria adicional, lo cual es un desperdicio, pero le permite lograr un aumento en el rendimiento.

En este tipo de LSD, no se utilizan comparaciones e intercambios, el algoritmo es completamente lineal. Complejidad computacional O (N).

La característica principal del algoritmo es la alta eficiencia para conjuntos de datos altamente mixtos o aleatorios. En conjuntos casi ordenados, tiene sentido usar otros algoritmos, ya que la ganancia no será tan significativa. Funciona mal en arreglos pequeños, menos de un par de cientos de elementos.

La clasificación se realiza localmente para ahorrar memoria.

//================================================== // RADIX  (  by rebuilder) //   ,  . //   (n),   ~(n+4k) //================================================== procedure RSort(var m: array of Longword); //-------------------------------------------------- procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte); var i,temp : Longword; k : Byte; begin for i := High(source) downto 0 do begin temp := source[i]; k := temp SHR num; dec(offset[k]); dest[offset[k]] := temp; end; end; //-------------------------------------------------- //    ,     var s : array[0..3] of array[0..255] of Longword; i,k : longword; //     k offset : array[0..3] of byte absolute k; m_temp : array of Longword; begin SetLength(m_temp, Length(m)); //    FillChar(s[0], 256 * 4 * SizeOf(Longword), 0); //   for i := 0 to High(m) do begin k := m[i]; Inc(s[0,offset[0]]); Inc(s[1,offset[1]]); Inc(s[2,offset[2]]); Inc(s[3,offset[3]]); end; //     for i := 1 to 255 do begin Inc(s[0,i], s[0,i-1]); Inc(s[1,i], s[1,i-1]); Inc(s[2,i], s[2,i-1]); Inc(s[3,i], s[3,i-1]); end; //         Sort_step(m, m_temp, s[0], 0); Sort_step(m_temp, m, s[1], 8); Sort_step(m, m_temp, s[2], 16); Sort_step(m_temp, m, s[3], 24); SetLength(m_temp, 0); end; //================================================== ... SetLength(m, n); for i := 0 to n - 1 do m[i] := Random(65536 * 65536); ... RSort(m); ... 

El código está escrito en Pascal, pero no será difícil portarlo a cualquier idioma conveniente para usted.

La secuencia de ejecución consta de dos etapas:

1. Para cada bloque (ocho dígitos binarios - 1 byte (valor óptimo)), contando, se calcula su posición en una nueva matriz.
2. Secuencialmente para cada bloque (del menos significativo al más alto), se mueve a la posición calculada previamente.

Mejoras:

1. Para una variedad de compensaciones, utilizamos la alineación en la memoria y, debido al pequeño volumen, se coloca en L1, la memoria caché del procesador.
2. La matriz de desplazamiento se llena inmediatamente para todos los dígitos, lo que le permite recorrer la matriz para contar solo una vez.
3. El cálculo de la posición no comienza desde el encabezado de la matriz, pero desde el final, esto resuelve dos problemas:
   
   • el final de la matriz en el primer paso ya está en la caché "calentada", que con matrices grandes da una ligera aceleración;
   • en segundo lugar, el ciclo descendente a cero es más corto por una instrucción de ensamblador, en cada paso del ciclo, en relación con el ciclo ascendente.
4. Para cada iteración (de cuatro), no se usa un bucle anidado, aunque con menos belleza, pero se guardan varias instrucciones más del procesador.

Debido a su simplicidad, el código es casi idéntico en velocidad a las compilaciones de compiladores de 32 y 64 bits. Si es necesario, es fácil imaginar una versión del algoritmo para números de 16 y 64 bits.

Comparación del algoritmo de muestreo aleatorio con clasificación rápida en una plataforma de 64 bits (en promedio, diez pases cada uno).



Sugerencias y comentarios sobre optimizaciones son bienvenidos.

Gracias