performance - una - Implementación rápida de algoritmos para ordenar listas muy pequeñas

quicksort explicacion

Question

Este es el problema con el que me encontré 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 usar 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 es un procesador Intel de 64 bits con SSE3.

Gracias

Answer 1

La ordenación de redes se puede implementar fácilmente en SIMD, aunque comienza a ponerse fea 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, entonces quiere ordenar al menos 16 conjuntos de datos; es mucho más difícil hacer este tipo de cosas en los vectores SIMD.

Ver también: Tipo más rápido de longitud fija 6 int array

Answer 2

La ordenación por inserción se considera mejor para matrices pequeñas. Consulte Clasificación estable rápida para matrices pequeñas (de menos de 32 o 64 elementos)

Answer 3

Para arreglos pequeños como este, probablemente deberías buscar redes de clasificación . 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 este sitio que puede ayudarlo a encontrar redes de clasificación óptimas para un tamaño determinado 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 sugirieron.

Answer 4

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

La forma más eficiente de ordenar, por ejemplo, cuatro elementos, sería desenredar el algoritmo de ordenamiento para realizar comparaciones lineales, eliminando así 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 mucho por cada artículo adicional que agregue. 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 5

Para un conjunto de datos tan pequeño, lo más simple posible de algoritmo. Lo más probable es que una Clasificación de inserción básica 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 6

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 puede ser probado 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.