Tugas
Tulis sebuah program, dalam bahasa pilihan Anda, yang membaca jalur input dari input standar hingga EOF, dan kemudian menuliskannya ke output standar dalam urutan ASCIIbetikal, mirip dengan sort
program baris perintah. Contoh pendek dan tidak licik dalam Python adalah:
import sys
for line in sorted(sys.stdin):
print(line.rstrip('\n'))
Bagian yang curang
Mirip dengan Perang OS , tujuan Anda adalah untuk membuktikan bahwa platform favorit Anda adalah "lebih baik", dengan membuat program Anda sengaja berjalan jauh lebih lambat pada platform yang bersaing. Demi kontes ini, "platform" terdiri dari kombinasi dari:
- Prosesor
- Arsitektur (x86, Alpha, ARM, MIPS, PowerPC, dll.)
- Bitness (64-bit vs 32-bit vs 16-bit)
- Big- versus little-endian
- Sistem operasi
- Windows vs Linux vs Mac OS, dll.
- Versi berbeda dari sistem operasi yang sama
- Implementasi bahasa
- Vendor kompiler / juru bahasa yang berbeda (mis., MSVC ++ vs. GCC)
- Versi berbeda dari kompiler / juru bahasa yang sama
Meskipun Anda dapat memenuhi persyaratan dengan menulis kode seperti:
#ifndef _WIN32
Sleep(1000);
#endif
Jawaban seperti itu seharusnya tidak dibatalkan. Tujuannya adalah untuk menjadi halus. Idealnya, kode Anda harus terlihat seperti tidak tergantung platform sama sekali. Jika Anda tidak memiliki #ifdef
pernyataan (atau kondisi berdasarkan os.name
atau System.Environment.OSVersion
atau apa pun), mereka harus memiliki pembenaran yang masuk akal (berdasarkan kebohongan, tentu saja).
Sertakan dalam jawaban Anda
- Kode
- Platform "favorit" dan "tidak disukai" Anda.
- Masukan untuk menguji program Anda.
- Waktu berjalan di setiap platform, untuk input yang sama.
- Deskripsi mengapa program berjalan sangat lambat pada platform yang tidak disukai.
Jawaban:
C
CleverSort
CleverSort adalah algoritma penyortiran string dua langkah yang canggih (yaitu over-engineered dan sub-optimal).
Pada langkah 1, itu dimulai dengan pra-pengurutan jalur input menggunakan pengurutan radix dan dua byte pertama dari setiap baris. Radix sort tidak komparatif dan bekerja sangat baik untuk string.
Pada langkah 2, ia menggunakan jenis penyisipan pada daftar string yang telah diurutkan sebelumnya. Karena daftar ini hampir diurutkan setelah langkah 1, jenis penyisipan cukup efisien untuk tugas ini.
Kode
Platform
Kita semua tahu bahwa mesin big-endian jauh lebih efisien daripada mesin kecil-endian mereka. Untuk pembandingan, kami akan mengompilasi CleverSort dengan optimisasi dihidupkan dan membuat daftar besar secara acak (lebih dari 100.000 string) dari baris 4-byte:
Benchmark big-endian
Tidak terlalu buruk.
Bechmark Little-Endian
Boo, Endian kecil! Boo!
Deskripsi
Jenis penyisipan sangat efisien untuk daftar yang hampir diurutkan, tetapi sangat tidak efisien untuk daftar yang diurutkan secara acak.
Bagian curang CleverSort adalah makro FIRSTSHORT :
Pada mesin big-endian, memesan string dua bilangan bulat 8-bit secara leksikografis atau mengubahnya menjadi bilangan bulat 16-bit dan memesannya setelah itu menghasilkan hasil yang sama.
Secara alami, ini dimungkinkan pada mesin-mesin little-endian juga, tetapi makro seharusnya
yang berfungsi seperti yang diharapkan di semua platform.
"Benchmark big-endian" di atas sebenarnya adalah hasil dari menggunakan makro yang tepat.
Dengan mesin makro dan mesin little-endian yang salah, daftar diurutkan berdasarkan karakter kedua dari setiap baris, menghasilkan urutan acak dari sudut pandang leksikografis. Jenis penyisipan berperilaku sangat buruk dalam kasus ini.
sumber
Python 2 vs. Python 3
Jelas, Python 3 beberapa kali lipat lebih cepat dari Python 2. Mari kita ambil contoh penerapan algoritma Shellsort ini :
Kode
Tolok ukur
Siapkan input tes. Ini diambil dari jawaban Dennis tetapi dengan lebih sedikit kata - Python 2 sangat lambat ...
Python 2
Python 3
Di mana kode curangnya?
Saya berasumsi beberapa pembaca mungkin ingin memburu penipu itu sendiri, jadi saya menyembunyikan jawabannya dengan tag spoiler.
Bonus 1:
Bonus 2:
sumber
flag
terlihat hanya untuk menulis, tidak bisakah Anda menghapusnya? Juga,r
tampaknya berlebihan jika Anda melakukannyaif lst[i+h] < lst[i]: ...
. Di sisi lain, jika Anda tetapr
mengapa melakukan swap? Tidak bisakah kamu melakukannyalst[i+h] = lst[i]
? Apakah semua ini merupakan gangguan yang disengaja?