Golfizado + clasificación rápida en C

11

[ Última actualización: programa de referencia y resultados preliminares disponibles, ver más abajo]

Por lo tanto, quiero probar la compensación de velocidad / complejidad con una aplicación clásica: la clasificación.

Escriba una función ANSI C que clasifique una matriz de números de coma flotante en orden creciente .

No se puede utilizar cualquier bibliotecas, llamadas al sistema, multithreading o ASM en línea.

Entradas juzgadas en dos componentes: longitud del código y rendimiento. Puntuación de la siguiente manera: las entradas se ordenarán por longitud (registro de # caracteres sin espacios en blanco, para que pueda mantener algo de formato) y por rendimiento (registro de # segundos sobre un punto de referencia), y cada intervalo [mejor, peor] se normaliza linealmente a [ 0,1]. El puntaje total de un programa será el promedio de los dos puntajes normalizados. La puntuación más baja gana. Una entrada por usuario.

La clasificación tendrá que (eventualmente) estar en su lugar (es decir, la matriz de entrada tendrá que contener los valores ordenados en el momento de la devolución), y debe usar la siguiente firma, incluidos los nombres:

void sort(float* v, int n) {

}

Caracteres a contar: aquellos en la sortfunción, firma incluida, más funciones adicionales llamadas por él (pero sin incluir el código de prueba).

El programa debe manejar cualquier valor numérico floaty matrices de longitud> = 0, hasta 2 ^ 20.

Conectaré sorty sus dependencias en un programa de prueba y compilaré en GCC (sin opciones sofisticadas). Alimentaré un montón de matrices en él, verificaré la exactitud de los resultados y el tiempo total de ejecución. Las pruebas se ejecutarán en un Intel Core i7 740QM (Clarksfield) en Ubuntu 13. Las
longitudes de matriz abarcarán todo el rango permitido, con una mayor densidad de matrices cortas. Los valores serán aleatorios, con una distribución de cola gorda (tanto en el rango positivo como en el negativo). Los elementos duplicados se incluirán en algunas pruebas.
El programa de prueba está disponible aquí: https://gist.github.com/anonymous/82386fa028f6534af263
Importa el envío como user.c. El número de casos de prueba ( TEST_COUNT) en el punto de referencia real será 3000. Proporcione cualquier comentario en los comentarios de las preguntas.

Plazo: 3 semanas (7 de abril de 2014, 16:00 GMT). Publicaré el punto de referencia en 2 semanas.
Puede ser aconsejable publicar cerca de la fecha límite para evitar regalar su código a los competidores.

Resultados preliminares, a partir de la publicación de referencia:
Estos son algunos resultados. La última columna muestra el puntaje como un porcentaje, cuanto más alto mejor, colocando a Johnny Cage en primer lugar. Los algoritmos que eran de órdenes de magnitud más lentos que el resto se ejecutaron en un subconjunto de pruebas y se extrapolaron en el tiempo. El propio C qsortestá incluido para comparación (¡Johnny's es más rápido!). Realizaré una comparación final a la hora de cierre.

ingrese la descripción de la imagen aquí

Mau
fuente
3
¿Puedes proporcionar el punto de referencia? Las diferentes funciones de clasificación funcionan de manera diferente según la naturaleza de los datos. Por ejemplo, el ordenamiento de burbujas es más rápido que el stdlib quicksort para arreglos pequeños. Nos gustaría optimizar para su punto de referencia.
Claudiu
@Claudiu Una vez vi una hermosa versión corta de quicksort, que funcionaba tan bien como cualquier otra en datos donde cada elemento era diferente. Pero si algunos elementos eran iguales, funcionaba a un ritmo absoluto de caracol. No estoy hablando del problema conocido de la mala elección de pivote en arreglos ordenados / parcialmente ordenados. Los datos de mi prueba se barajaron completamente al azar. A esta versión en particular simplemente no le gustaban los duplicados. Extraño pero cierto.
Level River St
3
Bienvenido a PPCG! Si bien no prohibimos los desafíos específicos del idioma, sí recomendamos encarecidamente formular preguntas de manera independiente del idioma siempre que sea posible. ¡Considérelo para su próxima pregunta y diviértase con esta!
Jonathan Van Matre
1
@steveverrill: no te sigo. No importa cuál sea su unidad porque la escala de 0 a 1 de todos modos. Si min es de 1 hora y max es de 3 horas, algo que tome 1.5 horas será de 0.25 independientemente de si min es de 60 minutos, max es de 180 minutos y toma 90 minutos
Claudiu
1
OP solo dijo que no había montaje en línea: no dijo nada sobre intrínsecos.
Paul R

Respuestas:

6

150 caracteres

Ordenación rápida.

/* 146 character.
 * sizeup 1.000; speedup 1.000; */
#define REC_SIZE    \
    sort(l, v+n-l); \
    n = l-v;

/* 150 character.
 * sizeup 1.027; speedup 1.038; */
#define REC_FAST  \
    sort(v, l-v); \
    n = v+n-l;    \
    v = l;

void sort(float* v, int n)
{
    while ( n > 1 )
     {
       float* l = v-1, * r = v+n, x = v[n/2], t;
L:
       while ( *++l < x );
       while ( x < (t = *--r) );

       if (l < r)
        {
          *r = *l; *l = t;
          goto L;
        }
       REC_FAST
     }
}

Comprimido.

void sort(float* v, int n) {
while(n>1){float*l=v-1,*r=v+n,x=v[n/2],t;L:while(*++l<x);while(x<(t=*--r));if(l<r){*r=*l;*l=t;goto L;}sort(v,l-v);n=v+n-l;v=l;}
}
Johnny Cage
fuente
¡Liderando la carrera!
Mau
3

150 caracteres (sin espacios en blanco)

void sort(float *v, int n) {
    int l=0;
    float t, *w=v, *z=v+(n-1)/2;

    if (n>0) {
      t=*v; *v=*z; *z=t;
      for(;++w<v+n;)
        if(*w<*v)
        {
          t=v[++l]; v[l]=*w; *w=t;
        }
      t=*v; *v=v[l]; v[l]=t;
      sort(v, l++);
      sort(v+l, n-l);
    }
}
Michael M.
fuente
Impresionante, primera entrada!
Mau
Siéntase libre de publicar una respuesta con SSE y la enumeraré en el marcador, aunque estoy interesado en soluciones 'portátiles' para el desafío.
Mau
if(*w<*v) { t=v[++l]; v[l]=*w; *w=t; }puede serif(*w<*v) t=v[++l], v[l]=*w, *w=t;
ASKASK
3

67 70 69 caracteres

No es nada rápido, pero increíblemente pequeño. Supongo que es un híbrido entre un algoritmo de selección y de clasificación de burbujas. Si realmente está intentando leer esto, entonces debe saber que ++i-v-nes lo mismo que ++i != v+n.

void sort(float*v,int n){
    while(n--){
        float*i=v-1,t;
        while(++i-v-n)
            *i>v[n]?t=*i,*i=v[n],v[n]=t:0;
    }
}
PREGUNTA PREGUNTA
fuente
if(a)b-> a?b:0guarda un personaje.
Ugoren
Bueno, ++i-v-nes lo mismo que ++i != v+nsolo en un condicional, por supuesto.
wchargin
@ugoren, creo que publicaste ese comentario sobre la respuesta incorrecta
ASKASK
@ASKASK, if(*i>v[n])...->*i>v[n]?...:0
ugoren
¿estás seguro de que es así como funciona la presencia?
ASKASK
2

123 caracteres (+3 líneas nuevas)

Un tipo estándar de Shell, comprimido.

d,i,j;float t;
void sort(float*v,int n){
for(d=1<<20;i=d/=2;)for(;i<n;v[j]=t)for(t=v[j=i++];j>=d&&v[j-d]>t;j-=d)v[j]=v[j-d];
}  

PD: descubrí que todavía es 10 veces más lento que Quicksort. También podría ignorar esta entrada.

Florian F
fuente
Su elección de brechas podría ser mejor. Esa es probablemente la razón por la cual esto es mucho más lento que la clasificación rápida. en.wikipedia.org/wiki/Shellsort#Gap_sequences
FDinoff
Me sorprendió descubrir cuánto afecta la secuencia de la brecha a la velocidad. Con una buena secuencia, se acerca a la clasificación rápida, pero en mi experiencia sigue siendo más lenta.
Florian F
No seas demasiado duro contigo mismo. Estás en tercer lugar.
Kevin
2

395 caracteres

Mergesort.

void sort(float* v,int n){static float t[16384];float*l,*r,*p,*q,*a=v,*b=v+n/2,
*c=v+n,x;if(n>1){sort(v,n/2);sort(v+n/2,n-n/2);while(a!=b&&b!=c)if(b-a<=c-b&&b-
a<=16384){for(p=t,q=a;q!=b;)*p++=*q++;for(p=t,q=t+(b-a);p!=q&&b!=c;)*a++=(*p<=
*b)?*p++:*b++;while(p!=q)*a++=*p++;}else{for(l=a,r=b,p=t,q=t+16384;l!=b&&r!=c&&
p!=q;)*p++=(*l<=*r)?*l++:*r++;for(q=b,b=r;l!=q;)*--r=*--q;for(q=t;p!=q;)*a++=
*q++;}}}

Formateado

static float* copy(const float* a, const float* b, float* out)
{   while ( a != b ) *out++ = *a++; return out;
}
static float* copy_backward(const float* a, const float* b, float* out)
{   while ( a != b ) *--out = *--b; return out;
}

static void ip_merge(float* a, float* b, float* c)
{
    /* 64K (the more memory, the better this performs). */
#define BSIZE (1024*64/sizeof(float))
    static float t[BSIZE];

    while ( a != b && b != c )
     {
       int n1 = b - a;
       int n2 = c - b;

       if (n1 <= n2 && n1 <= BSIZE)
        {
          float* p = t, * q = t + n1;
          /* copy [a,b] sequence. */
          copy(a, b, t);
          /* merge. */
          while ( p != q && b != c )
             *a++ = (*p <= *b) ? *p++ : *b++;
          /* copy remaining. */
          a = copy(p, q, a);
        }
       /* backward merge omitted. */
       else
        {
          /* there are slicker ways to do this; all require more support
           * code. */
          float* l = a, * r = b, * p = t, * q = t + BSIZE;
          /* merge until sequence end or buffer end is reached. */
          while ( l != b  && r != c && p != q )
             *p++ = (*l <= *r) ? *l++ : *r++;
          /* compact remaining. */
          copy_backward(l, b, r);
          /* copy buffer. */
          a = copy(t, p, a);
          b = r;
        }
     }
}

void sort(float* v, int n)
{
    if (n > 1)
     {
       int h = n/2;
       sort(v, h); sort(v+h, n-h); ip_merge(v, v+h, v+n);
     }
}
Knucklesandwich
fuente
2

331 326 327 312 caracteres

¿La raíz clasifica 8 bits a la vez? Utiliza un bithack elegante para que los flotadores negativos se ordenen correctamente (robado de http://stereopsis.com/radix.html ). No es tan compacto, pero es realmente rápido (~ 8 veces más rápido que la entrada preliminar más rápida). Espero el tamaño del código de velocidad de triunfo ...

#define I for(i=n-1;i>=0;i--)
#define J for(i=0;i<256;i++)
#define R for(r=0;r<4;r++)
#define F(p,q,k) I p[--c[k][q[i]>>8*k&255]]=q[i]

void sort(float *a, int n) {
  int *A = a,i,r,x,c[4][257],B[1<<20];
  R J c[r][i]=0;
  I {
    x=A[i]^=A[i]>>31|1<<31;
    R c[r][x>>8*r&255]++;
  }
  J R c[r][i+1]+=c[r][i];

  F(B,A,0);
  F(A,B,1);
  F(B,A,2);
  F(A,B,3)^(~B[i]>>31|1<<31);
}
Keith Randall
fuente
2

511 424 caracteres

Radixsort en el lugar

Actualización: Cambia al orden de inserción para tamaños de matriz más pequeños (aumenta el rendimiento de referencia en un factor de 4.0).

#define H p[(x^(x>>31|1<<31))>>s&255]
#define L(m) for(i=0;i<m;i++)
void R(int*a,int n,int s){if(n<64){float*i,*j,x;for(i=a+1;i<a+n;i++){x=*i;for(
j=i;a<j&&x<j[-1];j--)*j=j[-1];*j=x;}}else{int p[513]={},*q=p+257,z=255,i,j,x,t
;L(n)x=a[i],H++;L(256)p[i+1]+=q[i]=p[i];for(z=255;(i=p[z]-1)>=0;){x=a[i];while
((j=--H)!=i)t=x,x=a[j],a[j]=t;a[i]=x;while(q[z-1]==p[z])z--;}if(s)L(256)R(a+p[
i],q[i]-p[i],s-8);}}void sort(float* v,int n){R(v,n,24);}

Formateado

/* XXX, BITS is a power of two. */
#define BITS 8
#define BINS (1U << BITS)
#define TINY 64

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

static inline unsigned int floatbit_to_sortable_(const unsigned int x)
{   return x ^ ((0 - (x >> 31)) | 0x80000000);
}

static inline unsigned int sortable_to_floatbit_(const unsigned int x)
{   return x ^ (((x >> 31) - 1) | 0x80000000);
}

static void insertsort_(unsigned int* a, unsigned int* last)
{
    unsigned int* i;
    for ( i = a+1; i < last; i++ )
     {
       unsigned int* j, x = *i;
       for ( j = i; a < j && x < *(j-1); j-- )
          *j = *(j-1);
       *j = x;
     }
}

static void radixsort_lower_(unsigned int* a, const unsigned int size,
  const unsigned int shift)
{
    /* @note setup cost can be prohibitive for smaller arrays, switch to
     * something that performs better in these cases. */
    if (size < TINY)
     {
       insertsort_(a, a+size);
       return;
     }

    unsigned int h0[BINS*2+1] = {}, * h1 = h0+BINS+1;
    unsigned int i, next;

    /* generate histogram. */
    for ( i = 0; i < size; i++ )
       h0[(a[i] >> shift) % BINS]++;

    /* unsigned distribution.
     * @note h0[BINS] == h1[-1] == @p size; sentinal for bin advance. */
    for ( i = 0; i < BINS; i++ )
       h0[i+1] += (h1[i] = h0[i]);

    next = BINS-1;
    while ( (i = h0[next]-1) != (unsigned int) -1 )
     {
       unsigned int x = a[i];
       unsigned int j;
       while ( (j = --h0[(x >> shift) % BINS]) != i )
          SWAP(unsigned int, x, a[j]);
       a[i] = x;
       /* advance bins.
        * @note skip full bins (zero sized bins are full by default). */
       while ( h1[(int) next-1] == h0[next] )
          next--;
     }

    /* @note bins are sorted relative to one another at this point but
     * are not sorted internally. recurse on each bin using successive
     * radii as ordering criteria. */
    if (shift != 0)
       for ( i = 0; i < BINS; i++ )
          radixsort_lower_(a + h0[i], h1[i] - h0[i], shift-BITS);
}

void sort(float* v, int n)
{
    unsigned int* a = (unsigned int*) v;
    int i;

    for ( i = 0; i < n; i++ )
       a[i] = floatbit_to_sortable_(a[i]);

    radixsort_lower_(a, n, sizeof(int)*8-BITS);

    for ( i = 0; i < n; i++ )
       a[i] = sortable_to_floatbit_(a[i]);
}
MojoJojoBojoHojo
fuente
¡Agradable! Intenta marcar la respuesta original.
Mau
@Mau: Gracias y lo haremos. Quería mencionar un error en el código de evaluación comparativa. El yeso void*en qsort(línea 88) está arrojando la aritmética del puntero.
MojoJojoBojoHojo
1

121 114 111 caracteres

Solo una burbuja rápida y sucia, con recursión. Probablemente no muy eficiente.

void sort(float*v,int n){int i=1;float t;for(;i<n;i++)v[i-1]>(t=v[i])&&(v[i]=v[i-1],v[i-1]=t);n--?sort(v,n):0;}

O la versión larga

void sort(float* values, int n) {
  int i=1;  // Start at 1, because we check v[i] vs v[i-1]
  float temp;
  for(; i < n; i++) {
    // If v[i-1] > v[i] is true (!= 0), then swap.
    // Note I am assigning values[i] to temp here. Below I want to use commas
    // so the whole thing fits into one statement, but if you assign temp there you will get sequencing issues (i.e unpredictable swap results)
    values[i - 1] > (temp = values[i]) && (
    // I tried the x=x+y,y=x-y,x=x-y trick, but using a temp
    // turns out to be shorter even if we have to declare the t variable.
      values[i] = values[i - 1], 
      values[i - 1] = temp);
  }

  // If n == 1, we are done. Otherwise, sort the first n - 1 elements recursively. 
  // The 0 is just because the third statement cannot be empty.
  n-- ? sort(values, n) : 0;
}
CompuChip
fuente
Además, encontré un algoritmo realmente interesante aquí: rosettacode.org/wiki/Sorting_algorithms/Pancake_sort#C Pero no puedo comprimirlo lo suficiente como para vencer a 114 :)
CompuChip
su programa parece no completar en algunos casos y escribir fuera de los límites en otros casos.
Mau
@Mau Lo probé manualmente en algunas entradas y parecía funcionar bien, pero debido a la falta de tiempo no lo probé muy a fondo, así que estoy seguro de que hay algún mal comportamiento en alguna parte. ¿Podría publicar un caso de prueba en el que haya tenido problemas, por favor?
CompuChip
programa de prueba disponible arriba :)
Mau
Hmm, intenté ejecutarlo, obtengo algunos errores `munmap_chunk (): puntero inválido` en la parte de limpieza, pero nada sobre la falla de la prueba. Sin embargo, tiene razón en que hay un error fuera de uno, y parece que tengo algunos problemas de secuencia (la lista de declaraciones separadas por comas no hace lo que espero). Intentaré arreglarlo.
CompuChip
1

221 193 172 caracteres

Heapsort: no es el más pequeño, pero está en su lugar y garantiza el comportamiento O (n * log (n)).

static void sink(float* a, int i, int n, float t)
{
    float* b = a+i;

    for ( ; (i = i*2+2) <= n; b = a+i )
     {
       i -= (i == n || a[i] < a[i-1]) ? 1 : 0;

       if (t < a[i])
          *b = a[i];
       else
          break;
     }
    *b = t;
}

void sort(float* a, int n)
{
    int i;
    /* make. */
    for ( i = n/2-1; i >= 0; i-- )
       sink(a, i, n, a[i]);
    /* sort. */
    for ( i = n-1; i > 0; i-- )
     {
       float t = a[i]; a[i] = a[0];
       sink(a, 0, i, t);
     }
}

Comprimido.

void sort(float* a,int n){
#define F(p,q,r,x,y) for(i=n/p;q>0;){t=a[i];r;for(j=x;(b=a+j,j=j*2+2)<=y&&(j-=(j==y||a[j]<a[j-1]),t<a[j]);*b=a[j]);*b=t;}
float*b,t;int i,j;F(2,i--,,i,n)F(1,--i,a[i]=*a,0,i)
}
usuario19425
fuente
Puede guardar algunos caracteres deduciendo el espacio en blanco. Y posiblemente también la firma de la función obligatoria, pero dado que hay algunas entradas que cuentan que le he pedido al interlocutor que aclare si debe contarse.
Jonathan Van Matre
@ user19425: Si ejecuta el programa de prueba con TEST_COUNT= 3000, parece fallar al menos una prueba.
Mau
1

154 166 caracteres

OK, aquí hay un resumen rápido más largo pero más rápido.

void sort(float*v,int n){while(n>1){float*j=v,*k=v+n-1,t=*j;while(j<k){while(j<k&&*k>=t)k--;*j=*k;while(j<k&&*j<t)j++;*k=*j;}*k++=t;sort(k,v+n-k);n=j-v;}}

Aquí hay una corrección para sobrevivir a las entradas ordenadas. Y formateado ya que el espacio en blanco no cuenta.

void sort(float*v, int n){
    while(n>1){
        float*j=v, *k=j+n/2, t=*k;
        *k = *j;
        k = v+n-1;
        while(j<k){
            while(j<k && *k>=t) k--;
            *j=*k;
            while(j<k && *j<t) j++;
            *k=*j;
        }
        *k++ = t;
        sort(k,v+n-k);
        n = j-v;
    }
}
Florian F
fuente
Esta versión parece estar fuera de los límites en algunos casos, no termina en otros.
Mau
PD: OK, es muy lento en un conjunto ordenado. Pero el enunciado del problema dice que la entrada es aleatoria.
Florian F
Los valores son al azar. Nunca dije nada sobre en qué orden estarían :-) Pero sí, hay fragmentos que cubren aproximadamente el 10% de todos los valores ordenados en orden ascendente y otro 10% en orden descendente.
Mau
1
Lo suficientemente justo. Y un sort () debería funcionar en la entrada ordenada. Actualizaré mi presentación, entonces ...
Florian F
1

150 caracteres

Shellsort (w / Knuth gap).

void sort(float* v, int n) {
float*p,x;int i,h=0;while(2*(i=h*3+1)<=n)h=i;for(;h>0;h/=3)for(i=h;i<n;i++){x=v[i];for(p=v+i-h;p>=v&&x<*p;p-=h)p[h]=*p;p[h]=x;}
}

Formateado

static void hsort(float* v, const int h, const int n)
{
    int i;
    for (i = h; i < n; i++) {
        float* p, x = v[i];
        for (p = v + i-h; p >= v && x < *p; p -= h)
            p[h] = *p;
        p[h] = x;
    }
}

void sort(float* v, int n)
{
    int i, h = 0;
    while (2*(i = h*3+1) <= n)
        h = i;
    for (; h > 0; h /= 3)
        hsort(v, h, n);
}
SineDog
fuente
1

C 270 (golfizado)

#define N 1048576
void sort(float*v,int n)
{
float f[N],g;
int m[N],i,j,k,x;
g=v[0];k=0;
for(i=0;i<n;i++){for(j=0;j<n;j++){if(m[j]==1)continue;if(v[j]<g){g=v[j];k=j;}}f[i]=g;m[k]=1;for(x=0;x<n;x++){if(m[x]==0){g=v[x];k=x;break;}}}
for(i=0;i<n;i++){v[i]=f[i];}
}

Explicación: Se utiliza una matriz en blanco para almacenar cada número mínimo sucesivo. Una matriz int es una máscara con 0 que indica que el número aún no se ha copiado. Después de obtener el valor mínimo, una máscara = 1 omite los números ya utilizados. Luego, la matriz se copia nuevamente al original.

Cambié el código para eliminar el uso de las funciones de la biblioteca.

bacchusbeale
fuente
0

144

Descaradamente tomé el código de Johnny, agregué una pequeña optimización y comprimí el código de una manera muy sucia. Debería ser más corto y más rápido.

Tenga en cuenta que dependiendo de su compilador, sort (q, v + n- ++ q) debe reemplazarse por sort (++ q, v + nq).

#define w ;while(
void sort(float*v, int n){
    w n>1){
        float *p=v-1, *q=v+n, x=v[n/2], t
        w p<q){
            w *++p<x )
            w *--q>x );
            if( p<q ) t=*p, *p=*q, *q=t;
        }
        sort(q,v+n- ++q);
        n = p-v;
    }
}

Bueno, en realidad, comencé a formar mi código y lo optimicé, pero parece que Johnny ya tomó todas las decisiones correctas. Así que terminé con casi su código. No pensé en el truco del goto, pero podría prescindir.

Florian F
fuente
0

228 caracteres

Radixsort.

void sort(float* v, int n) {
#define A(x,y,z) for(x=y;x<z;x++)
#define B h[(a[i]^(a[i]>>31|1<<31))>>j*8&255]
    int m[1<<20],*a=v,*b=m,*t,i,j;
    A(j,0,4) {
        int h[256] = {};
        A(i,0,n) B++;
        A(i,1,256) h[i] += h[i-1];
        for (i = n-1; i >= 0; i--)
            b[--B] = a[i];
        t = a, a = b, b = t;
    }
}
Makarov
fuente