Golf + Penyortiran cepat di C

11

[ Pembaruan terbaru: program benchmark dan resul pendahuluan tersedia, lihat di bawah ini]

Jadi saya ingin menguji tradeoff kecepatan / kompleksitas dengan aplikasi klasik: sorting.

Tulis fungsi ANSI C yang mengurutkan susunan angka floating point dalam urutan yang meningkat .

Anda tidak dapat menggunakan setiap perpustakaan, sistem panggilan, multithreading atau ASM inline.

Entri dinilai berdasarkan dua komponen: panjang kode dan kinerja. Mencetak sebagai berikut: entri akan diurutkan berdasarkan panjang (log karakter # tanpa spasi, sehingga Anda dapat menyimpan beberapa format) dan berdasarkan kinerja (log # detik di atas tolok ukur), dan setiap interval [terbaik, terburuk] dinormalisasi secara linear ke [ 0,1]. Skor total suatu program akan menjadi rata-rata dari dua skor yang dinormalisasi. Skor terendah menang. Satu entri per pengguna.

Penyortiran harus (akhirnya) ada di tempatnya (yaitu larik input harus berisi nilai yang diurutkan pada waktu kembali), dan Anda harus menggunakan tanda tangan berikut, termasuk nama:

void sort(float* v, int n) {

}

Karakter yang akan dihitung: yang ada dalam sortfungsi, termasuk tanda tangan, ditambah fungsi tambahan yang dipanggil (tetapi tidak termasuk kode pengujian).

Program harus menangani nilai numerik floatdan panjang array apa pun> = 0, hingga 2 ^ 20.

Saya akan pasang sortdan dependensinya ke dalam program pengujian dan kompilasi pada GCC (tidak ada opsi mewah). Saya akan memberi makan banyak array ke dalamnya, memverifikasi kebenaran hasil dan total jangka waktu. Pengujian akan dijalankan pada Intel Core i7 740QM (Clarksfield) di bawah Ubuntu 13.
Panjang array akan menjangkau seluruh rentang yang diizinkan, dengan kepadatan array pendek yang lebih tinggi. Nilai akan acak, dengan distribusi lemak-ekor (baik dalam rentang positif dan negatif). Elemen duplikat akan dimasukkan dalam beberapa tes.
Program pengujian tersedia di sini: https://gist.github.com/anonymous/82386fa028f6534af263
Ia mengimpor pengiriman sebagai user.c. Jumlah kasus uji ( TEST_COUNT) dalam tolok ukur yang sebenarnya adalah 3000. Harap berikan umpan balik dalam komentar pertanyaan.

Batas waktu: 3 minggu (7 April 2014, 16:00 GMT). Saya akan memposting patokan dalam 2 minggu.
Mungkin disarankan untuk memposting di dekat tenggat waktu untuk menghindari pemberian kode Anda kepada pesaing.

Hasil pendahuluan, seperti publikasi patokan:
Berikut adalah beberapa hasil. Kolom terakhir menunjukkan skor sebagai persentase, semakin tinggi semakin baik, menempatkan Johnny Cage di tempat pertama. Algoritma yang perintah besarnya lebih lambat dari yang lain dijalankan pada subset tes, dan waktu diekstrapolasi. C sendiri qsortdimasukkan untuk perbandingan (Johnny lebih cepat!). Saya akan melakukan perbandingan akhir pada waktu penutupan.

masukkan deskripsi gambar di sini

Mau
sumber
3
Bisakah Anda memberikan patokan? Fungsi penyortiran yang berbeda memiliki kinerja yang berbeda berdasarkan sifat data. Misalnya bubble sort lebih cepat daripada quickdort stdlib untuk array kecil. Kami mungkin ingin mengoptimalkan untuk tolok ukur Anda.
Claudiu
@Claudiu Saya pernah melihat versi singkat dari quicksort, yang berjalan sama baiknya dengan yang lainnya pada data di mana setiap elemen berbeda. Tetapi jika beberapa elemen sama, itu berjalan pada kecepatan siput absolut. Saya tidak berbicara tentang masalah pilihan buruk dari pivot dalam array yang diurutkan / diurutkan sebagian. Data pengujian saya dikacak secara acak. Versi khusus ini tidak suka duplikat. Aneh, tapi benar.
Level River St
3
Selamat datang di PPCG! Meskipun kami tidak melarang tantangan khusus bahasa, kami sangat mendorong perumusan pertanyaan dengan cara agnostik bahasa bila memungkinkan. Pertimbangkan untuk pertanyaan Anda berikutnya, dan bersenang-senanglah dengan yang ini!
Jonathan Van Matre
1
@steveverrill: Saya tidak mengikuti. Tidak masalah apa unit Anda karena Anda menskalakannya dari 0 hingga 1. Jika min adalah 1 jam dan maks adalah 3 jam, sesuatu yang membutuhkan 1,5 jam akan menjadi 0,25 terlepas dari apakah min adalah 60 menit, maks adalah 180 menit, dan itu membutuhkan 90 menit
Claudiu
1
OP hanya mengatakan tidak ada perakitan inline - dia tidak mengatakan apa-apa tentang intrinsik.
Paul R

Jawaban:

6

150 karakter

Quicksort.

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

Terkompresi.

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
sumber
Memimpin balapan!
Mau
3

150 karakter (tanpa spasi putih)

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.
sumber
Luar biasa, entri pertama!
Mau
Jangan ragu untuk mengirim jawaban dengan SSE dan saya akan mencantumkannya di papan skor, meskipun saya tertarik dengan solusi 'portabel' untuk tantangan tersebut.
Mau
if(*w<*v) { t=v[++l]; v[l]=*w; *w=t; }bisaif(*w<*v) t=v[++l], v[l]=*w, *w=t;
ASKASK
3

67 70 69 karakter

Tidak cepat sama sekali, tetapi sangat kecil. Ini adalah hibrida antara pemilihan semacam dan algoritma semacam gelembung kurasa. Jika Anda benar-benar mencoba membaca ini, maka Anda harus tahu bahwa ++i-v-nitu sama dengan ++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
sumber
if(a)b-> a?b:0menyimpan char.
ugoren
Nah, ++i-v-nsama ++i != v+nsaja dengan yang bersyarat saja, tentu saja.
wchargin
@ugoren saya pikir Anda memposting komentar itu pada jawaban yang salah
ASKASK
@ASKASK, if(*i>v[n])...->*i>v[n]?...:0
ugoren
Apakah Anda yakin itulah cara presedensi bekerja?
ASKASK
2

123 karakter (+3 baris baru)

Jenis Shell standar, terkompresi.

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: ternyata masih 10x lebih lambat dari quicksort. Anda mungkin juga mengabaikan entri ini.

Florian F
sumber
Kesenjangan pilihan Anda bisa lebih baik. Mungkin itu sebabnya ini jauh lebih lambat daripada quicksort. en.wikipedia.org/wiki/Shellsort#Gap_afterences
FDinoff
Saya kagum menemukan seberapa besar urutan celah memengaruhi kecepatan. Dengan urutan yang baik ia mendekati quicksort tetapi tetap lebih lambat dalam pengalaman saya.
Florian F
Jangan terlalu keras pada diri sendiri. Anda berada di posisi ketiga.
Kevin
2

395 karakter

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

Diformat.

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

331 326 327 312 karakter

Apakah radix mengurutkan 8 bit pada suatu waktu. Menggunakan bithack mewah untuk mendapatkan mengapung negatif untuk mengurutkan dengan benar (dicuri dari http://stereopsis.com/radix.html ). Ini tidak kompak, tetapi sangat cepat (~ 8x lebih cepat dari entri awal tercepat). Saya berharap untuk ukuran kode kecepatan truf ...

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

511 424 karakter

Tempat radixsort

Pembaruan: Beralih ke jenis penyisipan untuk ukuran array yang lebih kecil (meningkatkan kinerja benchmark dengan faktor 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);}

Diformat.

/* 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
sumber
Bagus! Coba beri tanda pada jawaban asli.
Mau
@Mau: Terima kasih dan akan lakukan. Ingin menyebutkan kesalahan dalam kode pembandingan. Pemain ke void*dalam qsort(baris 88) melempar dari aritmatika pointer.
MojoJojoBojoHojo
1

121 114 111 karakter

Bubbleort yang cepat dan kotor, dengan rekursi. Mungkin tidak terlalu efisien.

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

Atau, versi panjang

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
sumber
Sebagai tambahan, saya menemukan algoritma yang sangat menarik di sini: rosettacode.org/wiki/Sorting_algorithms/Pancake_sort#C Tapi saya tidak bisa mendapatkannya cukup dikompresi untuk mengalahkan 114 :)
CompuChip
program Anda tampaknya gagal menyelesaikan dalam beberapa kasus dan menulis di luar batas dalam kasus lain.
Mau
@Mau saya mengujinya pada beberapa input secara manual dan tampaknya berfungsi dengan baik, tetapi karena kurangnya waktu saya tidak mengujinya dengan sangat baik sehingga saya yakin ada beberapa perilaku buruk di suatu tempat. Bisakah Anda mengirim test case di mana Anda mengalami masalah?
CompuChip
program tes tersedia di atas :)
Mau
Hmm saya mencoba menjalankannya, saya mendapatkan beberapa kesalahan `munmap_chunk (): pointer tidak benar` di bagian pembersihan, tetapi tidak ada yang gagal tentang pengujian. Namun Anda benar bahwa ada kesalahan satu demi satu, dan saya tampaknya memiliki beberapa masalah pengurutan (daftar pernyataan yang dipisahkan koma tidak melakukan apa yang saya harapkan). Saya akan mencoba memperbaikinya.
CompuChip
1

221 193 172 karakter

Heapsort - Bukan yang terkecil, tetapi di tempat dan menjamin perilaku 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);
     }
}

Terkompresi.

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)
}
pengguna19425
sumber
Anda dapat menyimpan beberapa karakter dengan mengurangi spasi. Dan mungkin juga tanda tangan fungsi wajib, tetapi karena ada beberapa entri yang dihitung bahwa saya telah meminta penanya untuk mengklarifikasi apakah itu harus dihitung.
Jonathan Van Matre
@ user19425: Jika Anda menjalankan program pengujian dengan TEST_COUNT= 3000, sepertinya gagal setidaknya satu tes.
Mau
1

154 166 karakter

OK, ini quicksort yang lebih panjang tapi lebih cepat.

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

Berikut adalah koreksi untuk bertahan input yang diurutkan. Dan diformat karena ruang putih tidak masuk hitungan.

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
sumber
Versi ini tampaknya menulis di luar batas dalam beberapa kasus, tidak berakhir pada yang lain.
Mau
PS: Baik, sangat lambat pada set yang diurutkan. Namun pernyataan masalah mengatakan inputnya acak.
Florian F
Nilai-nilainya acak. Saya tidak pernah mengatakan apa-apa tentang urutannya :-) Tapi ya, ada potongan yang mencakup sekitar 10% dari semua nilai yang diurutkan dalam urutan naik dan 10% lainnya dalam urutan menurun.
Mau
1
Cukup adil. Dan sort () harus bekerja pada input yang diurutkan. Saya akan memperbarui kiriman saya, lalu ...
Florian F
1

150 karakter

Shellsort (dengan kesenjangan 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;}
}

Diformat.

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

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

Penjelasan: Array kosong digunakan untuk menyimpan setiap angka minimum berturut-turut. Array int adalah mask dengan 0 yang menunjukkan nomor belum disalin. Setelah mendapatkan nilai minimum, mask = 1 melewatkan angka yang sudah digunakan. Kemudian array disalin kembali ke aslinya.

Saya mengubah kode untuk menghilangkan penggunaan fungsi perpustakaan.

bacchusbeale
sumber
0

144

Saya tanpa malu-malu mengambil kode Johnny, menambahkan sedikit optimasi dan mengkompres kode dengan cara yang sangat kotor. Itu harus lebih pendek dan lebih cepat.

Perhatikan bahwa tergantung pada kompiler Anda, sortir (q, v + n- ++ q) harus diganti dengan sortir (++ 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;
    }
}

Sebenarnya, saya mulai membentuk kode saya dan mengoptimalkannya, tetapi sepertinya Johnny sudah membuat semua pilihan yang tepat. Jadi saya berakhir dengan kuasi kodenya. Saya tidak memikirkan trik goto, tetapi saya bisa melakukannya tanpa.

Florian F
sumber
0

228 karakter

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
sumber