Sekarang semua orang telah mengembangkan keahlian pengkodean tingkat rendah (sering luar biasa) untuk Seberapa lambat Python sebenarnya? (Atau seberapa cepat bahasa Anda?) Dan Seberapa Lambat Apakah Python Sungguh (Bagian II)? sekarang saatnya untuk tantangan yang juga akan meregangkan kemampuan Anda untuk meningkatkan suatu algoritma.
Kode berikut menghitung daftar panjang 9. Posisi i
dalam daftar menghitung berapa kali setidaknya i
nol berturut-turut ditemukan ketika menghitung produk dalam antara F
dan S
. Untuk melakukan hal ini dengan tepat, ini mengulangi semua daftar F
panjang yang mungkin n
dan daftar S
panjang n+m-1
.
#!/usr/bin/python
import itertools
import operator
n=8
m=n+1
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n+m-1):
for F in itertools.product([-1,1], repeat = n):
i = 0
while (i<m and sum(map(operator.mul, F, S[i:i+n])) == 0):
leadingzerocounts[i] +=1
i+=1
print leadingzerocounts
Outputnya adalah
[4587520, 1254400, 347648, 95488, 27264, 9536, 4512, 2128, 1064]
Jika Anda meningkatkan n menjadi 10,12,14,16,18,20 menggunakan kode ini sangat cepat menjadi terlalu lambat.
Aturan
- Tantangannya adalah untuk memberikan hasil yang benar sebesar dan mungkin. Hanya nilai n yang relevan.
- Jika ada seri, kemenangan menuju ke kode tercepat di mesin saya untuk n terbesar.
- Saya berhak untuk tidak menguji kode yang membutuhkan waktu lebih dari 10 menit.
- Anda dapat mengubah algoritme dengan cara apa pun yang Anda suka asalkan memberikan hasil yang benar. Bahkan Anda harus mengubah algoritma untuk membuat kemajuan yang layak menuju kemenangan.
- Pemenang akan diberikan satu minggu sejak pertanyaan ditetapkan.
- Hadiah akan diberikan ketika jatuh tempo yang sedikit setelah ketika pemenang akan diberikan.
Mesin Saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda. Sebagai konsekuensinya, hanya gunakan perangkat lunak gratis yang mudah tersedia dan harap sertakan instruksi lengkap cara menyusun dan menjalankan kode Anda.
Status .
- C . n = 12 dalam 49 detik oleh @Fors
- Jawa . n = 16 dalam 3:07 oleh @PeterTaylor
- C ++ . n = 16 dalam 2:21 oleh @ilmale
- Rpython . n = 22 dalam 3:11 oleh @primo
- Jawa . n = 22 dalam 6:56 oleh @PeterTaylor
- Nimrod . n = 24 dalam 9:28 detik oleh @ReimerBehrends
Pemenangnya adalah Reimer Behrends dengan entri di Nimrod!
Sebagai tanda centang, output untuk n = 22 seharusnya [12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]
.
Kompetisi sudah berakhir, tetapi ... Saya akan menawarkan 200 poin untuk setiap pengiriman yang meningkat n dengan 2 (dalam 10 menit di komputer saya) sampai saya kehabisan poin. Penawaran ini terbuka selamanya .
sumber
Jawaban:
Nimrod (N = 22)
Kompilasi dengan
(Nimrod dapat diunduh di sini .)
Ini berjalan dalam waktu yang ditentukan untuk n = 20 (dan untuk n = 18 ketika hanya menggunakan utas tunggal, membutuhkan waktu sekitar 2 menit dalam kasus terakhir).
Algoritme menggunakan pencarian rekursif, memangkas pohon pencarian setiap kali produk dalam yang tidak nol ditemukan. Kami juga memotong ruang pencarian menjadi dua dengan mengamati bahwa untuk setiap pasangan vektor,
(F, -F)
kita hanya perlu mempertimbangkan satu karena yang lainnya menghasilkan set produk dalam yang sama (dengan meniadakanS
juga).Implementasinya menggunakan fasilitas metaprogramming Nimrod untuk membuka gulungan / sebaris beberapa level pertama dari pencarian rekursif. Ini menghemat sedikit waktu ketika menggunakan gcc 4.8 dan 4.9 sebagai backend dari Nimrod dan jumlah yang wajar untuk dentang.
Ruang pencarian dapat dipangkas lebih lanjut dengan mengamati bahwa kita hanya perlu mempertimbangkan nilai-nilai S yang berbeda dalam jumlah genap dari posisi N pertama dari pilihan kita F. Namun, kompleksitas atau kebutuhan memori yang tidak skala untuk nilai-nilai besar dari N, mengingat bahwa tubuh loop benar-benar dilewati dalam kasus-kasus itu.
Tabulasi di mana produk dalam adalah nol tampaknya lebih cepat daripada menggunakan fungsi penghitungan bit dalam loop. Rupanya mengakses tabel memiliki lokasi yang cukup bagus.
Tampaknya seolah-olah masalahnya harus sesuai dengan pemrograman dinamis, mengingat cara kerja pencarian rekursif, tetapi tidak ada cara yang jelas untuk melakukan itu dengan jumlah memori yang masuk akal.
Output contoh:
N = 16:
N = 18:
N = 20:
Untuk tujuan membandingkan algoritme dengan implementasi lainnya, N = 16 membutuhkan waktu sekitar 7,9 detik pada mesin saya ketika menggunakan utas tunggal dan 2,3 detik saat menggunakan empat inti.
N = 22 membutuhkan waktu sekitar 15 menit pada mesin 64-inti dengan gcc 4.4.6 sebagai backend Nimrod dan meluap bilangan bulat 64-bit
leadingZeros[0]
(mungkin bukan yang tidak ditandatangani, belum melihatnya).Pembaruan: Saya telah menemukan ruang untuk beberapa perbaikan lagi. Pertama, untuk nilai tertentu
F
, kita dapat menghitung 16 entri pertama dariS
vektor terkait secara tepat, karena mereka harus berbeda diN/2
tempat yang tepat . Jadi kita melakukan precompute daftar vektor bit dari ukuranN
yang memilikiN/2
bit diatur dan menggunakannya untuk mendapatkan bagian awalS
dariF
.Kedua, kita dapat meningkatkan pencarian rekursif dengan mengamati bahwa kita selalu tahu nilai
F[N]
(karena MSB adalah nol dalam representasi bit). Ini memungkinkan kami untuk memprediksi dengan tepat cabang mana yang kami rekur masuk dari produk dalam. Meskipun itu benar-benar memungkinkan kita mengubah seluruh pencarian menjadi loop rekursif, itu sebenarnya cukup mengacaukan prediksi cabang, jadi kami menjaga level teratas dalam bentuk aslinya. Kami masih menghemat waktu, terutama dengan mengurangi jumlah cabang yang kami lakukan.Untuk beberapa pembersihan, kode sekarang menggunakan bilangan bulat yang tidak ditandatangani dan memperbaikinya pada 64-bit (kalau-kalau ada seseorang yang ingin menjalankan ini pada arsitektur 32-bit).
Speedup keseluruhan adalah antara faktor x3 dan x4. N = 22 masih membutuhkan lebih dari delapan core untuk berjalan dalam waktu kurang dari 10 menit, tetapi pada mesin 64-core sekarang turun menjadi sekitar empat menit (dengan
numThreads
menambahkan sesuai). Saya tidak berpikir ada banyak ruang untuk perbaikan tanpa algoritma yang berbeda.N = 22:
Diperbarui lagi, memanfaatkan kemungkinan pengurangan lebih lanjut di ruang pencarian. Berjalan sekitar 9:49 menit untuk N = 22 pada mesin quadcore saya.
Pembaruan akhir (saya pikir). Kelas kesetaraan yang lebih baik untuk pilihan F, memotong runtime untuk N = 22 hingga
3:19 menit57 detik (sunting: Saya tidak sengaja menjalankannya dengan hanya satu utas) pada mesin saya.Perubahan ini memanfaatkan fakta bahwa sepasang vektor menghasilkan nol terkemuka yang sama jika satu dapat diubah menjadi yang lain dengan memutarnya. Sayangnya, optimasi tingkat rendah yang cukup kritis mensyaratkan bahwa bit atas F dalam representasi bit selalu sama, dan saat menggunakan kesetaraan ini memangkas ruang pencarian sedikit dan mengurangi runtime sekitar seperempat lebih dari menggunakan ruang keadaan yang berbeda pengurangan pada F, overhead dari menghilangkan optimasi level rendah lebih dari mengimbanginya. Namun, ternyata masalah ini dapat dihilangkan dengan juga mempertimbangkan fakta bahwa F yang merupakan invers satu sama lain juga setara. Sementara ini menambah kompleksitas perhitungan kelas ekivalensi sedikit, itu juga memungkinkan saya untuk mempertahankan optimasi tingkat rendah yang disebutkan di atas, yang mengarah ke peningkatan sekitar x3.
Satu lagi pembaruan untuk mendukung bilangan bulat 128-bit untuk akumulasi data. Untuk mengkompilasi dengan integer 128 bit, Anda harus
longint.nim
dari sini dan mengkompilasinya-d:use128bit
. N = 24 masih membutuhkan waktu lebih dari 10 menit, tetapi saya sudah memasukkan hasil di bawah ini untuk mereka yang tertarik.N = 24:
sumber
Jawa (
n=22
?)Saya pikir sebagian besar jawaban yang lebih baik daripada
n=16
menggunakan pendekatan yang mirip dengan ini, meskipun mereka berbeda dalam simetri yang mereka eksploitasi dan cara mereka membagi tugas di antara utas.Vektor yang didefinisikan dalam pertanyaan dapat diganti dengan string bit, dan produk dalam dengan XORing jendela yang tumpang tindih dan memeriksa bahwa ada
n/2
bit yang diatur secara tepat (dan karenanyan/2
bit dibersihkan). Adan! / ((n/2)!)
string (koefisien binomial pusat)n
bit dengann/2
bit yang ditetapkan (yang saya sebut string seimbang ), jadi untuk apa pun yang diberikanF
ada banyak jendelaS
yang memberikan produk dalam nol. Selain itu, aksi geserS
sepanjang satu dan memeriksa apakah kita masih dapat menemukan bit masuk yang memberikan nol produk dalam sesuai dengan mencari tepi dalam grafik yang node adalah jendela dan yang ujungnya menghubungkan sebuah nodeu
ke nodev
yangn-1
bit pertama adalah yang terakhirn-1
bitu
.Misalnya, dengan
n=6
danF=001001
kami mendapatkan grafik ini:dan untuk
F=001011
kita dapatkan grafik ini:Maka kita perlu menghitung untuk setiap
i
dari0
ken
berapa banyak jalan panjangi
ada, menjumlahkan atas grafik untuk setiapF
. Saya pikir kebanyakan dari kita menggunakan pencarian mendalam-pertama.Perhatikan bahwa grafiknya jarang: mudah untuk membuktikan bahwa setiap node memiliki paling banyak 1 dan paling banyak satu. Itu juga berarti bahwa satu-satunya struktur yang mungkin adalah rantai sederhana dan loop sederhana. Ini menyederhanakan DFS sedikit.
Saya mengeksploitasi beberapa simetri: string seimbang ditutup di bawah bit terbalik (
~
operasi dalam banyak bahasa dari keluarga ALGOL), dan di bawah rotasi bit, sehingga kita dapat mengelompokkan nilai-nilaiF
yang terkait dengan operasi ini dan hanya melakukan DFS sekali.Pada 2.5GHz Core 2 saya saya dapatkan
Karena komputer Lembik memiliki 8 core dan mengeksekusi program single-threaded saya sebelumnya dua kali lebih cepat dari saya, saya optimis bahwa itu akan dieksekusi
n=22
dalam waktu kurang dari 8 menit.sumber
C
Ini pada dasarnya hanya implementasi algoritma yang sedikit dioptimalkan dalam pertanyaan. Itu dapat mengelola
n=12
dalam batas waktu.Test run for
n=12
, termasuk kompilasi:Komentar: Saya baru saja mengaktifkan otak saya dan menggunakan beberapa kombinasi sederhana untuk menghitung bahwa nilai pertama akan selalu
n! / ((n / 2)!)^2 * 2^(n + m - 1)
. Tampak bagi saya bahwa harus ada solusi aljabar sepenuhnya untuk masalah ini.sumber
Jawa,
n=16
Untuk setiap nilai yang diberikan
F
ada\binom{n}{n/2}
vektor yang memiliki produk dalam nol dengannya. Jadi kita bisa membuat grafik yang simpulnya adalah vektor-vektor yang cocok dan ujung-ujungnya sesuai dengan pergeseranS
, dan kemudian kita hanya perlu menghitung lintasan panjang hinggan
dalam grafik.Saya belum mencoba mengoptimalkan mikro ini dengan mengganti kondisional dengan operasi bitwise, tetapi setiap penambahan dua kali lipat
n
waktu berjalan sekitar 16 kali lipat, jadi itu tidak akan membuat perbedaan yang cukup kecuali saya cukup dekat dengan ambang batas. Di mesin saya, saya tidak.Pada 2.5GHz Core 2 saya saya dapatkan
sumber
f
dan memulai simpul, lakukan iterasi di atas semuaf_xor_g
dengann/2
bit yang diatur secara tepat . Untuk masing-masing hal ini, lakukan iterate pada semuaf
dan ambilg = f ^ f_xor_g
.RPython, N = 22 ~ 3: 23
Multi-berulir, menggunakan keturunan rekursif tanpa tumpukan. Program menerima dua argumen baris perintah: N, dan jumlah utas pekerja.
Untuk Mengkompilasi
Buat klon lokal dari repositori PyPy menggunakan mercurial, git, atau apa pun yang Anda suka. Ketik mantra berikut (dengan asumsi skrip di atas diberi nama
convolution-high.py
):di mana
%PYPY_REPO%
merupakan variabel lingkungan yang menunjuk ke repositori yang baru saja Anda kloning. Kompilasi membutuhkan waktu sekitar satu menit.Contoh waktu
N = 16, 4 utas:
N = 18, 4 utas:
N = 20, 4 utas:
N = 22, 4 utas:
sumber
Python 3.3, N = 20, 3.5 menit
Disclaimer: maksud saya BUKAN untuk memposting ini sebagai jawaban saya sendiri, karena algoritma yang saya gunakan hanyalah port yang tidak tahu malu dari solusi RPython primo . Tujuan saya di sini adalah hanya untuk menunjukkan apa yang dapat Anda lakukan dengan Python jika Anda menggabungkan keajaiban Numpy dan Numba modul.
Numba menjelaskan secara singkat:
Pembaruan 1 : Saya perhatikan setelah melemparkan angka-angka di sekitar bahwa kita dapat melewati beberapa angka sepenuhnya. Jadi sekarang maxf menjadi (1 << n) // 2 dan maxs menjadi maxf 2 **. Ini akan mempercepat prosesnya sedikit. n = 16 sekarang hanya membutuhkan ~ 48s (turun dari 4,5 menit). Saya juga punya ide lain yang akan saya coba dan lihat apakah saya bisa membuatnya sedikit lebih cepat.
Pembaruan 2: Mengubah algoritma (solusi primo). Meskipun port saya belum mendukung multithreading, itu cukup sepele untuk ditambahkan. Bahkan dimungkinkan untuk melepaskan CPython GIL menggunakan Numba dan ctypes. Solusi ini, bagaimanapun, berjalan sangat cepat pada single core juga!
Dan akhirnya:
Ini berjalan di mesin saya di 212688ms atau ~ 3,5 menit.
sumber
C ++ N = 16
Saya menguji pada EEEPC dengan atom .. waktu saya tidak masuk akal. : D
Atom memecahkan n = 14 dalam 34 detik. Dan n = 16 dalam 20 menit. Saya ingin menguji n = 16 pada OP pc. Saya optimis.
Idenya adalah bahwa setiap kali kita menemukan solusi untuk F yang diberikan, kita telah menemukan 2 ^ i solusi karena kita dapat mengubah bagian bawah S yang mengarah ke hasil yang sama.
untuk mengkompilasi:
gcc 26459.cpp -std = c ++ 11 -O3 -march = asli -fstrict-aliasing -ftree-vectorize -Wall -pedantic -o 26459
sumber
JAVASCRIPT n: 12
Di komputer saya butuh 231,242 detik. Dalam Demo saya menggunakan pekerja web untuk mencegah pembekuan browser. Ini tentu dapat lebih ditingkatkan dengan pekerja paralel. Saya tahu JS tidak memiliki peluang dalam tantangan ini, tetapi saya melakukannya untuk bersenang-senang!
Klik untuk menjalankan Demo online
sumber
n=22
[235388928,86292480,19031048,5020640,1657928,783920,545408,481256,463832,460256,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744]
i.imgur.com/FIJa2Ch.pngFortran: n = 12
Saya baru saja membuat versi quick'n'dirty di Fortran, tidak ada optimasi kecuali OpenMP. Itu harus masuk tepat di bawah 10 menit untuk n = 12 pada mesin OPs, dibutuhkan 10:39 pada mesin saya yang lebih lambat.
Bilangan bulat 64-bit memang memiliki dampak kinerja negatif; kira saya harus memikirkan kembali seluruh algoritma untuk ini menjadi lebih cepat. Tidak tahu apakah saya akan repot, saya pikir saya lebih suka menghabiskan waktu memikirkan tantangan bagus yang lebih sesuai dengan selera saya. Jika ada orang lain yang ingin mengambil ini dan menjalankannya, silakan :)
sumber
Lua: n = 16
Penafian: niat saya BUKAN untuk memposting ini sebagai jawaban saya sendiri, karena algoritma yang saya gunakan dicuri tanpa malu-malu dari jawaban pintar Anna Jokela . yang tanpa malu-malu dicuri dari jawaban pintar ilmale .
Selain itu, bahkan tidak valid - ia memiliki ketidakakuratan yang disebabkan oleh angka floating point (akan lebih baik jika Lua akan mendukung bilangan bulat 64-bit). Namun, saya masih mengunggahnya, hanya untuk menunjukkan seberapa cepat solusi ini. Ini adalah bahasa pemrograman yang dinamis, namun saya dapat menghitung n = 16 dalam waktu yang wajar (1 menit pada CPU 800MHz).
Jalankan dengan LuaJIT, penerjemah standar terlalu lambat.
sumber
long long
alih-alihdouble
dengan pengaturan kompilasi), bukan LuaJIT.