Algoritmo de clasificación más rápido para una situación específica

Question

¿Cuál es el algoritmo de clasificación más rápido para un gran número (decenas de miles) de grupos de 9 valores positivos de doble precisión, donde cada grupo debe clasificarse individualmente? Por lo tanto, tiene que clasificar rápidamente un pequeño número de valores de doble precisión posiblemente repetidos, muchas veces seguidas. Los valores están en el intervalo [0..1]. No me importa la complejidad del espacio o la estabilidad, solo la velocidad.

Answer 1

Ordenando cada grupo individualmente, la combinación de fusión probablemente sería más fácil de implementar con buenos resultados.

Una red de clasificación probablemente sería la solución más rápida: http://en.wikipedia.org/wiki/Sorting_network

Answer 2

Buena pregunta, porque esto se reduce a "La manera más rápida de resolver una serie de 9 elementos", y la mayoría de las comparaciones entre y análisis de métodos de clasificación están a punto N. grande. Supongo que los "grupos" están claramente definidos y no juegan un papel real aquí.

Probablemente tendrá que comparar algunos candidatos porque entran en juego muchos factores (localidad).

En cualquier caso, lo que hace sonidos paralelos como una buena idea. Use Parallel.For() si puede usar, NET4.

Answer 3

Creo que tendrá que probar algunos ejemplos para ver qué funciona mejor, ya que tiene un conjunto inusual de condiciones. Mi conjetura que la mejor será uno de

• clasificación de la red
• ordenación por inserción
• ordenación rápida (una sola planta - ordenación por inserción abajo)
• ordenamiento por mezcla

Teniendo en cuenta que el doble el número de precisión es relativamente largo. Sospecho que no funcionará mejor con una clasificación de radix, pero puede agregarlo.

Para lo que vale, Java usa la ordenación rápida en dobles hasta que el número de elementos que se ordenarán cae por debajo de 7, en el cual se usa ordenar por inserción. La tercera opción imita esa solución.

También su problema general es embarrassingly parallel por lo que desea hacer uso del paralelismo cuando sea posible. El problema se ve demasiado pequeño para una solución distribuida (más tiempo se perdería en la creación de redes de salvado), pero si se pone encima de la derecha, el problema puede hacer uso de múltiples núcleos muy eficaz.

Answer 4

Parece que desea que la forma más tacaño de ciclo para ordenar 9 valores. Dado que el número de valores se limita, me (como se sugiere Kathy) primero hacer una especie de inserción desenrollada en los 4 primeros elementos y el segundo 5 elementos. Entonces fusionaría esos dos grupos.

He aquí un tipo de inserción desenrollado de 4 elementos:

if (u[1] < u[0]) swap(u[0], u[1]); 
if (u[2] < u[0]) swap(u[0], u[2]); 
if (u[3] < u[0]) swap(u[0], u[3]); 

if (u[2] < u[1]) swap(u[1], u[2]); 
if (u[3] < u[1]) swap(u[1], u[3]); 

if (u[3] < u[2]) swap(u[2], u[3]); 

Así es un bucle de mezcla. El primer conjunto de 4 elementos es en u, y el segundo conjunto de 5 elementos en en v. El resultado está en r.

i = j = k = 0; 
while(i < 4 && j < 5){ 
    if (u[i] < v[j]) r[k++] = u[i++]; 
    else if (v[j] < u[i]) r[k++] = v[j++]; 
    else { 
    r[k++] = u[i++]; 
    r[k++] = v[j++]; 
    } 
} 
while (i < 4) r[k++] = u[i++]; 
while (j < 5) r[k++] = v[j++];