Golfe + Classificação rápida em C

11

[ Última atualização: programa de benchmark e resultados preliminares disponíveis, veja abaixo]

Então, eu quero testar a relação velocidade / complexidade com um aplicativo clássico: classificação.

Escreva uma função ANSI C que classifique uma matriz de números de ponto flutuante em ordem crescente .

Você não pode usar nenhuma biblioteca, chamada de sistema, multithreading ou ASM embutido.

Entradas julgadas em dois componentes: comprimento e desempenho do código . Com a seguinte pontuação: as entradas serão classificadas por tamanho (log de # caracteres sem espaço em branco, para que você possa manter alguma formatação) e desempenho (log de # segundos sobre uma referência) e cada intervalo [melhor, pior] normalizado linearmente para [ 0,1] A pontuação total de um programa será a média das duas pontuações normalizadas. Menor pontuação ganha. Uma entrada por usuário.

A classificação precisará (eventualmente) estar em vigor (ou seja, a matriz de entrada deverá conter valores classificados no tempo de retorno) e você deverá usar a seguinte assinatura, incluindo nomes:

void sort(float* v, int n) {

}

Caracteres a serem contados: aqueles na sortfunção, assinatura incluída, além de funções adicionais chamadas por ela (mas não incluindo o código de teste).

O programa deve manipular qualquer valor numérico floate matrizes de comprimento> = 0, até 2 ^ 20.

Vou conectar sorte suas dependências em um programa de testes e compilar no GCC (sem opções sofisticadas). Vou alimentar várias matrizes, verificar a exatidão dos resultados e o tempo total de execução. Os testes serão executados em um Intel Core i7 740QM (Clarksfield) no Ubuntu 13. Os
comprimentos dos arrays abrangerão todo o intervalo permitido, com uma densidade mais alta de arrays curtos. Os valores serão aleatórios, com uma distribuição de cauda gorda (tanto na faixa positiva quanto na negativa). Elementos duplicados serão incluídos em alguns testes.
O programa de teste está disponível aqui: https://gist.github.com/anonymous/82386fa028f6534af263
Ele importa o envio como user.c. O número de casos de teste ( TEST_COUNT) no benchmark real será 3000. Por favor, forneça algum feedback nos comentários da pergunta.

Prazo: 3 semanas (7 de abril de 2014, 16:00 GMT). Vou postar o benchmark em 2 semanas.
Pode ser aconselhável postar perto do prazo, para evitar que seu código seja entregue aos concorrentes.

Resultados preliminares, a partir da publicação do benchmark:
Aqui estão alguns resultados. A última coluna mostra a pontuação como porcentagem, quanto maior, melhor, colocando Johnny Cage em primeiro lugar. Algoritmos com ordens de magnitude mais lentas que o restante foram executados em um subconjunto de testes e o tempo extrapolado. O próprio C qsortestá incluído para comparação (o Johnny é mais rápido!). Vou fazer uma comparação final na hora do fechamento.

insira a descrição da imagem aqui

Mau
fonte
3
Você pode fornecer a referência? Diferentes funções de classificação são executadas de maneira diferente com base na natureza dos dados. Por exemplo, a classificação de bolhas é mais rápida que a stdlib quicksort para pequenas matrizes. Gostaríamos de otimizar seu benchmark.
Claudiu
@ Claudiu Uma vez vi uma versão curta e adorável do quicksort, que funcionava tão bem quanto qualquer outro em dados em que cada elemento era diferente. Mas se alguns elementos eram os mesmos, funcionava a um ritmo absoluto. Não estou falando sobre o problema conhecido da má escolha do pivô em matrizes classificadas / parcialmente classificadas. Meus dados de teste foram completamente aleatoriamente embaralhados. Esta versão em particular simplesmente não gostava de duplicatas. Estranho, mas é verdade.
Level River St
3
Bem-vindo ao PPCG! Embora não proibimos desafios específicos ao idioma, incentivamos fortemente a formulação de perguntas de maneira independente do idioma sempre que possível. Considere isso para sua próxima pergunta e divirta-se com essa!
Jonathan Van Matre 14/03
1
@ steveverrill: Eu não sigo. Não importa qual é a sua unidade, porque você a escala de 0 a 1 de qualquer maneira. Se min é de 1 hora e no máximo é de 3 horas, algo que leva 1,5 horas será 0,25 independentemente de min é de 60 minutos, no máximo é de 180 minutos, e leva 90 minutos
claudiu
1
O OP apenas disse que não havia montagem em linha - ele não disse nada sobre intrínsecas.
Paul R

Respostas:

6

150 caracteres

Ordenação 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
fonte
Liderando a corrida!
Mau
3

150 caracteres (sem espaços em branco)

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.
fonte
Impressionante, primeira entrada!
Mau
Sinta-se à vontade para postar uma resposta com a SSE e eu a listarei no placar, embora eu esteja interessado em soluções 'portáteis' para o desafio.
Mau
if(*w<*v) { t=v[++l]; v[l]=*w; *w=t; }pode serif(*w<*v) t=v[++l], v[l]=*w, *w=t;
ASKASK
3

67 70 69 caracteres

Não é rápido, mas incrivelmente pequeno. É um híbrido entre um algoritmo de classificação de seleção e de classificação de bolhas, eu acho. Se você está realmente tentando ler isso, deve saber que ++i-v-né o mesmo 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;
    }
}
ASKASK
fonte
if(a)b-> a?b:0salva um caractere.
ugoren
Bem, ++i-v-né o mesmo que ++i != v+napenas em um condicional, é claro.
wchargin
@ugoren eu acho que você postou o comentário sobre a resposta errada
ASKASK
@ASKASK, if(*i>v[n])...->*i>v[n]?...:0
ugoren
Tem certeza de que é assim que a prescedência funciona?
ASKASK
2

123 caracteres (+3 novas linhas)

Uma classificação Shell padrão, compactada.

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];
}  

PS: descobriu que ainda é 10 vezes mais lento que o quicksort. Você também pode ignorar esta entrada.

Florian F
fonte
Sua escolha de lacunas poderia ser melhor. Provavelmente é por isso que isso é muito mais lento que o quicksort. pt.wikipedia.org/wiki/Shellsort#Gap_sequences
FDinoff
Fiquei surpreso ao descobrir o quanto a sequência de intervalos afeta a velocidade. Com uma boa sequência, chega perto do quicksort, mas permanece mais lento na minha experiência.
Florian F
Não seja muito duro consigo mesmo. Você está em terceiro lugar.
Kevin
2

Caráter 395

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++;}}}

Formatado.

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
fonte
2

331 326 327 312 caracteres

O radix classifica 8 bits de cada vez. Usa um bithack sofisticado para fazer com que os flutuadores negativos sejam classificados corretamente (roubados de http://stereopsis.com/radix.html ). Não é tão compacto, mas é realmente rápido (~ 8x mais rápido que a entrada preliminar mais rápida). Estou esperando o tamanho do código de velocidade superada ...

#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
fonte
2

511 424 caracteres

Radixsort no local

Atualização: Muda para a classificação de inserção para tamanhos de matriz menores (aumenta o desempenho de referência em um fator 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);}

Formatado.

/* 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
fonte
Agradável! Tente sinalizar a resposta original.
Mau
@ Mau: Obrigado e vai fazer. Queria mencionar um erro no código de benchmarking. O elenco para void*in qsort(linha 88) está jogando fora a aritmética do ponteiro.
MojoJojoBojoHojo 31/03
1

121 114 111 caracteres

Apenas uma bolha rápida e suja, com recursão. Provavelmente não é muito 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;}

Ou, a versão longa

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
fonte
Como um aparte, eu encontrei um algoritmo realmente interessante aqui: rosettacode.org/wiki/Sorting_algorithms/Pancake_sort#C Mas eu não posso obtê-lo comprimido o suficiente para bater 114 :)
CompuChip
seu programa parece não ser concluído em alguns casos e gravado fora dos limites em outros casos.
Mau
@ Marau Testei-o manualmente em algumas entradas e parecia funcionar bem, mas devido à falta de tempo não testei muito por isso, tenho certeza de que há algum comportamento ruim em algum lugar. Você poderia postar um caso de teste em que teve problemas, por favor?
CompuChip 30/03
programa de teste disponível acima :)
Mau
Hmm, tentei executá-lo, estou recebendo alguns erros `munmap_chunk (): ponteiro inválido` na parte de limpeza, mas nada no teste falhou. No entanto, você está certo de que há um erro de um por um, e parece que tenho alguns problemas de seqüenciamento (a lista de instruções separadas por vírgula não faz o que eu esperava). Vou tentar consertar.
30814 CompuChip
1

221 193 172 caracteres

Heapsort - Não é o menor, mas está no local e garante o comportamento de 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)
}
user19425
fonte
Você pode salvar alguns caracteres deduzindo o espaço em branco. E, possivelmente, também a assinatura da função obrigatória, mas como existem algumas entradas contadas, pedi ao interlocutor para esclarecer se deveria ser contada.
Jonathan Van Matre
@ user19425: Se você executar o programa de teste com TEST_COUNT= 3000, parece que falhará em pelo menos um teste.
Mau
1

154 166 caracteres

OK, aqui está uma seção rápida mais longa, mas mais rápida.

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;}}

Aqui está uma correção para sobreviver às entradas classificadas. E formatado, pois o espaço em branco não conta.

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
fonte
Esta versão parece estar fora dos limites em alguns casos, não sendo finalizada em outros.
Mau
PS: OK, é muito lento em um conjunto classificado. Mas a declaração do problema diz que a entrada é aleatória.
Florian F
Os valores são aleatórios. Eu nunca disse nada sobre em que ordem eles estariam :-) Mas sim, existem pedaços cobrindo cerca de 10% de todos os valores classificados em ordem crescente e outros 10% em ordem decrescente.
Mau
1
Justo. E um sort () deve funcionar na entrada classificada. Vou atualizar minha submissão, então ...
Florian F
1

150 caracteres

Shellsort (com intervalo de Knuth).

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;}
}

Formatado.

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
fonte
1

C 270 (golfe)

#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];}
}

Explicação: Uma matriz em branco é usada para armazenar cada número mínimo sucessivo. Uma matriz int é uma máscara com 0 indicando que o número ainda não foi copiado. Após obter o valor mínimo, uma máscara = 1 pula os números já usados. Em seguida, a matriz é copiada de volta ao original.

Mudei o código para eliminar o uso das funções da biblioteca.

bacchusbeale
fonte
0

144

Eu descaradamente peguei o código de Johnny, adicionei uma pequena otimização e o compactou de uma maneira muito suja. Deve ser mais curto e mais rápido.

Observe que, dependendo do seu compilador, a classificação (q, v + n- ++ q) deve ser substituída pela classificação (++ 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;
    }
}

Bem, na verdade, comecei a formar meu código e o otimizei, mas parece que Johnny já fez todas as escolhas certas. Então acabei com quase o código dele. Eu não pensei no truque do goto, mas poderia ficar sem.

Florian F
fonte
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
fonte