Implementación rápida de algoritmos para ordenar una lista muy pequeña

Question

Este es el problema que tuve hace mucho tiempo. Pensé que podría pedirte tus ideas. supongo que tengo una lista muy pequeña de números (enteros), 4 u 8 elementos, que deben ordenarse, rápido. ¿cuál sería el mejor enfoque/algoritmo?

mi enfoque era utilizar las funciones max/min (10 funciones para ordenar 4 números, sin ramificaciones, iirc).

// s(i,j) == max(i,j), min(i,j) 
i,j = s(i,j) 
k,l = s(k,l) 
i,k = s(i,k) // i on top 
j,l = s(j,l) // l on bottom 
j,k = s(j,k) 

Supongo que mi pregunta se refiere más a la implementación que al tipo de algoritmo.

En este punto, se vuelve algo dependiente del hardware, así que supongamos que el procesador Intel de 64 bits con SSE3.

Gracias

Answer 1

Para matrices pequeñas como esta, probablemente debería consultar sorting networks. Como puede ver en esa página, el ordenamiento por inserción se puede expresar como una red de clasificación. Sin embargo, si conoce el tamaño de la matriz de antemano, puede diseñar una red óptima. Eche un vistazo a this site que puede ayudarlo a encontrar redes de clasificación óptimas para un tamaño dado de matriz (aunque lo óptimo solo está garantizado hasta un tamaño de 16, creo). Los comparadores están incluso agrupados en operaciones que pueden realizarse en paralelo. Los comparadores son esencialmente los mismos que su función s (x, y), aunque si realmente quiere que esto sea rápido, no debería usar min y max porque entonces está haciendo el doble de comparaciones que son necesarias.

Si necesita este algoritmo de clasificación para trabajar en una amplia gama de tamaños, entonces probablemente debería ir con la ordenación de inserción como otros han sugerido.

Answer 2

para un pequeño conjunto de estos datos, que quieren lo más simple del algoritmo como sea posible. Lo más probable es que un Insertion Sort básico funcione tan bien como pueda desear.

Necesitaría saber más sobre el sistema en el que se está ejecutando, cuántas veces necesita hacer este tipo de orden un segundo, etc. ... pero la regla general en pequeños ordenamientos es mantenerlo simple. Quicksort y similares no son beneficiosos.

Answer 3

El tipo de inserción se considera mejor para matrices pequeñas. Ver Fast stable sort for small arrays (under 32 or 64 elements)

Answer 4

Veo que ya tiene una solución que usa 5 comparaciones (suponiendo que s (i, j) compara los dos números una vez, y los intercambia o no). Si te apegas a la clasificación basada en la comparación, entonces no puedes hacerlo con menos de 5 comparaciones.

¡Esto se puede comprobar porque hay 4! = 24 formas posibles de pedir 4 números. Cada comparación solo puede reducir las posibilidades a la mitad, por lo que con 4 comparaciones solo se puede distinguir entre 2^4 = 16 posibles ordenaciones.

Answer 5

Para ordenar pequeñas cantidades de números, desea un algoritmo simple ya que la complejidad agrega más sobrecarga.

La forma más eficiente para ordenar, por ejemplo, cuatro elementos sería desentrañar el algoritmo de ordenación de las comparaciones lineales, elliminating por lo tanto toda la sobrecarga:

function sort(i,j,k,l) { 
    if (i < j) { 
    if (j < k) { 
     if (k < l) return [i,j,k,l]; 
     if (j < l) return [i,j,l,k]; 
     if (i < l) return [i,l,j,k]; 
     return [l,i,j,k]; 
    } else if (i < k) { 
     if (j < l) return [i,k,j,l]; 
     if (k < l) return [i,k,l,j]; 
     if (i < l) return [i,l,k,j]; 
     return [l,i,k,j]; 
    } else { 
     if (j < l) return [k,i,j,l]; 
     if (i < l) return [k,i,l,j]; 
     if (k < l) return [k,l,i,j]; 
     return [l,k,i,j]; 
    } 
    } else { 
    if (i < k) { 
     if (k < l) return [j,i,k,l]; 
     if (i < l) return [j,i,l,k]; 
     if (j < l) return [j,l,i,k]; 
     return [l,j,i,k]; 
    } else if (j < k) { 
     if (i < l) return [j,k,i,l]; 
     if (k < l) return [j,k,l,i]; 
     if (j < l) return [j,l,k,i]; 
     return [l,j,k,i]; 
    } else { 
     if (i < l) return [k,j,i,l]; 
     if (j < l) return [k,j,l,i]; 
     if (k < l) return [k,l,j,i]; 
     return [l,k,j,i]; 
    } 
    } 
} 

Sin embargo, el código crece una gran cantidad para cada artículo adicional se agrega . Agregar un quinto elemento hace que el código sea aproximadamente cuatro veces más grande.En ocho ítems sería aproximadamente 30000 líneas, por lo que, aunque sigue siendo el más eficiente, es mucho código, y tendría que escribir un programa que escriba el código para corregirlo.

Answer 6

Las redes de clasificación se pueden implementar fácilmente en SIMD, aunque comienza a ponerse feo alrededor de N = 16. Para N = 4 o N = 8, aunque esta sería una buena opción. Lo ideal es que necesite muchos conjuntos de datos pequeños para ordenar al mismo tiempo, es decir, si está ordenando valores de 8 bits, quiere ordenar al menos 16 conjuntos de datos: es mucho más difícil hacer este tipo de cosas en vectores SIMD.

Consulte también: Fastest sort of fixed length 6 int array