[ 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 sort
fungsi, termasuk tanda tangan, ditambah fungsi tambahan yang dipanggil (tetapi tidak termasuk kode pengujian).
Program harus menangani nilai numerik float
dan panjang array apa pun> = 0, hingga 2 ^ 20.
Saya akan pasang sort
dan 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 qsort
dimasukkan untuk perbandingan (Johnny lebih cepat!). Saya akan melakukan perbandingan akhir pada waktu penutupan.
sumber
Jawaban:
150 karakter
Quicksort.
Terkompresi.
sumber
150 karakter (tanpa spasi putih)
sumber
if(*w<*v) { t=v[++l]; v[l]=*w; *w=t; }
bisaif(*w<*v) t=v[++l], v[l]=*w, *w=t;
67 7069 karakterTidak 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-n
itu sama dengan++i != v+n
.sumber
if(a)b
->a?b:0
menyimpan char.++i-v-n
sama++i != v+n
saja dengan yang bersyarat saja, tentu saja.if(*i>v[n])...
->*i>v[n]?...:0
123 karakter (+3 baris baru)
Jenis Shell standar, terkompresi.
PS: ternyata masih 10x lebih lambat dari quicksort. Anda mungkin juga mengabaikan entri ini.
sumber
395 karakter
Mergesort.
Diformat.
sumber
331326327312 karakterApakah 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 ...
sumber
511424 karakterTempat radixsort
Pembaruan: Beralih ke jenis penyisipan untuk ukuran array yang lebih kecil (meningkatkan kinerja benchmark dengan faktor 4.0).
Diformat.
sumber
void*
dalamqsort
(baris 88) melempar dari aritmatika pointer.121114111 karakterBubbleort yang cepat dan kotor, dengan rekursi. Mungkin tidak terlalu efisien.
Atau, versi panjang
sumber
221193172 karakterHeapsort - Bukan yang terkecil, tetapi di tempat dan menjamin perilaku O (n * log (n)).
Terkompresi.
sumber
TEST_COUNT
= 3000, sepertinya gagal setidaknya satu tes.154166 karakterOK, ini quicksort yang lebih panjang tapi lebih cepat.
Berikut adalah koreksi untuk bertahan input yang diurutkan. Dan diformat karena ruang putih tidak masuk hitungan.
sumber
150 karakter
Shellsort (dengan kesenjangan Knuth).
Diformat.
sumber
C 270 (golf)
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.
sumber
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).
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.
sumber
228 karakter
Radixsort.
sumber