c - bidimensional - El tipo más rápido de longitud fija 6 int array

size of array c (23)

Aquí hay una implementación usando redes de clasificación :

inline void Sort2(int *p0, int *p1) { const int temp = min(*p0, *p1); *p1 = max(*p0, *p1); *p0 = temp; } inline void Sort3(int *p0, int *p1, int *p2) { Sort2(p0, p1); Sort2(p1, p2); Sort2(p0, p1); } inline void Sort4(int *p0, int *p1, int *p2, int *p3) { Sort2(p0, p1); Sort2(p2, p3); Sort2(p0, p2); Sort2(p1, p3); Sort2(p1, p2); } inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5) { Sort3(p0, p1, p2); Sort3(p3, p4, p5); Sort2(p0, p3); Sort2(p2, p5); Sort4(p1, p2, p3, p4); }

Realmente necesita implementaciones mínimas y max sin ramificación muy eficientes para esto, ya que efectivamente es a lo que se reduce este código: una secuencia de operaciones max y max (13 de cada una, en total). Dejo esto como un ejercicio para el lector.

Tenga en cuenta que esta implementación se presta fácilmente a la vectorización (por ejemplo, SIMD: la mayoría de las ISA de SIMD tienen instrucciones mínimas / mínimas vectoriales) y también a implementaciones de GPU (por ejemplo, CUDA: no hay problemas con la divergencia de deformación, etc.).

Ver también: Implementación rápida de algoritmos para ordenar una lista muy pequeña.

Respondiendo a otra pregunta de desbordamiento de pila ( esta ) me topé con un interesante sub-problema. ¿Cuál es la forma más rápida de ordenar una matriz de 6 pulgadas?

Como la pregunta es de muy bajo nivel:

no podemos asumir que las bibliotecas están disponibles (y la llamada en sí tiene su costo), solo C simple
para evitar el vaciado de la línea de instrucciones (que tiene un costo muy alto) probablemente deberíamos minimizar las ramificaciones, saltos y cualquier otro tipo de interrupción del flujo de control (como las ocultas detrás de los puntos de secuencia en && o || ).
el espacio está restringido y minimizar los registros y el uso de la memoria es un problema, lo ideal es que lo mejor sea clasificarlos en su lugar.

Realmente esta pregunta es un tipo de golf donde el objetivo no es minimizar la longitud de la fuente, sino el tiempo de ejecución. Lo llamo código ''Zening'' como se usa en el título del libro Zen of Code optimization por Michael Abrash y sus sequels .

En cuanto a por qué es interesante, hay varias capas:

el ejemplo es simple y fácil de entender y medir, sin mucha habilidad en C
muestra los efectos de la elección de un buen algoritmo para el problema, pero también los efectos del compilador y el hardware subyacente.

Aquí está mi implementación de referencia (ingenua, no optimizada) y mi conjunto de pruebas.

#include <stdio.h> static __inline__ int sort6(int * d){ char j, i, imin; int tmp; for (j = 0 ; j < 5 ; j++){ imin = j; for (i = j + 1; i < 6 ; i++){ if (d[i] < d[imin]){ imin = i; } } tmp = d[j]; d[j] = d[imin]; d[imin] = tmp; } } static __inline__ unsigned long long rdtsc(void) { unsigned long long int x; __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x)); return x; } int main(int argc, char ** argv){ int i; int d[6][5] = { {1, 2, 3, 4, 5, 6}, {6, 5, 4, 3, 2, 1}, {100, 2, 300, 4, 500, 6}, {100, 2, 3, 4, 500, 6}, {1, 200, 3, 4, 5, 600}, {1, 1, 2, 1, 2, 1} }; unsigned long long cycles = rdtsc(); for (i = 0; i < 6 ; i++){ sort6(d[i]); /* * printf("d%d : %d %d %d %d %d %d/n", i, * d[i][0], d[i][6], d[i][7], * d[i][8], d[i][9], d[i][10]); */ } cycles = rdtsc() - cycles; printf("Time is %d/n", (unsigned)cycles); }

Primeros resultados

Como el número de variantes es cada vez mayor, las reuní en un conjunto de pruebas que se puede encontrar here . Las pruebas reales utilizadas son un poco menos ingenuas que las mostradas anteriormente, gracias a Kevin Stock. Puedes compilarlo y ejecutarlo en tu propio entorno. Estoy bastante interesado en el comportamiento en diferentes compiladores / arquitectura de destino. (OK, muchachos, pongan las respuestas, haré +1 a todos los contribuyentes de un nuevo conjunto de resultados).

Le di la respuesta a Daniel Stutzbach (para jugar golf) hace un año, ya que estaba en la fuente de la solución más rápida en ese momento (redes de clasificación).

Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, -O2

Llamada directa a la función de biblioteca qsort: 689.38
Implementación ingenua (ordenación por inserción): 285.70
Tipo de Inserción (Daniel Stutzbach): 142.12
Inserción Tipo Desenrollado: 125.47
Orden de clasificación: 102.26
Orden del orden con registros: 58.03
Redes de clasificación (Daniel Stutzbach): 111.68
Redes de clasificación (Paul R): 66.36
Clasificando Redes 12 con Intercambio Rápido: 58.86
Clasificando Redes 12 Swaps reordenado: 53.74
Clasificando Redes 12 Reordenadas Intercambio Simple: 31.54
Red de clasificación ordenada con intercambio rápido: 31.54
Red de clasificación ordenada con intercambio rápido V2: 33.63
Tipo de burbuja en línea (Paolo Bonzini): 48.85
Tipo de Inserción Desenrollada (Paolo Bonzini): 75.30

Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, -O1

Llamada directa a la función de biblioteca qsort: 705.93
Implementación ingenua (ordenación por inserción): 135.60
Tipo de Inserción (Daniel Stutzbach): 142.11
Inserción Tipo Desenrollado: 126.75
Orden del orden: 46.42
Orden de clasificación con registros: 43.58
Redes de clasificación (Daniel Stutzbach): 115.57
Redes de clasificación (Paul R): 64.44
Clasificando Redes 12 con Intercambio Rápido: 61.98
Clasificando Redes 12 Swaps reordenado: 54.67
Clasificando Redes 12 Reordenadas Intercambio Simple: 31.54
Red de clasificación ordenada con intercambio rápido: 31.24
Red de clasificación reordenada con intercambio rápido V2: 33.07
Tipo de burbuja en línea (Paolo Bonzini): 45.79
Tipo de inserción desenrollada (Paolo Bonzini): 80.15

Incluí los resultados de -O1 y -O2 porque, sorprendentemente, para varios programas, O2 es menos eficiente que O1. Me pregunto qué optimización específica tiene este efecto?

Comentarios sobre soluciones propuestas

Inserción Sort (Daniel Stutzbach)

Como era de esperar, minimizar las sucursales es una buena idea.

Redes de clasificación (Daniel Stutzbach)

Mejor que la ordenación por inserción. Me pregunté si el efecto principal no se debía a evitar el bucle externo. Lo intenté por orden de inserción desenrollada para verificar y de hecho obtenemos aproximadamente las mismas cifras (el código está here ).

Redes de clasificación (Paul R)

Lo mejor por mucho. El código real que solía probar está here . Aún no sé por qué es casi dos veces más rápido que la implementación de otra red de clasificación. Parámetro que pasa? Rápido máximo?

Clasificación de redes 12 SWAP con intercambio rápido

Como lo sugirió Daniel Stutzbach, combiné su red de clasificación de 12 intercambios con un intercambio rápido sin sucursales (el código está here ). De hecho, es más rápido, el mejor hasta el momento con un pequeño margen (aproximadamente el 5%), como podría esperarse utilizando 1 swap menos.

También es interesante notar que el intercambio sin sucursales parece ser mucho (4 veces) menos eficiente que el simple si se utiliza en la arquitectura PPC.

Llamando a la biblioteca qsort

Para dar otro punto de referencia, también intenté, como se sugirió, simplemente llamar a la biblioteca qsort (el código está here ). Como era de esperar, es mucho más lento: de 10 a 30 veces más lento ... como se hizo evidente con el nuevo conjunto de pruebas, el problema principal parece ser la carga inicial de la biblioteca después de la primera llamada, y no se compara tan mal con otros versión. Es solo entre 3 y 20 veces más lento en mi Linux. En algunas arquitecturas utilizadas para pruebas por otras, parece incluso más rápido (estoy realmente sorprendido por esa, ya que la biblioteca utiliza una API más compleja).

Orden de rango

Rex Kerr propuso otro método completamente diferente: para cada elemento de la matriz, calcule directamente su posición final. Esto es eficiente porque el orden de rango de computación no necesita ramificación. El inconveniente de este método es que toma tres veces la cantidad de memoria de la matriz (una copia de la matriz y las variables para almacenar órdenes de rango). Los resultados de rendimiento son muy sorprendentes (e interesantes). En mi arquitectura de referencia con sistema operativo de 32 bits e Intel Core2 Quad E8300, el recuento de ciclos fue ligeramente inferior a 1000 (como la clasificación de redes con intercambio de ramificación). Pero cuando se compiló y ejecutó en mi caja de 64 bits (Intel Core2 Duo) funcionó mucho mejor: se convirtió en el más rápido hasta ahora. Finalmente descubrí la verdadera razón. Mi caja de 32 bits usa gcc 4.4.1 y mi caja de 64 bits gcc 4.4.3 y la última parece ser mucho mejor para optimizar este código en particular (hubo muy poca diferencia para otras propuestas).

actualización :

Como se muestra en las figuras anteriores, este efecto aún fue mejorado por las versiones posteriores de gcc y Rank Order se volvió consistentemente el doble de rápido que cualquier otra alternativa.

Clasificando Redes 12 con Swap reordenado

La sorprendente eficacia de la propuesta de Rex Kerr con gcc 4.4.3 me hizo preguntarme: ¿cómo podría un programa con 3 veces más uso de memoria ser más rápido que las redes de clasificación sin sucursales? Mi hipótesis era que tenía menos dependencias del tipo de lectura después de la escritura, lo que permite un mejor uso del programador de instrucciones superscalar del x86. Eso me dio una idea: reordenar los swaps para minimizar las dependencias de lectura y escritura. Más simple: cuando haces SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); debe esperar a que finalice el primer intercambio antes de realizar el segundo porque ambos acceden a una celda de memoria común. Cuando haces SWAP(1, 2); SWAP(4, 5); SWAP(1, 2); SWAP(4, 5); El procesador puede ejecutar ambos en paralelo. Lo probé y funciona como se esperaba, las redes de clasificación se ejecutan aproximadamente un 10% más rápido.

Clasificando Redes 12 con Simple Swap

Un año después de la publicación original, Steinar H. Gunderson sugirió que no debemos intentar ser más astutos que el compilador y mantener el código de intercambio simple. De hecho, es una buena idea, ya que el código resultante es un 40% más rápido. También propuso un intercambio optimizado a mano utilizando el código de ensamblaje en línea x86 que aún puede ahorrar algunos ciclos más. Lo más sorprendente (dice volúmenes sobre la psicología del programador) es que hace un año ninguno de los utilizados probó esa versión de intercambio. El código que solía probar está here . Otros sugirieron otras formas de escribir un intercambio rápido en C, pero produce las mismas interpretaciones que la simple con un compilador decente.

El código "mejor" es ahora como sigue:

static inline void sort6_sorting_network_simple_swap(int * d){ #define min(x, y) (x<y?x:y) #define max(x, y) (x<y?y:x) #define SWAP(x,y) { const int a = min(d[x], d[y]); / const int b = max(d[x], d[y]); / d[x] = a; d[y] = b; } SWAP(1, 2); SWAP(4, 5); SWAP(0, 2); SWAP(3, 5); SWAP(0, 1); SWAP(3, 4); SWAP(1, 4); SWAP(0, 3); SWAP(2, 5); SWAP(1, 3); SWAP(2, 4); SWAP(2, 3); #undef SWAP #undef min #undef max }

Si creemos que nuestro conjunto de pruebas (y, sí, es bastante deficiente, su mero beneficio es ser breve, simple y fácil de entender lo que estamos midiendo), el número promedio de ciclos del código resultante para un tipo es inferior a 40 ciclos ( Se ejecutan 6 pruebas). Eso puso cada swap a un promedio de 4 ciclos. Yo lo llamo increíblemente rápido. ¿Alguna otra mejora posible?

El código de prueba es bastante malo; desborda la matriz inicial (¿la gente aquí lee las advertencias del compilador?), el printf está imprimiendo los elementos incorrectos, usa .byte para rdtsc sin ninguna razón, solo hay una ejecución (!), no hay nada que compruebe que los resultados finales son realmente correctos (por lo que es muy fácil "optimizar" en algo sutilmente incorrecto), las pruebas incluidas son muy rudimentarias (¿no hay números negativos?) y no hay nada que impida que el compilador simplemente descarte toda la función como código muerto.

Dicho esto, también es bastante fácil mejorar la solución de red bitónica; simplemente cambia las cosas min / max / SWAP a

#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }

y sale un 65% más rápido para mí (Debian gcc 4.4.5 con -O2, amd64, Core i7).

Me encontré con esta pregunta de Google hace unos días porque también tenía la necesidad de ordenar rápidamente una matriz de longitud fija de 6 enteros. Sin embargo, en mi caso, mis números enteros son solo 8 bits (en lugar de 32) y no tengo el requisito estricto de usar solo C. Pensé que compartiría mis hallazgos de todos modos, en caso de que puedan ser útiles para alguien ...

Implementé una variante de una clasificación de red en ensamblaje que utiliza SSE para vectorizar las operaciones de comparación e intercambio, en la medida de lo posible. Se necesitan seis "pases" para ordenar completamente la matriz. Utilicé un mecanismo novedoso para convertir directamente los resultados de PCMPGTB (comparación vectorizada) a parámetros aleatorios para PSHUFB (intercambio vectorizado), utilizando solo un PADDB (vectorizado agregar) y en algunos casos también una instrucción PAND (bitwise AND).

Este enfoque también tuvo el efecto secundario de producir una función verdaderamente sin ramas. No hay instrucciones de salto en absoluto.

Parece que esta implementación es aproximadamente un 38% más rápida que la implementación que actualmente está marcada como la opción más rápida en la pregunta ("Clasificación de redes 12 con intercambio simple"). Modifiqué esa implementación para usar elementos de matriz char durante mis pruebas, para hacer la comparación justa.

Debo tener en cuenta que este enfoque se puede aplicar a cualquier tamaño de matriz de hasta 16 elementos. Espero que la ventaja de velocidad relativa sobre las alternativas crezca para las matrices más grandes.

El código está escrito en MASM para procesadores x86_64 con SSSE3. La función utiliza la "nueva" convención de llamada de Windows x64. Aquí está...

PUBLIC simd_sort_6 .DATA ALIGN 16 pass1_shuffle OWORD 0F0E0D0C0B0A09080706040503010200h pass1_add OWORD 0F0E0D0C0B0A09080706050503020200h pass2_shuffle OWORD 0F0E0D0C0B0A09080706030405000102h pass2_and OWORD 00000000000000000000FE00FEFE00FEh pass2_add OWORD 0F0E0D0C0B0A09080706050405020102h pass3_shuffle OWORD 0F0E0D0C0B0A09080706020304050001h pass3_and OWORD 00000000000000000000FDFFFFFDFFFFh pass3_add OWORD 0F0E0D0C0B0A09080706050404050101h pass4_shuffle OWORD 0F0E0D0C0B0A09080706050100020403h pass4_and OWORD 0000000000000000000000FDFD00FDFDh pass4_add OWORD 0F0E0D0C0B0A09080706050403020403h pass5_shuffle OWORD 0F0E0D0C0B0A09080706050201040300h pass5_and OWORD 0000000000000000000000FEFEFEFE00h pass5_add OWORD 0F0E0D0C0B0A09080706050403040300h pass6_shuffle OWORD 0F0E0D0C0B0A09080706050402030100h pass6_add OWORD 0F0E0D0C0B0A09080706050403030100h .CODE simd_sort_6 PROC FRAME .endprolog ; pxor xmm4, xmm4 ; pinsrd xmm4, dword ptr [rcx], 0 ; pinsrb xmm4, byte ptr [rcx + 4], 4 ; pinsrb xmm4, byte ptr [rcx + 5], 5 ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer. Same on extract ; avoiding pins/extrb also means we don''t need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb. movd xmm4, dword ptr [rcx] pinsrw xmm4, word ptr [rcx + 4], 2 ; word 2 = bytes 4 and 5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass1_shuffle] pcmpgtb xmm5, xmm4 paddb xmm5, oword ptr [pass1_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass2_shuffle] pcmpgtb xmm5, xmm4 pand xmm5, oword ptr [pass2_and] paddb xmm5, oword ptr [pass2_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass3_shuffle] pcmpgtb xmm5, xmm4 pand xmm5, oword ptr [pass3_and] paddb xmm5, oword ptr [pass3_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass4_shuffle] pcmpgtb xmm5, xmm4 pand xmm5, oword ptr [pass4_and] paddb xmm5, oword ptr [pass4_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass5_shuffle] pcmpgtb xmm5, xmm4 pand xmm5, oword ptr [pass5_and] paddb xmm5, oword ptr [pass5_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass6_shuffle] pcmpgtb xmm5, xmm4 paddb xmm5, oword ptr [pass6_add] pshufb xmm4, xmm5 ;pextrd dword ptr [rcx], xmm4, 0 ; benchmarked with this ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version ;pextrb byte ptr [rcx + 5], xmm4, 5 movd dword ptr [rcx], xmm4 pextrw word ptr [rcx + 4], xmm4, 2 ; x86 is little-endian, so this is the right order ret simd_sort_6 ENDP END

Puede compilar esto en un objeto ejecutable y vincularlo a su proyecto C. Para obtener instrucciones sobre cómo hacer esto en Visual Studio, puedes leer este artículo . Puede usar el siguiente prototipo de C para llamar a la función desde su código C:

void simd_sort_6(char *values);

Para cualquier optimización, siempre es mejor probar, probar, probar. Intentaría al menos clasificar las redes y la ordenación por inserción. Si apostara, pondría mi dinero en orden de inserción basado en la experiencia pasada.

¿Sabes algo sobre los datos de entrada? Algunos algoritmos funcionarán mejor con ciertos tipos de datos. Por ejemplo, la ordenación por inserción se desempeña mejor en datos ordenados o casi ordenados, por lo que será la mejor opción si existe una probabilidad superior a la media de datos casi ordenados.

El algoritmo que publicaste es similar a una ordenación por inserción, pero parece que has minimizado la cantidad de swaps al costo de más comparaciones. Sin embargo, las comparaciones son mucho más caras que los intercambios, ya que las sucursales pueden hacer que la línea de instrucciones se detenga.

Aquí hay una implementación de orden de inserción:

static __inline__ int sort6(int *d){ int i, j; for (i = 1; i < 6; i++) { int tmp = d[i]; for (j = i; j >= 1 && tmp < d[j-1]; j--) d[j] = d[j-1]; d[j] = tmp; } }

Así es como construiría una red de clasificación. Primero, use este sitio para generar un conjunto mínimo de macros SWAP para una red de la longitud adecuada. Envolver eso en una función me da:

static __inline__ int sort6(int * d){ #define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; } SWAP(1, 2); SWAP(0, 2); SWAP(0, 1); SWAP(4, 5); SWAP(3, 5); SWAP(3, 4); SWAP(0, 3); SWAP(1, 4); SWAP(2, 5); SWAP(2, 4); SWAP(1, 3); SWAP(2, 3); #undef SWAP }

Parece que llegué a la fiesta un año tarde, pero aquí vamos ...

Mirando el ensamblaje generado por gcc 4.5.2, observé que se están realizando cargas y almacenes para cada intercambio, que realmente no es necesario. Sería mejor cargar los 6 valores en los registros, ordenarlos y almacenarlos nuevamente en la memoria. Ordené que las cargas en las tiendas estuvieran lo más cerca posible para que los registros se necesiten primero y se usen por última vez. También utilicé la macro SWAP de Steinar H. Gunderson. Actualización: Cambié a la macro SWAP de Paolo Bonzini que gcc convierte en algo similar a Gunderson, pero gcc puede ordenar mejor las instrucciones ya que no se dan como ensamblaje explícito.

Utilicé el mismo orden de intercambio que la red de intercambio reordenada dada como el mejor rendimiento, aunque puede haber un mejor ordenamiento. Si encuentro algo más de tiempo, generaré y probaré un montón de permutaciones.

Cambié el código de prueba para considerar más de 4000 arreglos y mostrar el número promedio de ciclos necesarios para ordenar cada uno. En un i5-650 obtengo ~ 34.1 ciclos / clasificación (usando -O3), en comparación con la red de clasificación reordenada original, obteniendo ~ 65.3 ciclos / clasificación (utilizando -O1, tiempos -O2 y -O3).

#include <stdio.h> static inline void sort6_fast(int * d) { #define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; } register int x0,x1,x2,x3,x4,x5; x1 = d[1]; x2 = d[2]; SWAP(x1, x2); x4 = d[4]; x5 = d[5]; SWAP(x4, x5); x0 = d[0]; SWAP(x0, x2); x3 = d[3]; SWAP(x3, x5); SWAP(x0, x1); SWAP(x3, x4); SWAP(x1, x4); SWAP(x0, x3); d[0] = x0; SWAP(x2, x5); d[5] = x5; SWAP(x1, x3); d[1] = x1; SWAP(x2, x4); d[4] = x4; SWAP(x2, x3); d[2] = x2; d[3] = x3; #undef SWAP #undef min #undef max } static __inline__ unsigned long long rdtsc(void) { unsigned long long int x; __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx"); return x; } void ran_fill(int n, int *a) { static int seed = 76521; while (n--) *a++ = (seed = seed *1812433253 + 12345); } #define NTESTS 4096 int main() { int i; int d[6*NTESTS]; ran_fill(6*NTESTS, d); unsigned long long cycles = rdtsc(); for (i = 0; i < 6*NTESTS ; i+=6) { sort6_fast(d+i); } cycles = rdtsc() - cycles; printf("Time is %.2lf/n", (double)cycles/(double)NTESTS); for (i = 0; i < 6*NTESTS ; i+=6) { if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5]) printf("d%d : %d %d %d %d %d %d/n", i, d[i+0], d[i+1], d[i+2], d[i+3], d[i+4], d[i+5]); } return 0; }

Cambié la suite de prueba modificada para que también informe los relojes por orden y ejecute más pruebas (la función cmp también se actualizó para manejar el desbordamiento de enteros), aquí están los resultados en algunas arquitecturas diferentes. Intenté realizar pruebas en una CPU de AMD pero rdtsc no es confiable en el X6 1100T que tengo disponible.

Clarkdale (i5-650) ================== Direct call to qsort library function 635.14 575.65 581.61 577.76 521.12 Naive implementation (insertion sort) 538.30 135.36 134.89 240.62 101.23 Insertion Sort (Daniel Stutzbach) 424.48 159.85 160.76 152.01 151.92 Insertion Sort Unrolled 339.16 125.16 125.81 129.93 123.16 Rank Order 184.34 106.58 54.74 93.24 94.09 Rank Order with registers 127.45 104.65 53.79 98.05 97.95 Sorting Networks (Daniel Stutzbach) 269.77 130.56 128.15 126.70 127.30 Sorting Networks (Paul R) 551.64 103.20 64.57 73.68 73.51 Sorting Networks 12 with Fast Swap 321.74 61.61 63.90 67.92 67.76 Sorting Networks 12 reordered Swap 318.75 60.69 65.90 70.25 70.06 Reordered Sorting Network w/ fast swap 145.91 34.17 32.66 32.22 32.18 Kentsfield (Core 2 Quad) ======================== Direct call to qsort library function 870.01 736.39 723.39 725.48 721.85 Naive implementation (insertion sort) 503.67 174.09 182.13 284.41 191.10 Insertion Sort (Daniel Stutzbach) 345.32 152.84 157.67 151.23 150.96 Insertion Sort Unrolled 316.20 133.03 129.86 118.96 105.06 Rank Order 164.37 138.32 46.29 99.87 99.81 Rank Order with registers 115.44 116.02 44.04 116.04 116.03 Sorting Networks (Daniel Stutzbach) 230.35 114.31 119.15 110.51 111.45 Sorting Networks (Paul R) 498.94 77.24 63.98 62.17 65.67 Sorting Networks 12 with Fast Swap 315.98 59.41 58.36 60.29 55.15 Sorting Networks 12 reordered Swap 307.67 55.78 51.48 51.67 50.74 Reordered Sorting Network w/ fast swap 149.68 31.46 30.91 31.54 31.58 Sandy Bridge (i7-2600k) ======================= Direct call to qsort library function 559.97 451.88 464.84 491.35 458.11 Naive implementation (insertion sort) 341.15 160.26 160.45 154.40 106.54 Insertion Sort (Daniel Stutzbach) 284.17 136.74 132.69 123.85 121.77 Insertion Sort Unrolled 239.40 110.49 114.81 110.79 117.30 Rank Order 114.24 76.42 45.31 36.96 36.73 Rank Order with registers 105.09 32.31 48.54 32.51 33.29 Sorting Networks (Daniel Stutzbach) 210.56 115.68 116.69 107.05 124.08 Sorting Networks (Paul R) 364.03 66.02 61.64 45.70 44.19 Sorting Networks 12 with Fast Swap 246.97 41.36 59.03 41.66 38.98 Sorting Networks 12 reordered Swap 235.39 38.84 47.36 38.61 37.29 Reordered Sorting Network w/ fast swap 115.58 27.23 27.75 27.25 26.54 Nehalem (Xeon E5640) ==================== Direct call to qsort library function 911.62 890.88 681.80 876.03 872.89 Naive implementation (insertion sort) 457.69 236.87 127.68 388.74 175.28 Insertion Sort (Daniel Stutzbach) 317.89 279.74 147.78 247.97 245.09 Insertion Sort Unrolled 259.63 220.60 116.55 221.66 212.93 Rank Order 140.62 197.04 52.10 163.66 153.63 Rank Order with registers 84.83 96.78 50.93 109.96 54.73 Sorting Networks (Daniel Stutzbach) 214.59 220.94 118.68 120.60 116.09 Sorting Networks (Paul R) 459.17 163.76 56.40 61.83 58.69 Sorting Networks 12 with Fast Swap 284.58 95.01 50.66 53.19 55.47 Sorting Networks 12 reordered Swap 281.20 96.72 44.15 56.38 54.57 Reordered Sorting Network w/ fast swap 128.34 50.87 26.87 27.91 28.02

Sé que esta es una vieja pregunta.

Pero acabo de escribir un tipo diferente de solución que quiero compartir.
Usando nada mas que MAX MAX anidado,

No es rápido, ya que usa 114 de cada uno,
podría reducirlo a 75 de manera bastante simple, así que -> pastebin

Pero entonces ya no es puramente min max.

Lo que podría funcionar es hacer min / max en múltiples enteros a la vez con AVX

Referencia de PMINSW

#include <stdio.h> static __inline__ int MIN(int a, int b){ int result =a; __asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b)); return result; } static __inline__ int MAX(int a, int b){ int result = a; __asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b)); return result; } static __inline__ unsigned long long rdtsc(void){ unsigned long long int x; __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x)); return x; } #define MIN3(a, b, c) (MIN(MIN(a,b),c)) #define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d))) static __inline__ void sort6(int * in) { const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5]; in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) ); const int AB = MAX(A, B), AC = MAX(A, C), AD = MAX(A, D), AE = MAX(A, E), AF = MAX(A, F), BC = MAX(B, C), BD = MAX(B, D), BE = MAX(B, E), BF = MAX(B, F), CD = MAX(C, D), CE = MAX(C, E), CF = MAX(C, F), DE = MAX(D, E), DF = MAX(D, F), EF = MAX(E, F); in[1] = MIN4 ( MIN4( AB, AC, AD, AE ), MIN4( AF, BC, BD, BE ), MIN4( BF, CD, CE, CF ), MIN3( DE, DF, EF) ); const int ABC = MAX(AB,C), ABD = MAX(AB,D), ABE = MAX(AB,E), ABF = MAX(AB,F), ACD = MAX(AC,D), ACE = MAX(AC,E), ACF = MAX(AC,F), ADE = MAX(AD,E), ADF = MAX(AD,F), AEF = MAX(AE,F), BCD = MAX(BC,D), BCE = MAX(BC,E), BCF = MAX(BC,F), BDE = MAX(BD,E), BDF = MAX(BD,F), BEF = MAX(BE,F), CDE = MAX(CD,E), CDF = MAX(CD,F), CEF = MAX(CE,F), DEF = MAX(DE,F); in[2] = MIN( MIN4 ( MIN4( ABC, ABD, ABE, ABF ), MIN4( ACD, ACE, ACF, ADE ), MIN4( ADF, AEF, BCD, BCE ), MIN4( BCF, BDE, BDF, BEF )), MIN4( CDE, CDF, CEF, DEF ) ); const int ABCD = MAX(ABC,D), ABCE = MAX(ABC,E), ABCF = MAX(ABC,F), ABDE = MAX(ABD,E), ABDF = MAX(ABD,F), ABEF = MAX(ABE,F), ACDE = MAX(ACD,E), ACDF = MAX(ACD,F), ACEF = MAX(ACE,F), ADEF = MAX(ADE,F), BCDE = MAX(BCD,E), BCDF = MAX(BCD,F), BCEF = MAX(BCE,F), BDEF = MAX(BDE,F), CDEF = MAX(CDE,F); in[3] = MIN4 ( MIN4( ABCD, ABCE, ABCF, ABDE ), MIN4( ABDF, ABEF, ACDE, ACDF ), MIN4( ACEF, ADEF, BCDE, BCDF ), MIN3( BCEF, BDEF, CDEF ) ); const int ABCDE= MAX(ABCD,E), ABCDF= MAX(ABCD,F), ABCEF= MAX(ABCE,F), ABDEF= MAX(ABDE,F), ACDEF= MAX(ACDE,F), BCDEF= MAX(BCDE,F); in[4]= MIN ( MIN4( ABCDE, ABCDF, ABCEF, ABDEF ), MIN ( ACDEF, BCDEF ) ); in[5] = MAX(ABCDE,F); } int main(int argc, char ** argv) { int d[6][6] = { {1, 2, 3, 4, 5, 6}, {6, 5, 4, 3, 2, 1}, {100, 2, 300, 4, 500, 6}, {100, 2, 3, 4, 500, 6}, {1, 200, 3, 4, 5, 600}, {1, 1, 2, 1, 2, 1} }; unsigned long long cycles = rdtsc(); for (int i = 0; i < 6; i++) { sort6(d[i]); } cycles = rdtsc() - cycles; printf("Time is %d/n", (unsigned)cycles); for (int i = 0; i < 6; i++) { printf("d%d : %d %d %d %d %d %d/n", i, d[i][0], d[i][1], d[i][2], d[i][3], d[i][4], d[i][5]); } }

EDITAR:
Solución de orden de rango inspirada en la de Rex Kerr, mucho más rápida que el desorden arriba

static void sort6(int *o) { const int A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5]; const unsigned char AB = A>B, AC = A>C, AD = A>D, AE = A>E, BC = B>C, BD = B>D, BE = B>E, CD = C>D, CE = C>E, DE = D>E, a = AB + AC + AD + AE + (A>F), b = 1 - AB + BC + BD + BE + (B>F), c = 2 - AC - BC + CD + CE + (C>F), d = 3 - AD - BD - CD + DE + (D>F), e = 4 - AE - BE - CE - DE + (E>F); o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E; o[15-a-b-c-d-e]=F; }

Ya que estos son enteros y las comparaciones son rápidas, ¿por qué no calcular el orden de rango directamente?

inline void sort6(int *d) { int e[6]; memcpy(e,d,6*sizeof(int)); int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]); int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]); int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]); int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]); int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]); int o5 = 15-(o0+o1+o2+o3+o4); d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5]; }

Aquí está mi contribución a este hilo: un recorte de 1, 4 espacios optimizado para un vector int de 6 miembros (valp) que contiene valores únicos.

void shellsort (int *valp) { int c,a,*cp,*ip=valp,*ep=valp+5; c=*valp; a=*(valp+4);if (c>a) {*valp= a;*(valp+4)=c;} c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;} cp=ip; do { c=*cp; a=*(cp+1); do { if (c<a) break; *cp=a; *(cp+1)=c; cp-=1; c=*cp; } while (cp>=valp); ip+=1; cp=ip; } while (ip<ep); }

En mi portátil HP dv7-3010so con un Athlon M300 de doble núcleo a 2 Ghz (memoria DDR2) se ejecuta en 165 ciclos de reloj. Este es un promedio calculado a partir de la secuencia de cada secuencia única (6! / 720 en total). Compilado para Win32 utilizando OpenWatcom 1.8. El bucle es esencialmente una ordenación por inserción y tiene 16 instrucciones / 37 bytes de largo.

No tengo un entorno de 64 bits para compilar.

Aquí hay tres métodos de clasificación típicos que representan tres clases diferentes de algoritmos de clasificación:

Insertion Sort: Θ(n^2) Heap Sort: Θ(n log n) Count Sort: Θ(3n)

¿Pero echa un vistazo a la discusión de Stefan Nelsson sobre el algoritmo de clasificación más rápido? donde discute una solución que se reduce a O(n log log n)... verifique su implementación en C

Este algoritmo de clasificación semi-lineal fue presentado por un artículo en 1995:

A. Andersson, T. Hagerup, S. Nilsson y R. Raman. ¿Ordenando en tiempo lineal? En Actas del 27º Simposio Anual ACM sobre Teoría de la Computación, páginas 427-436, 1995.

Creo que su pregunta tiene dos partes.

Lo primero es determinar el algoritmo óptimo. Esto se hace, al menos en este caso, repitiendo cada orden posible (no hay tantos) que le permite calcular el mínimo, el máximo, el promedio y la desviación estándar de las comparaciones y los swaps. Ten un subcampeón o dos a la mano también.
El segundo es optimizar el algoritmo. Se puede hacer mucho para convertir ejemplos de códigos de libros de texto en algoritmos de la vida real e inclinarlos. Si te das cuenta de que un algoritmo no se puede optimizar en la medida necesaria, prueba con un subcampeón.

No me preocuparía demasiado vaciar tuberías (suponiendo que x86 actual): la predicción de bifurcaciones ha avanzado mucho. Lo que me preocuparía es asegurarme de que el código y los datos encajen en una línea de caché (tal vez dos para el código). Una vez allí, las latencias de recuperación son refrescantemente bajas, lo que compensará cualquier bloqueo. También significa que su bucle interno tendrá aproximadamente diez instrucciones, o sea lo que es justo donde debería estar (hay dos bucles internos diferentes en mi algoritmo de clasificación, son 10 instrucciones / 22 bytes y 9/22 respectivamente). Suponiendo que el código no contenga ningún divs, puede estar seguro de que será cegadoramente rápido.

Porté el conjunto de pruebas a una máquina de arquitectura PPC que no puedo identificar (no tuve que tocar el código, solo aumenté las iteraciones de la prueba, usé 8 casos de prueba para evitar contaminar los resultados con mods y reemplazé el rdtsc específico de x86):

Llamada directa a la función de biblioteca qsort : 101

Implementación ingenua (ordenación por inserción) : 299

Tipo de Inserción (Daniel Stutzbach) : 108

Inserción Tipo Desenrollado : 51

Redes de clasificación (Daniel Stutzbach) : 26

Redes de clasificación (Paul R) : 85

Clasificando Redes 12 con Intercambio Rápido : 117

Clasificando Redes 12 Swaps reordenado : 116

Orden del orden : 56

Si bien me gusta mucho la macro de intercambio provista:

#define min(x, y) (y ^ ((x ^ y) & -(x < y))) #define max(x, y) (x ^ ((x ^ y) & -(x < y))) #define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

Veo una mejora (que podría hacer un buen compilador):

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

Tomamos nota de cómo funcionan el mínimo y el máximo y extraemos explícitamente la subexpresión común. Esto elimina completamente las macros mín. Y máx.

Un intercambio XOR puede ser útil en sus funciones de intercambio.

void xorSwap (int *x, int *y) { if (*x != *y) { *x ^= *y; *y ^= *x; *x ^= *y; } }

El if puede causar demasiada divergencia en su código, pero si tiene una garantía de que todas sus intenciones son únicas, esto podría ser útil.

Bueno, si son solo 6 elementos y puede aprovechar el paralelismo, desea minimizar la bifurcación condicional, etc. ¿Por qué no genera todas las combinaciones y prueba el orden? Me atrevería a decir que en algunas arquitecturas, puede ser bastante rápido (siempre que tenga la memoria preasignada)

Descubrí que al menos en mi sistema, las funciones sort6_iterator()y las funciones sort6_iterator_local()definidas a continuación se ejecutaron al menos a la misma velocidad, y con frecuencia notablemente más rápido, que el titular de registro actual anterior:

#define MIN(x, y) (x<y?x:y) #define MAX(x, y) (x<y?y:x) template<class IterType> inline void sort6_iterator(IterType it) { #define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); / const auto b = MAX(*(it + x), *(it + y)); / *(it + x) = a; *(it + y) = b; } SWAP(1, 2) SWAP(4, 5) SWAP(0, 2) SWAP(3, 5) SWAP(0, 1) SWAP(3, 4) SWAP(1, 4) SWAP(0, 3) SWAP(2, 5) SWAP(1, 3) SWAP(2, 4) SWAP(2, 3) #undef SWAP }

Pasé esta función un std::vectoriterador en mi código de tiempo. Sospecho que el uso de iteradores proporciona a g ++ ciertas garantías sobre lo que puede y no puede pasar con la memoria a la que se refiere el iterador, que de otra manera no tendría y son estas garantías las que permiten a g ++ optimizar mejor el código de clasificación (que si Recuerdo correctamente, es también parte de la razón por la que tantos stdalgoritmos, comostd::sort(), generalmente tienen un rendimiento tan obscenamente bueno). Sin embargo, al tiempo que me di cuenta de que el contexto (es decir, el código circundante) en el que se realizó la llamada a la función de clasificación tuvo un impacto significativo en el rendimiento, lo que probablemente se debe a que la función está en línea y luego optimizada. Por ejemplo, si el programa era lo suficientemente simple, entonces generalmente no había mucha diferencia en el rendimiento entre pasar la función de clasificación a un puntero y pasarle un iterador; de lo contrario, el uso de los iteradores generalmente resulta en un rendimiento notablemente mejor y nunca (según mi experiencia hasta ahora) un rendimiento notablemente peor. Sospecho que esto puede deberse a que g ++ puede optimizar globalmente un código suficientemente simple.

Por otra parte, sort6_iterator()es algunas veces (de nuevo, dependiendo del contexto en el que se llama a la función) superado constantemente por la siguiente función de clasificación:

template<class IterType> inline void sort6_iterator_local(IterType it) { #define SWAP(x,y) { const auto a = MIN(data##x, data##y); / const auto b = MAX(data##x, data##y); / data##x = a; data##y = b; } //DD = Define Data #define DD1(a) auto data##a = *(it + a); #define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b); //CB = Copy Back #define CB(a) *(it + a) = data##a; DD2(1,2) SWAP(1, 2) DD2(4,5) SWAP(4, 5) DD1(0) SWAP(0, 2) DD1(3) SWAP(3, 5) SWAP(0, 1) SWAP(3, 4) SWAP(1, 4) SWAP(0, 3) CB(0) SWAP(2, 5) CB(5) SWAP(1, 3) CB(1) SWAP(2, 4) CB(4) SWAP(2, 3) CB(2) CB(3) #undef CB #undef DD2 #undef DD1 #undef SWAP }

Tenga en cuenta que la definición de SWAP()lo siguiente algunas veces da como resultado un rendimiento ligeramente mejor, aunque la mayoría de las veces resulta en un rendimiento ligeramente peor o una diferencia insignificante en el rendimiento.

#define SWAP(x,y) { const auto a = MIN(data##x, data##y); / data##y = MAX(data##x, data##y); / data##x = a; }

Si solo desea un algoritmo de clasificación en el que gcc -O3 sea siempre bueno en la optimización, dependiendo de cómo pase la entrada, pruebe uno de los siguientes dos algoritmos:

template<class T> inline void sort6(T it) { #define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}} #define DD1(a) register auto data##a=*(it+a); #define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b); #define CB1(a) *(it+a)=data##a; #define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b; DD2(1,2) SORT2(1,2) DD2(4,5) SORT2(4,5) DD1(0) SORT2(0,2) DD1(3) SORT2(3,5) SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5) SORT2(1,4) SORT2(0,3) CB1(0) SORT2(2,4) CB1(4) SORT2(1,3) CB1(1) SORT2(2,3) CB2(2,3) #undef CB1 #undef CB2 #undef DD1 #undef DD2 #undef SORT2 }

template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) { #define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);} #define DD1(a) register auto data##a=e##a; #define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b; #define CB1(a) e##a=data##a; #define CB2(a,b) e##a=data##a;e##b=data##b; DD2(1,2) SORT2(1,2) DD2(4,5) SORT2(4,5) DD1(0) SORT2(0,2) DD1(3) SORT2(3,5) SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5) SORT2(1,4) SORT2(0,3) CB1(0) SORT2(2,4) CB1(4) SORT2(1,3) CB1(1) SORT2(2,3) CB2(2,3) #undef CB1 #undef CB2 #undef DD1 #undef DD2 #undef SORT2 }

La razón para usar la registerpalabra clave es porque esta es una de las pocas veces que sabe que desea estos valores en los registros. Sin él register, el compilador lo resolverá la mayor parte del tiempo, pero a veces no lo hace. Usar la registerpalabra clave ayuda a resolver este problema. Normalmente, sin embargo, no use la registerpalabra clave, ya que es más probable que ralentice el código que lo acelere.

Además, tenga en cuenta el uso de plantillas. Esto se hace a propósito, ya que, incluso con la inlinepalabra clave, las funciones de plantilla generalmente se optimizan mucho más agresivamente por las funciones de gcc que las de vainilla C (esto tiene que ver con que gcc necesita lidiar con los punteros de funciones para las funciones de vainilla C, pero no con las de plantilla).

Esta pregunta se está volviendo bastante antigua, pero en realidad tuve que resolver el mismo problema en estos días: agoritmos rápidos para ordenar matrices pequeñas. Pensé que sería una buena idea compartir mi conocimiento. Aunque comencé a usar las redes de clasificación, finalmente logré encontrar otros algoritmos para los cuales el número total de comparaciones realizadas para clasificar cada permutación de 6 valores era menor que con las redes de clasificación y más pequeño que con la clasificación por inserción. No conté el número de swaps; Espero que sea más o menos equivalente (quizás un poco más alto a veces).

El algoritmo sort6utiliza el algoritmo sort4que utiliza el algoritmo sort3. Aquí está la implementación en alguna forma ligera de C ++ (el original tiene una gran cantidad de plantillas para que pueda funcionar con cualquier iterador de acceso aleatorio y cualquier función de comparación adecuada).

Clasificando 3 valores

El siguiente algoritmo es una ordenación por inserción desenrollada. Cuando se deben realizar dos swaps (6 asignaciones), utiliza 4 asignaciones en su lugar:

void sort3(int* array) { if (array[1] < array[0]) { if (array[2] < array[0]) { if (array[2] < array[1]) { std::swap(array[0], array[2]); } else { int tmp = array[0]; array[0] = array[1]; array[1] = array[2]; array[2] = tmp; } } else { std::swap(array[0], array[1]); } } else { if (array[2] < array[1]) { if (array[2] < array[0]) { int tmp = array[2]; array[2] = array[1]; array[1] = array[0]; array[0] = tmp; } else { std::swap(array[1], array[2]); } } } }

Parece un poco complejo porque la ordenación tiene más o menos una rama para cada posible permutación de la matriz, usando comparaciones de 2 ~ 3 y como máximo 4 asignaciones para ordenar los tres valores.

Clasificando 4 valores

Éste llama y sort3luego realiza una orden de inserción desenrollada con el último elemento de la matriz:

void sort4(int* array) { // Sort the first 3 elements sort3(array); // Insert the 4th element with insertion sort if (array[3] < array[2]) { std::swap(array[2], array[3]); if (array[2] < array[1]) { std::swap(array[1], array[2]); if (array[1] < array[0]) { std::swap(array[0], array[1]); } } } }

Este algoritmo realiza de 3 a 6 comparaciones y como máximo 5 swaps. Es fácil desenrollar una ordenación por inserción, pero usaremos otro algoritmo para la última ordenación ...

Clasificando 6 valores

Este utiliza una versión desenrollada de lo que llamé una ordenación de doble inserción . El nombre no es tan bueno, pero es bastante descriptivo, aquí es cómo funciona:

Ordena todo menos el primero y los últimos elementos de la matriz.
Intercambia el primero y los elementos de la matriz si el primero es mayor que el anterior.
Inserte el primer elemento en la secuencia ordenada desde el frente y luego el último elemento desde la parte posterior.

Después del intercambio, el primer elemento siempre es más pequeño que el anterior, lo que significa que, al insertarlos en la secuencia ordenada, no habrá más de N comparaciones para insertar los dos elementos en el peor de los casos: por ejemplo, si el El primer elemento se insertó en la 3ª posición, luego el último no se puede insertar más abajo que la 4ª posición.

void sort6(int* array) { // Sort everything but first and last elements sort4(array+1); // Switch first and last elements if needed if (array[5] < array[0]) { std::swap(array[0], array[5]); } // Insert first element from the front if (array[1] < array[0]) { std::swap(array[0], array[1]); if (array[2] < array[1]) { std::swap(array[1], array[2]); if (array[3] < array[2]) { std::swap(array[2], array[3]); if (array[4] < array[3]) { std::swap(array[3], array[4]); } } } } // Insert last element from the back if (array[5] < array[4]) { std::swap(array[4], array[5]); if (array[4] < array[3]) { std::swap(array[3], array[4]); if (array[3] < array[2]) { std::swap(array[2], array[3]); if (array[2] < array[1]) { std::swap(array[1], array[2]); } } } } }

Mis pruebas en cada permutación de 6 valores muestran que estos algoritmos siempre realizan entre 6 y 13 comparaciones. No calculé la cantidad de swaps realizados, pero no espero que sea superior a 11 en el peor de los casos.

Espero que esto ayude, incluso si esta pregunta ya no representa un problema real :)

EDITAR: después de colocarlo en el punto de referencia proporcionado, es claramente más lento que la mayoría de las alternativas interesantes. Tiende a funcionar un poco mejor que el ordenamiento por inserción desenrollada, pero eso es todo. Básicamente, no es el mejor tipo para los enteros, pero podría ser interesante para los tipos con una operación de comparación costosa.

Estoy ansioso por probar esto y aprender de estos ejemplos, pero primero algunos tiempos de mi Powerbook G4 PPC de 1.5 GHz con memoria RAM DDR de 1 GB. (Tomé prestado un temporizador similar a rdtsc para el PPC de http://www.mcs.anl.gov/~kazutomo/rdtsc.html para los horarios). Ejecuté el programa varias veces y los resultados absolutos variaron pero consistentemente La prueba más rápida fue "Insertion Sort (Daniel Stutzbach)", con "Insertion Sort Unrolled" en segundo lugar.

Aquí está el último conjunto de veces:

**Direct call to qsort library function** : 164 **Naive implementation (insertion sort)** : 138 **Insertion Sort (Daniel Stutzbach)** : 85 **Insertion Sort Unrolled** : 97 **Sorting Networks (Daniel Stutzbach)** : 457 **Sorting Networks (Paul R)** : 179 **Sorting Networks 12 with Fast Swap** : 238 **Sorting Networks 12 reordered Swap** : 236 **Rank Order** : 116

Nunca optimice mín / máx sin realizar evaluaciones comparativas y observar el ensamblaje real generado por el compilador. Si dejo que GCC optimice el mínimo con instrucciones de movimiento condicional, obtengo una aceleración del 33%:

#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }

(280 vs. 420 ciclos en el código de prueba). Hacer max con?: Es más o menos lo mismo, casi perdido en el ruido, pero lo anterior es un poco más rápido. Este SWAP es más rápido con GCC y Clang.

Los compiladores también están haciendo un trabajo excepcional en la asignación de registros y el análisis de alias, moviendo efectivamente d [x] a las variables locales por adelantado, y solo copiando a la memoria al final. De hecho, lo hacen incluso mejor que si trabajara completamente con variables locales (como d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]). Estoy escribiendo esto porque estás asumiendo una fuerte optimización y, sin embargo, intentas ser más astuto que el compilador en min / max. :)

Por cierto, probé Clang y GCC. Hacen la misma optimización, pero debido a las diferencias de programación, los dos tienen alguna variación en los resultados, no puedo decir realmente cuál es más rápido o más lento. GCC es más rápido en las redes de clasificación, Clang en las ordenaciones cuadráticas.

Sólo para completar, también son posibles las clasificaciones de burbujas desenrolladas y las inserciones. Aquí está el tipo de burbuja:

SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5); SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(0,1); SWAP(1,2); SWAP(0,1);

Y aquí está el tipo de inserción:

//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } } //Faster on x86, probably slower on ARM or similar: #define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; } static inline void sort6_insertion_sort_unrolled_v2(int * d){ int t; t = d[1]; ITER(0); t = d[2]; ITER(1); ITER(0); t = d[3]; ITER(2); ITER(1); ITER(0); t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0); t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);

Este tipo de inserción es más rápido que el de Daniel Stutzbach, y es especialmente bueno en una GPU o una computadora con predicación porque ITER se puede hacer con solo 3 instrucciones (vs. 4 para SWAP). Por ejemplo, aquí está la t = d[2]; ITER(1); ITER(0);línea en el ensamblaje ARM:

MOV r6, r2 CMP r6, r1 MOVLT r2, r1 MOVLT r1, r6 CMP r6, r0 MOVLT r1, r0 MOVLT r0, r6

Para seis elementos, la ordenación por inserción es competitiva con la red de clasificación (12 intercambios frente a 15 iteraciones equilibra 4 instrucciones / intercambio frente a 3 instrucciones / iteración); Burbuja, por supuesto, es más lento. Pero no va a ser cierto cuando el tamaño crezca, ya que la ordenación por inserción es O (n ^ 2), mientras que las redes de clasificación son O (n log n).

Ordenar 4 artículos con el uso cmp == 0. Los números de cmp son ~ 4.34 (los nativos de FF tienen ~ 4.52), pero tómense 3 veces más que fusionando listas. Pero mejor menos operaciones de cmp, si tienes números grandes o texto grande. Edición: error reparado

Prueba en línea http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm

Sé que llego muy tarde, pero estaba interesado en experimentar con algunas soluciones diferentes. Primero, limpié esa pasta, la compilé y la puse en un repositorio. Mantuve algunas soluciones indeseables como callejones sin salida para que otros no lo intentaran. Entre esto estaba mi primera solución, que intentaba asegurar que x1> x2 se calculara una vez. Después de la optimización, no es más rápido que las otras versiones simples.

Agregué una versión en bucle del orden de clasificación, ya que mi propia aplicación de este estudio es para clasificar de 2 a 8 elementos, por lo que dado que hay una cantidad variable de argumentos, es necesario un bucle. Esta es también la razón por la que ignoré las soluciones de red de clasificación.

El código de prueba no probó que los duplicados se manejaron correctamente, por lo que aunque las soluciones existentes eran todas correctas, agregué un caso especial al código de prueba para garantizar que los duplicados se manejaran correctamente.

Luego, escribí un tipo de inserción que está completamente en los registros AVX. En mi máquina es un 25% más rápido que los otros tipos de inserción, pero un 100% más lento que el orden de clasificación. Hice esto exclusivamente para el experimento y no tenía ninguna expectativa de que fuera mejor debido a la ramificación en la clasificación de inserción.

static inline void sort6_insertion_sort_avx(int* d) { __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0); __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7); __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6); __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX); __m256i val, gt, permute; unsigned j; // 8 / 32 = 2^-2 #define ITER(I) / val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));/ gt = _mm256_cmpgt_epi32(sorted, val);/ permute = _mm256_blendv_epi8(index, shlpermute, gt);/ j = ffs( _mm256_movemask_epi8(gt)) >> 2;/ sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),/ val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j))) ITER(1); ITER(2); ITER(3); ITER(4); ITER(5); int x[8]; _mm256_storeu_si256((__m256i*)x, sorted); d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5]; #undef ITER }

Luego, escribí un orden de clasificación usando AVX. Esto coincide con la velocidad de las otras soluciones de orden de clasificación, pero no es más rápido. El problema aquí es que solo puedo calcular los índices con AVX, y luego tengo que hacer una tabla de índices. Esto se debe a que el cálculo se basa en el destino y no en el origen. Consulte Conversión de índices basados en origen a índices basados en destino.

static inline void sort6_rank_order_avx(int* d) { __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7); __m256i one = _mm256_set1_epi32(1); __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX); __m256i rot = src; __m256i index = _mm256_setzero_si256(); __m256i gt, permute; __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6); __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7); __m256i srcIx = dstIx; __m256i eq = one; __m256i rotIx = _mm256_setzero_si256(); #define INC(I)/ rot = _mm256_permutevar8x32_epi32(rot, ror);/ gt = _mm256_cmpgt_epi32(src, rot);/ index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));/ index = _mm256_add_epi32(index, _mm256_and_si256(eq,/ _mm256_cmpeq_epi32(src, rot)));/ eq = _mm256_insert_epi32(eq, 0, I) INC(0); INC(1); INC(2); INC(3); INC(4); int e[6]; e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5]; int i[8]; _mm256_storeu_si256((__m256i*)i, index); d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5]; }

El repositorio se puede encontrar aquí: https://github.com/eyepatchParrot/sort6/

Si la clasificación por inserción es razonablemente competitiva aquí, recomendaría probar un shellsort. Me temo que 6 elementos es probablemente demasiado pequeño para estar entre los mejores, pero vale la pena intentarlo.

Código de ejemplo, no probado, no corrugado, etc. Desea ajustar la secuencia inc = 4 e inc - = 3 para encontrar el óptimo (int. Inc = 2, inc - = 1 por ejemplo).

static __inline__ int sort6(int * d) { char j, i; int tmp; for (inc = 4; inc > 0; inc -= 3) { for (i = inc; i < 5; i++) { tmp = a[i]; j = i; while (j >= inc && a[j - inc] > tmp) { a[j] = a[j - inc]; j -= inc; } a[j] = tmp; } } }

No creo que esto gane, pero si alguien publica una pregunta sobre la clasificación de 10 elementos, quién sabe ...

Según Wikipedia, esto puede incluso combinarse con redes de clasificación: Pratt, V (1979). Shellsort y redes de clasificación (disertaciones sobresalientes en ciencias de la computación). Guirnalda. ISBN 0-824-04406-1

Tal vez yo soy tarde a la fiesta, pero al menos mi aportación es un nuevo enfoque.

El código realmente debe estar en línea
incluso si están en línea, hay demasiadas ramas
la parte de análisis es básicamente O (N (N-1)) que parece bien para N = 6
el código podría ser más efectivo si el costo deswap sería más alto (irt el costo de compare)
Confío en que las funciones estáticas estén en línea.
El método está relacionado con el ordenamiento por rango.
- En lugar de rangos, se utilizan los rangos relativos (compensaciones).
- la suma de los rangos es cero para cada ciclo en cualquier grupo de permutación.
- en lugar de SWAP()incluir dos elementos, se persiguen los ciclos, necesitando solo una temperatura, y un intercambio (registro-> registro) (nuevo <- antiguo).

Actualización: cambié un poco el código, algunas personas usan compiladores de C ++ para compilar el código C ...

#include <stdio.h> #if WANT_CHAR typedef signed char Dif; #else typedef signed int Dif; #endif static int walksort (int *arr, int cnt); static void countdifs (int *arr, Dif *dif, int cnt); static void calcranks(int *arr, Dif *dif); int wsort6(int *arr); void do_print_a(char *msg, int *arr, unsigned cnt) { fprintf(stderr,"%s:", msg); for (; cnt--; arr++) { fprintf(stderr, " %3d", *arr); } fprintf(stderr,"/n"); } void do_print_d(char *msg, Dif *arr, unsigned cnt) { fprintf(stderr,"%s:", msg); for (; cnt--; arr++) { fprintf(stderr, " %3d", (int) *arr); } fprintf(stderr,"/n"); } static void inline countdifs (int *arr, Dif *dif, int cnt) { int top, bot; for (top = 0; top < cnt; top++ ) { for (bot = 0; bot < top; bot++ ) { if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; } } } return ; } /* Copied from RexKerr ... */ static void inline calcranks(int *arr, Dif *dif){ dif[0] = (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]); dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]); dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]); dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]); dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]); dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]); } static int walksort (int *arr, int cnt) { int idx, src,dst, nswap; Dif difs[cnt]; #if WANT_REXK calcranks(arr, difs); #else for (idx=0; idx < cnt; idx++) difs[idx] =0; countdifs(arr, difs, cnt); #endif calcranks(arr, difs); #define DUMP_IT 0 #if DUMP_IT do_print_d("ISteps ", difs, cnt); #endif nswap = 0; for (idx=0; idx < cnt; idx++) { int newval; int step,cyc; if ( !difs[idx] ) continue; newval = arr[idx]; cyc = 0; src = idx; do { int oldval; step = difs[src]; difs[src] =0; dst = src + step; cyc += step ; if(dst == idx+1)idx=dst; oldval = arr[dst]; #if (DUMP_IT&1) fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d/n##/n" , nswap, cyc, step, idx, oldval, newval , src, dst, difs[dst], arr[dst] , newval ); do_print_a("Array ", arr, cnt); do_print_d("Steps ", difs, cnt); #endif arr[dst] = newval; newval = oldval; nswap++; src = dst; } while( cyc); } return nswap; } /*************/ int wsort6(int *arr) { return walksort(arr, 6); }

Trate de ''combinar lista ordenada'' ordenar. :) Utilice dos matrices. Más rápido para arsenal pequeño y grande.
Si concuerdas, solo verificas donde insertar. Otros valores más grandes que no necesitas comparar (cmp = ab> 0).
Para 4 números, puede usar el sistema 4-5 cmp (~ 4.6) o 3-6 cmp (~ 4.9). Tipo de burbuja usar 6 cmp (6). Un montón de cmp para grandes números de código más lento.
Este código utiliza 5 cmp (no ordenación MSL):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}

MSL principal 9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8

código js