El tipo más rápido de longitud fija de 6 int.

401

Respondiendo a otra pregunta de Stack Overflow ( esta ), me topé con un subproblema interesante. ¿Cuál es la forma más rápida de ordenar una matriz de 6 enteros?

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 tubería de instrucciones (que tiene un costo muy alto), probablemente deberíamos minimizar las ramas, los saltos y cualquier otro tipo de interrupción del flujo de control (como los ocultos detrás de los puntos de secuencia en &&o ||).
  • el espacio es limitado y la minimización de los registros y el uso de la memoria es un problema, idealmente en el lugar es probablemente el mejor.

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 de Michael Abrash y sus secuelas .

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

  • el ejemplo es simple y fácil de entender y medir, no involucra mucha habilidad C
  • muestra los efectos de 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);
}

Resultados crudos

A medida que aumenta el número de variantes, las reuní todas en un conjunto de pruebas que se puede encontrar aquí . Las pruebas reales utilizadas son un poco menos ingenuas que las mostradas anteriormente, gracias a Kevin Stock. Puede compilarlo y ejecutarlo en su propio entorno. Estoy bastante interesado por el comportamiento en diferentes compilaciones / arquitectura de destino. (OK chicos, pónganlo en respuestas, haré +1 en cada contribuyente de un nuevo conjunto de resultados).

Le di la respuesta a Daniel Stutzbach (para jugar al 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 (tipo de inserción): 285.70
  • Tipo de inserción (Daniel Stutzbach): 142.12
  • Tipo de inserción desenrollado: 125.47
  • Orden de rango: 102.26
  • Orden de clasificación con registros: 58.03
  • Redes de clasificación (Daniel Stutzbach): 111.68
  • Redes de clasificación (Paul R): 66.36
  • Clasificación de redes 12 con intercambio rápido: 58.86
  • Ordenar redes 12 Reordenado Swap: 53.74
  • Sorting Networks 12 reordenado Simple Swap: 31.54
  • Red de clasificación reordenada con intercambio rápido: 31.54
  • Red de clasificación reordenada con intercambio rápido V2: 33.63
  • Clasificación de burbujas 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 (tipo de inserción): 135,60
  • Tipo de inserción (Daniel Stutzbach): 142.11
  • Tipo de inserción desenrollado: 126.75
  • Orden de rango: 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
  • Clasificación de redes 12 con intercambio rápido: 61,98
  • Ordenar redes 12 Reordenado Swap: 54.67
  • Sorting Networks 12 reordenado Simple Swap: 31.54
  • Red de clasificación reordenada con intercambio rápido: 31.24
  • Red de clasificación reordenada con intercambio rápido V2: 33.07
  • Clasificación de burbujas 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

Tipo de inserción (Daniel Stutzbach)

Como se esperaba, minimizar las ramas es una buena idea.

Redes de clasificación (Daniel Stutzbach)

Mejor que el tipo de inserción. Me preguntaba si el efecto principal no se obtenía al evitar el bucle externo. Lo probé mediante un tipo de inserción desenrollado para verificar y, de hecho, obtenemos aproximadamente las mismas cifras (el código está aquí ).

Redes de clasificación (Paul R)

Lo mejor por mucho. El código real que solía probar está aquí . Todavía no sé por qué es casi dos veces más rápido que la otra implementación de red de clasificación. Paso de parámetros? Max rápido?

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

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

También es interesante notar que el intercambio sin ramas parece ser mucho (4 veces) menos eficiente que el simple que usa if en la arquitectura PPC.

Llamar a la biblioteca qsort

Para dar otro punto de referencia, también intenté, como se sugiere, llamar a la biblioteca qsort (el código está aquí ). Como se esperaba, 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 otros, parece incluso más rápido (realmente estoy sorprendido por eso, ya que la biblioteca qsort usa 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 cómputo 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 las órdenes de clasificación). 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 ordenar 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.

actualización :

Como las cifras publicadas arriba muestran que este efecto aún se mejoró con versiones posteriores de gcc y el orden de clasificación se volvió consistentemente dos veces más rápido que cualquier otra alternativa.

Clasificación de redes 12 con intercambio 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 ramificaciones? Mi hipótesis era que tenía menos dependencias del tipo lectura después de escritura, lo que permite un mejor uso del planificador de instrucciones superescalar del x86. Eso me dio una idea: reordenar los intercambios para minimizar las dependencias de lectura después de escritura. En pocas palabras: cuando lo hace SWAP(1, 2); SWAP(0, 2);, debe esperar a que termine el primer intercambio antes de realizar el segundo porque ambos acceden a una celda de memoria común. Cuando lo hace, 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.

Clasificación de redes 12 con intercambio simple

Un año después de la publicación original, Steinar H. Gunderson sugirió que no deberíamos intentar burlar al compilador y mantener el código de intercambio simple. De hecho, es una buena idea ya que el código resultante es aproximadamente 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 mucho sobre la psicología del programador) es que hace un año ninguno de los usuarios intentó esa versión de intercambio. El código que solía probar está aquí . Otros sugirieron otras formas de escribir un intercambio rápido en C, pero produce el mismo rendimiento que el simple con un compilador decente.

El "mejor" código es ahora el siguiente:

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 pobre, su simple beneficio es ser corto, 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 coloca cada intercambio en un promedio de 4 ciclos. A eso lo llamo asombrosamente rápido. ¿Alguna otra mejora posible?

kriss
fuente
2
¿Tienes algunas restricciones en las entradas? Por ejemplo, podemos suponer que para cualquier 2 x, y x-yy x+yno causará desbordamiento o desbordamiento?
Matthieu M.
3
Debería intentar combinar mi red de clasificación de 12 intercambios con la función de intercambio sin ramas de Paul. Su solución pasa todos los parámetros como elementos separados en la pila en lugar de un puntero único a una matriz. Eso también podría marcar la diferencia.
Daniel Stutzbach
2
Tenga en cuenta que la implementación correcta de rdtsc en 64 bits se __asm__ volatile (".byte 0x0f, 0x31; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");debe a que rdtsc pone la respuesta en EDX: EAX mientras que GCC lo espera en un único registro de 64 bits. Puede ver el error compilando en -O3. También vea a continuación mi comentario a Paul R sobre un SWAP más rápido.
Paolo Bonzini
3
@Tyler: ¿Cómo se implementa a nivel de ensamblaje sin una rama?
Loren Pechtel
44
@Loren: CMP EAX, EBX; SBB EAX, EAXpondrá 0 o 0xFFFFFFFF EAXdependiendo de si EAXes mayor o menor que EBX, respectivamente. SBBes "restar con préstamo", la contrapartida de ADC("agregar con acarreo"); el bit de estado al que se refiere es el bit de acarreo. Por otra parte, recuerdo eso ADCy SBBtuve una latencia y un rendimiento terribles en el Pentium 4 vs. ADDy SUB, y todavía eran dos veces más lentos en las CPU Core. Desde el 80386 también hay instrucciones de SETccalmacenamiento CMOVcccondicional y movimiento condicional, pero también son lentas.
j_random_hacker

Respuestas:

162

Para cualquier optimización, siempre es mejor probar, probar, probar. Intentaría al menos ordenar las redes y la inserción. Si estuviera apostando, apostaría mi dinero en el tipo 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 funciona mejor en datos ordenados o casi ordenados, por lo que será la mejor opción si hay una probabilidad superior a la media de datos casi ordenados.

El algoritmo que publicó es similar a un tipo de inserción, pero parece que ha minimizado el número de intercambios a costa de más comparaciones. Sin embargo, las comparaciones son mucho más caras que los intercambios, ya que las ramas pueden hacer que la tubería de instrucciones se detenga.

Aquí hay una implementación de clasificación 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. Terminar 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
}
Daniel Stutzbach
fuente
99
+1: bueno, lo hiciste con 12 intercambios en lugar de los 13 en mi red codificada a mano y derivada empíricamente arriba. Le daría otro +1 si pudiera por el enlace al sitio que genera redes para usted, ahora marcado.
Paul R
99
Esta es una idea fantástica para una función de clasificación de propósito general si espera que la mayoría de las solicitudes sean matrices de pequeño tamaño. Utilice una declaración de cambio para los casos que desea optimizar, utilizando este procedimiento; deje que el caso predeterminado use una función de clasificación de biblioteca.
Mark Ransom
55
@Mark Una buena función de clasificación de bibliotecas ya tendrá una ruta rápida para arreglos pequeños. Muchas bibliotecas modernas utilizarán un QuickSort o MergeSort recursivo que cambia a InsertionSort después de recurrir a n < SMALL_CONSTANT.
Daniel Stutzbach
3
@ Mark Bueno, una función de clasificación de la biblioteca C requiere que especifique la operación de comparación a través de un portero de funciones. La sobrecarga de llamar a una función para cada comparación es enorme. Por lo general, sigue siendo el camino más limpio, porque rara vez es una ruta crítica en el programa. Sin embargo, si es la ruta crítica, realmente podemos ordenar mucho más rápido si sabemos que estamos ordenando enteros y exactamente 6 de ellos. :)
Daniel Stutzbach
77
@tgwh: el intercambio XOR es casi siempre una mala idea.
Paul R
63

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 miny ramificaciones muy eficientes maxpara esto, ya que eso es efectivamente a lo que se reduce este código: una secuencia miny maxoperaciones (13 de cada una, en total). Lo dejo como 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 SIMD tienen instrucciones mínimas / máximas de vectores) y también a implementaciones de GPU (por ejemplo, CUDA - al no tener ramificaciones, no hay problemas con la divergencia de deformación, etc.).

Ver también: Implementación rápida del algoritmo para ordenar una lista muy pequeña

Paul R
fuente
1
Para algunos trucos para min / max: graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
Rubys
1
@Paul: en el contexto real de uso de CUDA, sin duda es la mejor respuesta. Comprobaré si también está (y cuánto) en el contexto de golf x64 y publicaré el resultado.
kriss
1
Sort3sería más rápido (en la mayoría de las arquitecturas, de todos modos) si notaras que (a+b+c)-(min+max)es el número central.
Rex Kerr
1
@Rex: Ya veo, eso se ve bien. Para arquitecturas SIMD como AltiVec y SSE, sería el mismo número de ciclos de instrucción (max y min son instrucciones de ciclo único como sumar / restar), pero para una CPU escalar normal, su método se ve mejor.
Paul R
2
Si dejo que GCC Optimizar minutos con instrucciones de movimiento condicional consigo un aumento de velocidad 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; }. Aquí no estoy usando?: Para d [y] porque da un rendimiento ligeramente peor, pero está casi en el ruido.
Paolo Bonzini
45

Dado que estos son enteros y las comparaciones son rápidas, ¿por qué no calcular el orden de clasificación de cada uno 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];
}
Rex Kerr
fuente
@Rex: con gcc -O1 está por debajo de 1000 ciclos, bastante rápido pero más lento que ordenar la red. ¿Alguna idea para mejorar el código? Tal vez si pudiéramos evitar la copia de matriz ...
kriss
@kriss: Es más rápido que la red de clasificación para mí con -O2. ¿Hay alguna razón por la cual -O2 no está bien, o también es más lento para usted en -O2? Tal vez es una diferencia en la arquitectura de la máquina?
Rex Kerr
1
@Rex: lo siento, me perdí el patrón> vs> = a primera vista. Funciona en todos los casos.
kriss
3
@kriss: Ajá. Eso no es del todo sorprendente: hay muchas variables flotando y deben ordenarse cuidadosamente y almacenarse en caché en los registros, etc.
Rex Kerr
2
@SSpoke 0+1+2+3+4+5=15Dado que falta uno de ellos, 15 menos la suma del resto produce uno perdido
Glenn Teitelbaum
35

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

Al observar el ensamblaje generado por gcc 4.5.2, observé que se realizan cargas y almacenes para cada intercambio, lo 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 de allí, los registros se necesitan primero y se usan 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 se 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 orden. 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 (usando -O1, late -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é, modifiqué el conjunto de pruebas para informar también los relojes por tipo y ejecuté 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é probar en una CPU 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
Kevin Stock
fuente
Su idea de las variables de registro debe aplicarse a la solución de "Orden de clasificación" de Rex Kerr. Eso debería ser más rápido, y quizás entonces la -O3optimización no sea contraproducente.
cdunn2001
1
@ cdunn2001 Lo acabo de probar, no veo mejoras (excepto algunos ciclos en -O0 y -Os). Mirando el asm, parece que gcc ya logró usar registros y eliminar la llamada a memcpy.
Kevin Stock
¿Le importaría agregar la versión de intercambio simple a su conjunto de pruebas? Supongo que podría ser interesante compararlo con el intercambio rápido de ensamblaje optimizado a mano.
kriss
1
Su código todavía usa el intercambio de Gunderson, el mío sería #define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }.
Paolo Bonzini
@Paolo Bonzini: Sí, tengo la intención de agregar un caso de prueba con el suyo, pero aún no tuve tiempo. Pero evitaré el montaje en línea.
kriss
15

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 enteros son solo de 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 un tipo de red en el ensamblaje que usa 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), usando solo una instrucción PADDB (vectorized add) y en algunos casos también una instrucción PAND (bit a bit Y).

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

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 ("Ordenar redes 12 con intercambio simple"). Modifiqué esa implementación para usar charelementos de matriz durante mis pruebas, para que la comparación sea justa.

Debo señalar 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 llamadas 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, puede leer este artículo . Puede usar el siguiente prototipo C para llamar a la función desde su código C:

void simd_sort_6(char *values);
Joe Crivello
fuente
Sería interesante comparar el suyo con otras propuestas de nivel de ensamblaje. El desempeño comparado de la implementación no los incluye. Usar SSE suena bien de todos modos.
kriss
Otra área de investigación futura sería la aplicación de las nuevas instrucciones Intel AVX a este problema. Los vectores más grandes de 256 bits son lo suficientemente grandes como para adaptarse a 8 DWORD.
Joe Crivello
1
En lugar de pxor / pinsrd xmm4, mem, 0, ¡solo úsalo movd!
Peter Cordes
14

El código de prueba es bastante malo; desborda la matriz inicial (¿no leen aquí las advertencias del compilador?), printf está imprimiendo los elementos incorrectos, usa .byte para rdtsc sin ninguna buena razón, solo hay una ejecución (!), no hay nada que verifique que el 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 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 cambie 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 aproximadamente un 65% más rápido para mí (Debian gcc 4.4.5 con -O2, amd64, Core i7).

Steinar H. Gunderson
fuente
OK, el código de prueba es pobre. Siéntase libre de mejorarlo. Y sí, puedes usar el código de ensamblaje. ¿Por qué no ir hasta el final y codificarlo completamente usando el ensamblador x86? Puede ser un poco menos portátil, pero ¿por qué molestarse?
kriss
Gracias por notar el desbordamiento de la matriz, lo corregí. Es posible que otras personas no lo hayan notado porque hicieron clic en el enlace para copiar / pegar el código, donde no hay desbordamiento.
kriss
44
Ni siquiera necesitas un ensamblador, en realidad; si simplemente suelta todos los trucos inteligentes, GCC reconocerá la secuencia e insertará los movimientos condicionales por usted: #define min (a, b) ((a <b)? a: b) #define max (a, b) ( (a <b)? b: a) #define SWAP (x, y) {int a = min (d [x], d [y]); int b = max (d [x], d [y]); d [x] = a; d [y] = b; } Sale tal vez un poco más lento que la variante asm en línea, pero eso es difícil de decir dada la falta de evaluación comparativa adecuada.
Steinar H. Gunderson el
3
… Y finalmente, si sus números son flotantes, y no tiene que preocuparse por NaN, etc., GCC puede convertir esto en instrucciones SSE minss / maxss, que aún es ~ 25% más rápido. Moraleja: suelta los ingeniosos trucos de bitfiddling y deja que el compilador haga su trabajo. :-)
Steinar H. Gunderson
13

Si bien me gusta la macro de intercambio proporcionada:

#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 un buen compilador podría hacer):

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

Tomamos nota de cómo funcionan min y max y extraemos la sub-expresión común explícitamente. Esto elimina las macros mín. Y máx. Por completo.

phkahler
fuente
Eso los lleva al revés, observe que d [y] obtiene el máximo, que es x ^ (subexpresión común).
Kevin Stock
Me di cuenta de lo mismo; Creo que su implementación es correcta lo que desea en d[x]lugar de x(lo mismo para y), y d[y] < d[x]para la desigualdad aquí (sí, diferente del código min / max).
Tyler
Intenté con su intercambio, pero la optimización local tiene efectos negativos a un nivel mayor (supongo que introduce dependencias). Y el resultado es más lento que el otro intercambio. Pero como puede ver con la nueva solución propuesta, de hecho hubo mucho rendimiento para obtener un intercambio de optimización.
kriss
12

Nunca optimice min / max sin benchmarking y mirando el ensamblaje generado por el compilador real. Si dejo que GCC optimice el mínimo con instrucciones de movimiento condicionales, obtengo un 33% de aceleración:

#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). Doing max with?: Es más o menos lo mismo, casi se pierde 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 de nuevo a la memoria al final. De hecho, lo hacen aún mejor que si trabajaras completamente con variables locales (como d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]). Escribo esto porque está asumiendo una fuerte optimización y, sin embargo, está intentando burlar al 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 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 los tipos cuadráticos.

Solo para completar, también es posible el tipo de burbuja desenrollada y los tipos de inserción. 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 predicció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 clasificación de inserción es competitiva con la red de clasificación (12 swaps vs. 15 iteraciones equilibra 4 instrucciones / intercambio vs. 3 instrucciones / iteración); tipo de burbuja, por supuesto, es más lento. Pero no será cierto cuando aumente el tamaño, ya que la ordenación por inserción es O (n ^ 2) mientras que las redes de ordenación son O (n log n).

revs Paolo Bonzini
fuente
1
Más o menos relacionado: envié un informe a GCC para que pudiera implementar la optimización directamente en el compilador. No estoy seguro de que se haga, pero al menos puedes seguir cómo evoluciona.
Morwenn
11

Porté el conjunto de pruebas a una máquina de arquitectura PPC que no puedo identificar (no tuve que tocar el código, solo aumente las iteraciones de la prueba, use 8 casos de prueba para evitar resultados contaminantes con modificaciones y reemplace el rdtsc específico x86):

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

Implementación ingenua (tipo de inserción) : 299

Tipo de inserción (Daniel Stutzbach) : 108

Tipo de inserción desenrollado : 51

Redes de clasificación (Daniel Stutzbach) : 26

Redes de clasificación (Paul R) : 85

Clasificación de redes 12 con intercambio rápido : 117

Ordenar redes 12 Reordenado Intercambio : 116

Orden de rango : 56

jheriko
fuente
1
Muy interesante. Parece que el intercambio sin ramas es una mala idea en PPC. También puede ser un efecto relacionado con el compilador. ¿Cuál fue usado?
kriss
Es una rama del compilador gcc: la lógica min, max probablemente no tenga ramificaciones; inspeccionaré el desmontaje y se lo haré saber, pero a menos que el compilador sea lo suficientemente inteligente como para incluir algo como x <y sin un if todavía se convierte en una rama, en x86 / x64 la instrucción CMOV podría evitar esto, pero no existe tal instrucción para valores de punto fijo en PPC, solo flotantes. Podría incursionar en esto mañana y hacerle saber: recuerdo que hubo un min / max sin ramas mucho más simple en la fuente Winamp AVS, pero iirc fue solo para flotadores, pero podría ser un buen comienzo para un enfoque verdaderamente sin ramas.
jheriko
44
Aquí está una min sucursales / max para PPC con entradas sin signo: subfc r5,r4,r3; subfe r6,r6,r6; andc r6,r5,r6; add r4,r6,r4; subf r3,r6,r3. r3 / r4 son entradas, r5 / r6 son registros de memoria virtual, en la salida r3 obtiene el mínimo y r4 obtiene el máximo. Debe ser decentemente programable a mano. Lo encontré con el superoptimizador GNU, comenzando con secuencias mín. Y máx. De 4 instrucciones y buscando manualmente dos que pudieran combinarse. Para entradas con signo, por supuesto, puede agregar 0x80000000 a todos los elementos al principio y restarlo nuevamente al final, y luego trabajar como si no estuvieran firmados.
Paolo Bonzini
7

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 la garantía de que todos sus ints son únicos, esto podría ser útil.

naj
fuente
1
xor swap también funciona para valores iguales ... x ^ = y establece x a 0, y ^ = x deja y como y (== x), x ^ = y establece x a y
jheriko
11
Cuando no funciona es cuándo xy yapunta a la misma ubicación.
hobbs
De todos modos, cuando se usa con redes de clasificación, nunca llamamos con x e y apuntando a la misma ubicación. Todavía hay que encontrar una manera de evitar las pruebas, que es mayor para obtener el mismo efecto que el intercambio sin ramas. Tengo una idea para lograr eso.
kriss
5

Estoy ansioso por probar esto y aprender de estos ejemplos, pero primero algunos tiempos de mi Powerbook G4 PPC de 1.5 GHz con 1 GB de RAM DDR. (Tomé prestado un temporizador similar a rdtsc para PPC de http://www.mcs.anl.gov/~kazutomo/rdtsc.html para los horarios). Ejecuté el programa varias veces y los resultados absolutos variaron, pero el 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
Nico
fuente
4

Aquí está mi contribución a este hilo: un shellsort optimizado de 1, 4 gap para un vector int (valp) de 6 miembros 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 computadora 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 del tiempo de cada secuencia única (6! / 720 en total). Compilado a Win32 usando OpenWatcom 1.8. El bucle es esencialmente un tipo de inserción y tiene 16 instrucciones / 37 bytes de longitud.

No tengo un entorno de 64 bits para compilar.

Olof Forshell
fuente
bonito. Lo agregaré al testuite más largo
kriss
3

Si el tipo de inserción es razonablemente competitivo aquí, recomendaría probar un shellsort. Me temo que 6 elementos probablemente sean demasiado pequeños para estar entre los mejores, pero puede valer la pena intentarlo.

Código de ejemplo, sin probar, sin depurar, etc. Desea ajustar la secuencia inc = 4 e inc - = 3 para encontrar la secuencia óptima (pruebe 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 cómo ordenar 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

revs gcp
fuente
siéntase libre de proponer alguna implementación :-)
kriss
Propuesta agregada. Disfruta los bichos.
gcp
3

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 garantizar 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 ordenar de 2 a 8 elementos, por lo que, dado que hay un número 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 manejaran correctamente, por lo que si bien las soluciones existentes eran 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. Lo hice solo para experimentar y no esperaba que fuera mejor debido a la ramificación en el tipo 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 rango, 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 la fuente. 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/

parche
fuente
1
Puede usar vmovmskpsen vectores enteros (con un reparto para mantener felices a los intrínsecos), evitando la necesidad de desplazar a la derecha el resultado de bitscan ( ffs).
Peter Cordes
1
Puede agregar 1 condicionalmente en función de un cmpgtresultado restándolo , en lugar de enmascararlo con set1(1). por ejemplo, index = _mm256_sub_epi32(index, gt)lo haceindex -= -1 or 0;
Peter Cordes
1
eq = _mm256_insert_epi32(eq, 0, I)no es una manera eficiente de poner a cero un elemento si se compila tal como está escrito (especialmente para elementos fuera del 4 bajo, porque vpinsrdsolo está disponible con un destino XMM; los índices superiores a 3 tienen que ser emulados). En cambio, _mm256_blend_epi32( vpblendd) con un vector cero. vpblenddes una instrucción single-uop que se ejecuta en cualquier puerto, frente a una combinación aleatoria que necesita el puerto 5 en las CPU de Intel. ( agner.org/optimize ).
Peter Cordes
1
Además, puede considerar generar los rotvectores con diferentes barajaduras de la misma fuente, o al menos ejecutar 2 cadenas dep en paralelo que utilice alternativamente, en lugar de una sola cadena dep a través de una barajadura de cruce de carril (latencia de 3 ciclos). Eso aumentará ILP dentro de un solo tipo. 2 dep chain limita el número de constantes vectoriales a un número razonable, solo 2: 1 para una rotación y uno para 2 pasos de rotación combinados.
Peter Cordes
2

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 pequeños arreglos. Pensé que sería una buena idea compartir mis conocimientos. Si bien comencé a usar 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 fue menor que con las redes de clasificación, y menor que con la clasificación de inserción. No conté el número de permutas; Esperaría que sea más o menos equivalente (tal vez un poco más alto a veces).

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

Ordenar 3 valores

El siguiente algoritmo es un tipo de inserción desenrollado. Cuando se tienen que realizar dos swaps (6 asignaciones), en su lugar utiliza 4 asignaciones:

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 el orden tiene más o menos una rama para cada permutación posible de la matriz, usando 2 ~ 3 comparaciones y como máximo 4 asignaciones para ordenar los tres valores.

Ordenar 4 valores

Éste llama sort3luego realiza una ordenación 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 intercambios. Es fácil desenrollar un tipo de inserción, pero usaremos otro algoritmo para el último tipo ...

Ordenar 6 valores

Este usa una versión desenrollada de lo que llamé un tipo de inserción doble . El nombre no es tan bueno, pero es bastante descriptivo, así es como funciona:

  • Ordena todo menos el primer y el último elemento de la matriz.
  • Cambie el primero y los elementos de la matriz si el primero es mayor que el último.
  • 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 último, 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 ha sido insertado en la 3ra posición, luego el último no se puede insertar más abajo que la 4ta 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 este algoritmo siempre realiza entre 6 y 13 comparaciones. No calculé el número de intercambios 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 ponerlo 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 tipo de inserción desenrollada, pero eso es todo. Básicamente, no es el mejor tipo para enteros, pero podría ser interesante para tipos con una operación de comparación costosa.

revs Morwenn
fuente
Estos son buenos Como el problema resuelto tiene muchas décadas de antigüedad, probablemente tan antiguo como una programación en C, que la pregunta ahora tiene casi 5 años no parece tan relevante.
kriss
Debes echar un vistazo a la forma en que las otras respuestas están cronometradas. El punto es que con comparaciones de recuento de conjuntos de datos tan pequeños o incluso comparaciones e intercambios realmente no dice qué tan rápido es un algoritmo (básicamente, ordenar 6 ints es siempre O (1) porque O (6 * 6) es O (1)). La solución actual más rápida de las propuestas anteriormente es encontrar inmediatamente la posición de cada valor utilizando una gran comparación (por RexKerr).
kriss
@kriss ¿Es el más rápido ahora? Desde mi lectura de los resultados, el enfoque de redes de clasificación fue el más rápido, mi malo. También es cierto que mi solución proviene de mi biblioteca genérica y que no siempre comparo enteros, ni siempre uso operator<para la comparación. Además del recuento objetivo de comparaciones e intercambios, también cronometré adecuadamente mis algoritmos; esta solución fue la genérica más rápida, pero de hecho me perdí la de @ RexKerr. Voy a probarlo :)
Morwenn
La solución de RexKerr (Order Rank) se convirtió en la más rápida en la arquitectura X86 desde el compilador gcc 4.2.3 (y a partir de gcc 4.9 se volvió casi dos veces más rápido que el segundo mejor). Pero depende en gran medida de las optimizaciones del compilador y puede no ser cierto en otras arquitecturas.
kriss
@kriss Es interesante saberlo. Y de hecho podría tener más diferencias con -O3. Supongo que adoptaré otra estrategia para mi biblioteca de clasificación: proporcionar tres tipos de algoritmos para tener un número bajo de comparaciones, un número bajo de intercambios o potencialmente el mejor rendimiento. Al menos, lo que pase será transparente para el lector. Gracias por sus ideas :)
Morwenn
1

Creo que su pregunta tiene dos partes.

  • El primero es determinar el algoritmo óptimo. Esto se hace, al menos en este caso, recorriendo cada pedido posible (no hay tantos) que le permite calcular la desviación mínima, máxima, promedio y estándar exacta de las comparaciones y los intercambios. Tenga un segundo puesto o dos a mano también.
  • El segundo es optimizar el algoritmo. Se puede hacer mucho para convertir ejemplos de código de libros de texto en algoritmos reales y leves. Si se da cuenta de que un algoritmo no se puede optimizar en la medida requerida, intente un segundo puesto.

No me preocuparía demasiado por vaciar las tuberías (suponiendo x86 actual): la predicción de rama ha recorrido un largo camino. Lo que me preocupa es asegurarme de que el código y los datos quepan en una línea de caché cada uno (tal vez dos para el código). Una vez allí, las latencias de recuperación son refrescantemente bajas, lo que compensará cualquier pérdida. También significa que su bucle interno tendrá unas diez instrucciones o menos, 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 de largo respectivamente). Suponiendo que el código no contiene ningún divs, puede estar seguro de que será cegadoramente rápido.

Olof Forshell
fuente
No estoy seguro de cómo entender tu respuesta. Primero, no entiendo en absoluto qué algoritmo está proponiendo. Y cómo podría ser óptimo si tiene que recorrer 720 posibles ordenaciones (las respuestas existentes requieren mucho menos de 720 ciclos). Si tiene una entrada aleatoria, no puedo imaginar (incluso a nivel teórico) cómo la predicción de ramificación podría funcionar mejor que 50-50, excepto si no le importan los datos de entrada. También es probable que la mayoría de las buenas soluciones ya propuestas funcionen con datos y código completamente en caché. Pero tal vez no entendí completamente tu respuesta. ¿Te importaría mostrar algún código?
kriss
Lo que quise decir es que solo hay 720 (6!) Combinaciones diferentes de 6 enteros y, al ejecutarlas todas a través de los algoritmos candidatos, puede determinar muchas cosas como mencioné, esa es la parte teórica. La parte práctica es ajustar ese algoritmo para que se ejecute en la menor cantidad de ciclos de reloj posible. Mi punto de partida para ordenar 6 enteros es un shellsort de 1, 4 gap. La brecha de 4 allana el camino para una buena predicción de rama en la brecha de 1.
Olof Forshell
El 1, 4 brecha shellsort para 6! combinaciones únicas (comenzando con 012345 y terminando con 543210) tendrán un mejor caso de 7 comparaciones y 0 intercambios y el peor de 14 comparaciones y 10 intercambios. El caso promedio es de aproximadamente 11.14 comparaciones y 6 intercambios.
Olof Forshell
1
No obtengo la "distribución aleatoria regular": lo que estoy haciendo es probar todas las combinaciones posibles y determinar las estadísticas mínimas / medias / máximas. Shellsort es una serie de tipos de inserción de incrementos decrecientes, de modo que el incremento final - 1 - hace mucho menos trabajo que si se realiza solo como en un tipo de inserción pura. En cuanto al recuento de reloj, mi algoritmo requiere un promedio de 406 ciclos de reloj y esto incluye recopilar estadísticas y hacer dos llamadas a la rutina de clasificación real, una para cada espacio. Esto está en un compilador móvil Athlon M300, OpenWatcom.
Olof Forshell
1
"distribución aleatoria regular" significa que todas las combinaciones de datos reales que se ordenan pueden no tener la misma probabilidad. Si todas las combinaciones no tienen la misma probabilidad, sus estadísticas se rompen porque el promedio debe tener en cuenta cuántas veces es probable que ocurra una distribución dada. Para el recuento de reloj, si prueba cualquier otra implementación de este tipo (enlaces proporcionados anteriormente) y la ejecuta en su sistema de prueba, tendremos una base para la comparación y veremos qué tan bien se desempeña el elegido.
kriss
1

Sé que esta es una vieja pregunta.

Pero acabo de escribir un tipo diferente de solución que quiero compartir.
Usando nada más que MIN MAX anidado,

No es rápido, ya que usa 114 de cada uno,
podría reducirlo a 75 bastante simplemente así -> 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 clasificación inspirada en Rex Kerr, mucho más rápido que el desastre anterior

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;
}
PrincePolka
fuente
1
Siempre es agradable ver nuevas soluciones. Parece que es posible una optimización fácil. Al final, puede que no resulte tan diferente de Sorting Networks.
kriss
Sí, el número de MIN y MAX podría reducirse, por ejemplo, MIN (AB, CD) se repite varias veces, pero creo que reducirlos será difícil. Agregué tus casos de prueba.
PrincePolka
pmin / maxsw funcionan en enteros con signo de 16 bits empaquetados ( int16_t). Pero su función C afirma que ordena una matriz de int(que es de 32 bits en todas las implementaciones de C que admiten esa asmsintaxis). ¿Lo probó solo con pequeños enteros positivos que solo tienen 0 en sus mitades altas? Eso funcionará ... Para intque necesite SSE4.1 pmin/maxsd(d = dword). felixcloutier.com/x86/pminsd:pminsq o pminusdpara uint32_t.
Peter Cordes
1

Descubrí que al menos en mi sistema, las funciones sort6_iterator()y las sort6_iterator_local()definidas a continuación se ejecutan al menos tan rápido, y con frecuencia notablemente más rápido, que el poseedor del récord 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 de un std::vectoriterador en mi código de tiempo.

Sospecho (por comentarios como este y en otros lugares) que el uso de iteradores le da a g ++ ciertas garantías sobre lo que puede y no puede sucederle a la memoria a la que se refiere el iterador, que de lo contrario no tendría y son estas garantías las que permiten a g ++ optimice mejor el código de clasificación (por ejemplo, con punteros, el compilador no puede estar seguro de que todos los punteros apuntan a diferentes ubicaciones de memoria). Si recuerdo correctamente, esto también es parte de la razón por la cual tantos algoritmos STL, como std::sort(), generalmente tienen un rendimiento tan obsceno.

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, que copia los datos en variables locales antes de la clasificación ellos. 1 Tenga en cuenta que dado que solo hay 6 variables locales definidas, si estas variables locales son primitivas, es probable que nunca se almacenen en la RAM y que solo se almacenen en los registros de la CPU hasta el final de la llamada a la función, lo que ayuda a hacer esta clasificación Funcionan rápido. (También ayuda que el compilador sepa que distintas variables locales tienen ubicaciones distintas en la memoria).

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 la SWAP()siguiente manera algunas veces resulta en 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 ordenación que en los tipos de datos primitivos, gcc -O3 sea consistentemente bueno para la optimización, sin importar en qué contexto aparezca la llamada a la función de ordenación en 1 , luego, dependiendo de cómo pase la entrada, intente uno de los dos siguientes 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
}

O si desea pasar las variables por referencia, use esto (la función a continuación difiere de la anterior en sus primeras 5 líneas):

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 register, el compilador resolverá esto la mayor parte del tiempo, pero a veces no lo hace. El uso de la registerpalabra clave ayuda a resolver este problema. Sin embargo, normalmente no use la registerpalabra clave ya que es más probable que ralentice su 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 están mucho más agresivamente optimizadas por gcc que las funciones vanilla C (esto tiene que ver con gcc que necesita tratar con punteros de función para funciones vanilla C pero no con funciones de plantilla).

  1. Mientras cronometraba varias funciones de clasificación, noté 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 deba a que la función está en línea y luego optimizada. Por ejemplo, si el programa era lo suficientemente simple, generalmente no había mucha diferencia en el rendimiento entre pasar la función de clasificación a un puntero versus pasarle un iterador; de lo contrario, el uso de iteradores generalmente resultó en un rendimiento notablemente mejor y nunca (en mi experiencia hasta ahora al menos) un rendimiento notablemente peor. Sospecho que esto puede deberse a que g ++ puede optimizar globalmente un código suficientemente simple.
Matthew K.
fuente
0

Intente "fusionar la lista ordenada". :) Use dos arreglos. Más rápido para pequeñas y grandes series.
Si concatena, solo verifica dónde se inserta. Otros valores más grandes que no necesita comparar (cmp = ab> 0).
Para 4 números, puede usar el sistema 4-5 cmp (~ 4.6) o 3-6 cmp (~ 4.9). El tipo de burbuja utiliza 6 cmp (6). Un montón de cmp para grandes números de código más lento.
Este código usa 5 cmp (no ordena 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);}

Principial MSL 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

function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}

Peter
fuente
0

Ordenar 4 elementos con uso cmp == 0. Los números de cmp son ~ 4.34 (los nativos de FF tienen ~ 4.52), pero tardan 3 veces más que fusionar listas. Pero mejor menos operaciones cmp, si tiene números grandes o texto grande. Editar: error reparado

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

function sort4DG(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
    {
    swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
    cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
    if (cc[13]>0)
        {
        swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
        return n;
        }
    else    {
    cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3]));  // new cc23 | c03 //repaired
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    }
else    {
    if (cc[12]>0)
        {
        swap(n,i+1,i+2);
        cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    else    {
        return n;
        }
    }
return n;
}
peter
fuente
1
El caso de uso es ligeramente diferente del contexto inicial de la pregunta. Con los tipos de longitud fijos, los detalles importan y contar cmp de swaps no es suficiente. Ni siquiera me sorprendería si no fuera el tipo real lo que consumiría tiempo, sino algo completamente diferente llamando a typeof () en el init. No sé cómo realizar la medición de la hora real del reloj usando Javascript. Tal vez con nodo?
kriss
0

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

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

Actualización: cambió un poco el código, algunas personas usan compiladores C ++ para compilar 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);
}
wildplasser
fuente
parece una especie de burbuja. Potencialmente, es un buen candidato para la implementación más lenta, pero aún puede ser interesante saber si trabajar en el código hace una gran diferencia. Pon tu código en el mismo formato que otros, para que podamos ejecutar el punto de referencia en él.
kriss
@kriss en.wikipedia.org/wiki/Permutation_group Ciertamente no es un tipo de burbuja: el código detecta ciclos en la permutación dada y los recorre, colocando cada elemento en su lugar final. La wsort6()función final tiene la interfaz correcta.
joop
@joop: mi mal, no hay burbuja de hecho. Dicho esto en el contexto, todavía espero que el código sea mucho peor que cualquier otra implementación actual. Por cierto, la solución de Orden de clasificación es óptima con respecto al número de intercambios, ya que encuentra directamente la posición final de cada elemento. Tampoco está claro si walkort incluso funciona cuando eliminamos la hipótesis de que todos los números ordenados son diferentes como aquí. Para comparar el código, deberíamos rastrear el código. Además, como generalmente estoy compilando en un compilador de C ++, el código no funcionará porque el OP llamó a una variable "nueva" (y eso rompe el resaltado de sintaxis).
kriss
El método está muy cerca del orden de clasificación, solo las tareas finales se realizan en su lugar . Aparte de los rangos o1..o5, no hay necesidad de la segunda e[6]matriz temporal . Y: ¿compilar código C en un compilador de C ++ y culpar al código?
joop
@greybeard: gracias, agregué un espacio antes #include. Solucionado
wildplasser
0
//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
    int t[6] = {0};
    int r1,r2;

    r1=0;
    r1 += (a[0] > a[1]);
    r1 += (a[0] > a[2]);
    r1 += (a[0] > a[3]);
    r1 += (a[0] > a[4]);
    r1 += (a[0] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[0];

    r2=0;
    r2 += (a[1] > a[0]);
    r2 += (a[1] > a[2]);
    r2 += (a[1] > a[3]);
    r2 += (a[1] > a[4]);
    r2 += (a[1] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[1];

    r1=0;
    r1 += (a[2] > a[0]);
    r1 += (a[2] > a[1]);
    r1 += (a[2] > a[3]);
    r1 += (a[2] > a[4]);
    r1 += (a[2] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[2];

    r2=0;
    r2 += (a[3] > a[0]);
    r2 += (a[3] > a[1]);
    r2 += (a[3] > a[2]);
    r2 += (a[3] > a[4]);
    r2 += (a[3] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[3];

    r1=0;
    r1 += (a[4] > a[0]);
    r1 += (a[4] > a[1]);
    r1 += (a[4] > a[2]);
    r1 += (a[4] > a[3]);
    r1 += (a[4] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[4];

    r2=0;
    r2 += (a[5] > a[0]);
    r2 += (a[5] > a[1]);
    r2 += (a[5] > a[2]);
    r2 += (a[5] > a[3]);
    r2 += (a[5] > a[4]);
    while(t[r2]){r2++;} 
    t[r2] = a[5];

    a[0]=t[0];
    a[1]=t[1];
    a[2]=t[2];
    a[3]=t[3];
    a[4]=t[4];
    a[5]=t[5];
}

static __inline__ void sort6(int* a)
{
    #define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
    register int t;

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

    #undef wire
}
revs FrantzelasG
fuente
Independientemente de la velocidad, ¿estás seguro de que funciona? En bruteforce sort tus bucles son dudosos. Me parece que no funcionarán si tenemos un cero en los valores ordenados.
kriss
1
La matriz t [6] se inicializa a 0x0. Por lo tanto, no importa dónde y si se escribirá una clave con valor 0x0.
FranG
-1

Bueno, si son solo 6 elementos y puede aprovechar el paralelismo, quiere minimizar la ramificació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)

GClaramunt
fuente
99
Hay 720 pedidos, y las versiones rápidas tienen menos de 100 ciclos. Incluso si el paralelismo masivo pudiera ser apalancado, en una escala de tiempo tan pequeña, el costo de crear y sincronizar los subprocesos probablemente excedería el costo de simplemente ordenar los arreglos en un núcleo.
Kevin Stock
-3

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 mira 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. ¿Clasificación en tiempo lineal? En Actas del 27º Simposio anual de ACM sobre la teoría de la informática, páginas 427-436, 1995.

Khaled A Khunaifer
fuente
8
Esto es interesante pero no viene al caso. Big-Θ está destinado a ocultar factores constantes y mostrar la tendencia cuando el tamaño del problema (n) aumenta. El problema aquí es completamente sobre un tamaño de problema fijo (n = 6) y teniendo en cuenta factores constantes.
kriss
@kriss tienes razón, mi comparación es asintótica, por lo que la comparación práctica mostrará si es más rápido o no para ese caso
Khaled.K
44
No puede concluir, porque cada algoritmo diferente esconde una constante multiplicativa K diferente (y también una constante aditiva C). es decir: k0, c0 para la ordenación por inserción, k1, c1 para la ordenación del montón y así sucesivamente. Todas esas constantes son realmente diferentes (se podría decir en términos físicos que cada algoritmo tiene su propio "coeficiente de fricción"). No se puede concluir que un algoritmo sea realmente más rápido en este caso (o en cualquier caso n fijo).
kriss