[ Najnowsza aktualizacja: dostępny program testów porównawczych i wstępne wyniki, patrz poniżej]

Dlatego chcę przetestować kompromis prędkości / złożoności za pomocą klasycznej aplikacji: sortowania.

Napisz funkcję ANSI C, która sortuje tablicę liczb zmiennoprzecinkowych w kolejności rosnącej .

Nie można korzystać z żadnych bibliotek, wywołania systemowe, wielowątkowość lub inline ASM.

Wpisy oceniane na podstawie dwóch składników: długości kodu i wydajności. Punktacja będzie następująca: wpisy zostaną posortowane według długości (log # znaków bez spacji, dzięki czemu można zachować pewne formatowanie) i według wydajności (log # sekund ponad testem porównawczym), a każdy przedział [najlepszy, najgorszy] liniowo znormalizowany do [ 0,1]. Całkowity wynik programu będzie średnią z dwóch znormalizowanych wyników. Najniższy wynik wygrywa. Jeden wpis na użytkownika.

Sortowanie będzie musiało (ewentualnie) być na miejscu (tj. Tablica wejściowa będzie musiała zawierać posortowane wartości w czasie powrotu) i musisz użyć następującej sygnatury, w tym nazw:

void sort(float* v, int n) {

}

Znaki, które należy policzyć: te w sortfunkcji, w tym podpis, plus dodatkowe funkcje przez niego wywoływane (ale bez kodu testowego).

Program musi obsługiwać dowolne wartości liczbowe floati tablice o długości> = 0, do 2 ^ 20.

Włożę wtyczkę sorti jej zależności do programu testującego i skompiluję na GCC (żadnych fantazyjnych opcji). Wprowadzę do niego kilka tablic, zweryfikuję poprawność wyników i całkowity czas działania. Testy będą przeprowadzane na procesorze Intel Core i7 740QM (Clarksfield) pod Ubuntu 13.
Długości tablicy obejmą cały dozwolony zakres, z większą gęstością krótkich tablic. Wartości będą losowe, z rozkładem grubych ogonów (zarówno w zakresie dodatnim, jak i ujemnym). W niektórych testach zostaną uwzględnione powielone elementy.
Program testowy jest dostępny tutaj: https://gist.github.com/anonymous/82386fa028f6534af263
Importuje zgłoszenie jako user.c. Liczba przypadków testowych ( TEST_COUNT) w rzeczywistym teście będzie wynosić 3000. W komentarzach do pytania proszę podać wszelkie uwagi.

Termin: 3 tygodnie (7 kwietnia 2014, 16:00 GMT). Opublikuję test za 2 tygodnie.
Wskazane może być opublikowanie posta blisko terminu, aby uniknąć przekazywania kodu konkurentom.

Wstępne wyniki w momencie publikacji testu porównawczego:
Oto kilka wyników. Ostatnia kolumna pokazuje wynik w procentach, im wyższy, tym lepiej, stawiając Johnny'ego Cage'a na pierwszym miejscu. Algorytmy, które były o rząd wielkości wolniejsze niż reszta, były uruchamiane w podzbiorze testów i ekstrapolowane w czasie. Własność C qsortjest dołączona do porównania (Johnny's jest szybszy!). Przeprowadzę końcowe porównanie w czasie zamknięcia.

150 znaków

Szybkie sortowanie.

/* 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
     }
}

Sprężony.

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

150 znaków (bez białych znaków)

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

67 70 69 znaków

Wcale nie szybki, ale niezwykle mały. Chyba jest to hybryda między sortowaniem selekcji a algorytmem sortowania bąbelkowego. Jeśli naprawdę próbujesz to przeczytać, powinieneś wiedzieć, że ++i-v-nto samo ++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;
    }
}

123 znaki (+3 nowe linie)

Standardowy rodzaj powłoki, skompresowany.

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: odkryłem, że wciąż jest 10 razy wolniejszy niż Quicksort. Równie dobrze możesz zignorować ten wpis.

395 znaków

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

Sformatowany.

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

331 326 327 312 znaków

Czy Radix sortuje 8 bitów na raz. Używa fantazyjnego bithacka, aby poprawnie uzyskać ujemne liczby zmiennoprzecinkowe (skradzione z http://stereopsis.com/radix.html ). Nie jest tak kompaktowy, ale jest naprawdę szybki (~ 8 razy szybszy niż najszybszy zapis wstępny). Mam nadzieję, że rozmiar kodu szybkiego przekroczenia prędkości ...

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

511 424 znaków

W miejscu radixsort

Aktualizacja: Przełącza na sortowanie wstawiania dla mniejszych rozmiarów macierzy (zwiększa wydajność testu porównawczego czterokrotnie).

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

Sformatowany.

/* 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]);
}

121 114 111 znaków

Po prostu szybki i brudny zestaw pęcherzyków z rekurencją. Prawdopodobnie niezbyt wydajny.

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

Lub długa wersja

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

221 193 172 znaków

Heapsort - nie najmniejszy, ale na miejscu i gwarantuje zachowanie 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);
     }
}

Sprężony.

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

154 166 znaków

OK, tutaj jest szybszy, ale szybszy.

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

Oto poprawka na przetrwanie posortowanych danych wejściowych. I sformatowane, ponieważ białe znaki się nie liczą.

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

150 znaków

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

Sformatowany.

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

C 270 (golf)

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

Objaśnienie: Pusta tablica służy do przechowywania każdej kolejnej minimalnej liczby. Tablica int to maska ​​z wartością 0, która wskazuje, że liczba nie została jeszcze skopiowana. Po uzyskaniu wartości minimalnej maska ​​= 1 pomija już używane liczby. Następnie tablica jest kopiowana z powrotem do oryginału.

Zmieniłem kod, aby wyeliminować użycie funkcji bibliotecznych.

144

Bezwstydnie wziąłem kod Johnny'ego, dodałem drobną optymalizację i skompresowałem kod w bardzo brudny sposób. Powinien być krótszy i szybszy.

Zauważ, że w zależności od twojego kompilatora sort (q, v + n- ++ q) należy zastąpić 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;
    }
}

Właściwie zacząłem tworzyć kod i go optymalizować, ale wygląda na to, że Johnny już dokonał właściwych wyborów. Więc skończyłem z quasi jego kodem. Nie myślałem o sztuczce goto, ale mogłem się obejść.

228 znaków

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