Tantangan ini sebagian merupakan tantangan algoritma, melibatkan beberapa matematika dan sebagian hanya merupakan tantangan kode tercepat.
Untuk bilangan bulat positif n
, pertimbangkan string acak 1
s dan 0
s yang panjangnya seragam n
dan sebut saja A
. Sekarang juga pertimbangkan string acak panjang n
yang dipilih secara seragam dan kedua yang nilainya adalah -1
, 0,
atau 1
dan menyebutnya B_pre
. Sekarang mari B
menjadi B_pre
+ B_pre
. Itu B_pre
disatukan dengan dirinya sendiri.
Sekarang perhatikan produk dalam A
dan B[j,...,j+n-1]
dan menyebutnya Z_j
dan indeks dari 1
.
Tugas
Outputnya harus berupa daftar n+1
fraksi. The i
Istilah th di output harus tepat probabilitas bahwa semua yang pertama i
istilah Z_j
dengan j <= i
sama 0
.
Skor
Yang terbesar di n
mana kode Anda memberikan hasil yang benar dalam waktu kurang dari 10 menit pada mesin saya.
Tie Breaker
Jika dua jawaban memiliki skor yang sama, jawaban yang pertama menang.
Dalam peristiwa (sangat sangat) tidak mungkin bahwa seseorang menemukan metode untuk mendapatkan skor tanpa batas, bukti valid pertama dari solusi semacam itu akan diterima.
Petunjuk
Jangan mencoba menyelesaikan masalah ini secara matematis, itu terlalu sulit. Cara terbaik dalam pandangan saya adalah kembali ke definisi dasar probabilitas dari sekolah menengah dan menemukan cara cerdas untuk mendapatkan kode untuk melakukan enumerasi lengkap tentang kemungkinan.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / interpreter / dll yang tersedia secara bebas. untuk Linux dan semua perpustakaan yang juga tersedia secara bebas untuk Linux.
Mesin saya Pengaturan waktu akan dijalankan di mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda. Sebagai akibatnya, hanya gunakan perangkat lunak gratis yang mudah tersedia dan harap sertakan instruksi lengkap cara menyusun dan menjalankan kode Anda.
Beberapa hasil tes. Pertimbangkan output pertama untuk masing-masing n
. Saat itulah i=1
. Untuk n
1-13 seharusnya.
1: 4/6
2: 18/36
3: 88/216
4: 454/1296
5: 2424/7776
6: 13236/46656
7: 73392/279936
8: 411462/1679616
9: 2325976/10077696
10: 13233628/60466176
11: 75682512/362797056
12: 434662684/2176782336
13: 2505229744/13060694016
Anda juga dapat menemukan formula umum untuk i=1
di http://oeis.org/A081671 .
Papan (dibagi berdasarkan bahasa)
- n = 15. Python + python paralel + pypy dalam 1min49detik oleh Jakube
- n = 17. C ++ dalam 3min37s oleh Keith Randall
- n = 16. C ++ dalam 2min38s oleh kuroi neko
sumber
Jawaban:
C ++, n = 18 dalam 9 menit pada 8 utas
(Beri tahu saya jika itu membuatnya kurang dari 10 menit di komputer Anda.)
Saya mengambil keuntungan dari beberapa bentuk simetri dalam array B. Itu adalah siklik (bergeser dengan satu posisi), pembalikan (membalik urutan elemen), dan tanda (ambil negatif dari setiap elemen). Pertama saya menghitung daftar B yang perlu kita coba dan beratnya. Kemudian setiap B dijalankan melalui rutin cepat (menggunakan instruksi bitcount) untuk semua nilai 2 ^ n dari A.
Inilah hasil untuk n == 18:
Kompilasi program di bawah ini dengan
g++ --std=c++11 -O3 -mpopcnt dot.cc
sumber
-pthread
lagi. Saya sampain=17
di mesin saya.Python 2 menggunakan pypy dan pp: n = 15 dalam 3 menit
Juga hanya kekuatan kasar yang sederhana. Menarik untuk dilihat, bahwa saya hampir mendapatkan kecepatan yang sama dengan kuroi neko dengan C ++. Kode saya dapat mencapai
n = 12
sekitar 5 menit. Dan saya hanya menjalankannya pada satu inti virtual.sunting: Mengurangi ruang pencarian dengan faktor
n
Saya melihat, bahwa vektor bersepeda
A*
dariA
menghasilkan angka yang sama seperti probabilitas (nomor yang sama) sebagai vektor asliA
ketika saya iterate lebihB
. Vektor misalnya The(1, 1, 0, 1, 0, 0)
memiliki probabilitas yang sama karena masing-masing dari vektor(1, 0, 1, 0, 0, 1)
,(0, 1, 0, 0, 1, 1)
,(1, 0, 0, 1, 1, 0)
,(0, 0, 1, 1, 0, 1)
dan(0, 1, 1, 0, 1, 0)
ketika memilih secara acakB
. Karena itu saya tidak perlu mengulangi masing-masing dari 6 vektor ini, tetapi hanya sekitar 1 dan ganticount[i] += 1
dengancount[i] += cycle_number
.Ini mengurangi kompleksitas dari
Theta(n) = 6^n
menjadiTheta(n) = 6^n / n
. Karenanya untukn = 13
ini sekitar 13 kali lebih cepat dari versi saya sebelumnya. Itu menghitungn = 13
dalam sekitar 2 menit 20 detik. Untukn = 14
itu masih agak terlalu lambat. Dibutuhkan sekitar 13 menit.sunting 2: Pemrograman multi-inti
Tidak terlalu senang dengan peningkatan selanjutnya. Saya memutuskan untuk juga mencoba menjalankan program saya pada banyak core. Pada 2 + 2 core saya, saya sekarang dapat menghitung
n = 14
dalam sekitar 7 menit. Hanya faktor 2 perbaikan.Kode ini tersedia di repo github ini: Tautan . Pemrograman multi-core sedikit jelek.
sunting 3: Mengurangi ruang pencarian untuk
A
vektor danB
vektorSaya memperhatikan simetri cermin yang sama untuk vektor
A
seperti yang kuroi neko lakukan. Masih tidak yakin, mengapa ini berhasil (dan jika berhasil untuk masing-masingn
).Pengurangan ruang pencarian untuk
B
vektor sedikit lebih pintar. Saya mengganti generasi vektor (itertools.product
), dengan fungsi sendiri. Pada dasarnya, saya mulai dengan daftar kosong dan meletakkannya di tumpukan. Sampai tumpukan kosong, saya menghapus daftar, jika tidak memiliki panjang yang sama dengann
, saya menghasilkan 3 daftar lainnya (dengan menambahkan -1, 0, 1) dan mendorongnya ke tumpukan. Daftar saya memiliki panjang yang sama dengann
, saya bisa mengevaluasi jumlahnya.Sekarang saya menghasilkan vektor sendiri, saya bisa memfilternya tergantung pada apakah saya dapat mencapai jumlah = 0 atau tidak. Misalnya jika vektor saya
A
adalah(1, 1, 1, 0, 0)
, dan vektor sayaB
terlihat(1, 1, ?, ?, ?)
, saya tahu, bahwa saya tidak dapat mengisi?
dengan nilai, jadi ituA*B = 0
. Jadi saya tidak perlu mengulangi semua 6 vektorB
formulir itu(1, 1, ?, ?, ?)
.Kita dapat memperbaiki ini, jika kita mengabaikan nilai-nilai untuk 1. Seperti disebutkan dalam pertanyaan, untuk nilai-nilai untuk
i = 1
adalah urutan A081671 . Ada banyak cara untuk menghitungnya. Saya memilih kekambuhan sederhana:a(n) = (4*(2*n-1)*a(n-1) - 12*(n-1)*a(n-2)) / n
. Karenai = 1
pada dasarnya kami dapat menghitung dalam waktu singkat, kami dapat memfilter lebih banyak vektorB
. MisalnyaA = (0, 1, 0, 1, 1)
danB = (1, -1, ?, ?, ?)
. Kita dapat mengabaikan vektor, di mana yang pertama? = 1
, karenaA * cycled(B) > 0
, untuk semua vektor ini. Saya harap Anda bisa mengikuti. Itu mungkin bukan contoh terbaik.Dengan ini saya bisa menghitung
n = 15
dalam 6 menit.edit 4:
Cepat menerapkan ide hebat kuroi neko, yang mengatakan, itu
B
dan-B
menghasilkan hasil yang sama. Speedup x2. Implementasinya hanya hack cepat.n = 15
dalam 3 menit.Kode:
Untuk kode lengkap kunjungi Github . Kode berikut hanya merupakan representasi dari fitur-fitur utama. Saya meninggalkan impor, pemrograman multicore, mencetak hasilnya, ...
Pemakaian:
Anda harus menginstal pypy (untuk Python 2 !!!). Modul python paralel tidak di-porting untuk Python 3. Kemudian Anda harus menginstal modul python paralel pp-1.6.4.zip . Ekstrak itu,
cd
ke dalam folder dan panggilpypy setup.py install
.Maka Anda dapat memanggil program saya dengan
pypy you-do-the-math.py 15
Secara otomatis akan menentukan jumlah cpu. Mungkin ada beberapa pesan kesalahan setelah menyelesaikan program, abaikan saja.
n = 16
harus dimungkinkan pada mesin Anda.Keluaran:
Catatan dan ide:
A & B
dan menghitung 01 dan 10 blok. Bersepeda dapat dilakukan dengan menggeser vektor dan menggunakan topeng, ... Saya benar-benar menerapkan semua ini, Anda dapat menemukannya di beberapa komitmen lama saya di Github. Tapi ternyata, lebih lambat dibandingkan dengan daftar. Saya kira, pypy benar-benar mengoptimalkan operasi daftar.sumber
pengganggu wol - C ++ - terlalu lambat
Yah karena programmer yang lebih baik mengambil implementasi C ++, saya memanggil berhenti untuk yang satu ini.
Membangun executable
Ini adalah sumber C ++ 11 mandiri yang mengkompilasi tanpa peringatan dan berjalan dengan lancar:
Jika Anda mengkompilasi dengan g ++, gunakan: g ++ -O3 -pthread -std = c ++ 11
melupakan
-pthread
akan menghasilkan dump inti yang bagus dan ramah.Optimalisasi
Istilah Z terakhir sama dengan yang pertama (Bpre x A dalam kedua kasus), sehingga dua hasil terakhir selalu sama, yang mengeluarkan komputasi nilai Z terakhir.
Keuntungannya bisa diabaikan, tetapi mengkodekannya tidak ada biaya sehingga Anda sebaiknya menggunakannya.
Seperti yang Jakube temukan, semua nilai siklik dari vektor A yang diberikan menghasilkan probabilitas yang sama.
Anda dapat menghitung ini dengan satu instance dari A dan mengalikan hasilnya dengan jumlah rotasi yang dimungkinkan. Grup rotasi dapat dengan mudah dihitung sebelumnya dalam waktu yang dapat diabaikan, jadi ini adalah perolehan kecepatan bersih yang besar.
Karena jumlah permutasi dari vektor panjang n adalah n-1, kompleksitas turun dari o (6 n ) ke o (6 n / (n-1)), pada dasarnya melangkah lebih jauh untuk waktu komputasi yang sama.
Tampaknya pasangan pola simetris juga menghasilkan probabilitas yang sama. Sebagai contoh, 100101 dan 101001.
Saya tidak punya bukti matematis tentang itu, tetapi secara intuitif ketika disajikan dengan semua pola B yang mungkin, setiap nilai A simetris akan berbelit-belit dengan nilai B simetrik yang sesuai untuk hasil global yang sama.
Ini memungkinkan untuk mengelompokkan lagi beberapa vektor A, untuk pengurangan sekitar 30% dari jumlah grup A.
SALAH
Untuk beberapa alasan semi-misterius, semua pola dengan hanya satu atau dua bit yang diatur menghasilkan hasil yang sama. Ini tidak mewakili banyak kelompok yang berbeda, tetapi masih dapat digabung tanpa biaya.Vektor B dan -B (B dengan semua komponen dikalikan -1) menghasilkan probabilitas yang sama.
(misalnya [1, 0, -1, 1] dan [-1, 0, 1, -1]).
Kecuali untuk vektor nol (semua komponen sama dengan 0), B dan -B membentuk sepasang vektor yang berbeda .
Ini memungkinkan untuk memotong jumlah nilai B menjadi dua dengan mempertimbangkan hanya satu dari setiap pasangan dan mengalikan kontribusinya dengan 2, menambahkan kontribusi global yang diketahui dari null B untuk setiap probabilitas hanya sekali.
Bagaimana itu bekerja
Jumlah nilai B sangat besar (3 n ), jadi pra-komputasi mereka akan membutuhkan jumlah memori yang tidak senonoh, yang akan memperlambat perhitungan dan akhirnya menghabiskan RAM yang tersedia.
Sayangnya, saya tidak dapat menemukan cara sederhana untuk menghitung setengah set nilai B yang dioptimalkan, jadi saya menggunakan pengkodean generator khusus.
Generator B yang perkasa sangat menyenangkan untuk dikodekan, meskipun bahasa yang mendukung mekanisme hasil akan memungkinkan untuk memprogramnya dengan cara yang jauh lebih elegan.
Singkatnya adalah mempertimbangkan "kerangka" dari vektor Bpre sebagai vektor biner di mana 1s mewakili nilai -1 atau +1 aktual.
Di antara semua nilai potensial + 1 / -1 ini, yang pertama ditetapkan ke +1 (dengan demikian memilih salah satu dari vektor B / -B yang mungkin), dan semua kemungkinan kombinasi + 1 / -1 yang tersisa disebutkan.
Terakhir, sistem kalibrasi sederhana memastikan setiap utas pekerja akan memproses berbagai nilai dengan ukuran yang kira-kira sama.
Nilai-nilai A sangat difilter untuk pengelompokan ulang dalam potongan yang dapat disinkronkan.
Ini dilakukan dalam fase pra-komputasi yang memaksa memeriksa semua nilai yang mungkin.
Bagian ini memiliki waktu eksekusi O (2 n ) yang dapat diabaikan dan tidak perlu dioptimalkan (kode yang sudah cukup terbaca seperti itu!).
Untuk mengevaluasi produk dalam (yang hanya perlu diuji terhadap nol), komponen -1 dan 1 B dikelompokkan kembali menjadi vektor biner.
Produk dalam adalah nol jika (dan hanya jika) ada jumlah yang sama dengan +1 dan -1s di antara nilai B yang sesuai dengan nilai A yang tidak nol.
Ini dapat dihitung dengan masking sederhana dan operasi penghitungan bit, dibantu dengan
std::bitset
itu akan menghasilkan kode hitung bit yang cukup efisien tanpa harus menggunakan instruksi intrinsik yang jelek.Pekerjaan ini dibagi rata di antara core, dengan afinitas CPU yang dipaksakan (setiap sedikit membantu, atau begitulah kata mereka).
Contoh hasil
Pertunjukan
Multithreading harus bekerja dengan sempurna pada ini, meskipun hanya core "benar" yang akan berkontribusi penuh pada kecepatan komputasi. CPU saya hanya memiliki 2 core untuk 4 CPU, dan keuntungan dari versi single-threaded adalah "hanya" sekitar 3,5.
Kompiler
Masalah awal dengan multithreading membuat saya percaya bahwa kompiler GNU berkinerja lebih buruk daripada Microsoft.
Setelah pengujian yang lebih menyeluruh, tampaknya g ++ menang sekali lagi, menghasilkan kode kira-kira 30% lebih cepat (rasio yang sama saya perhatikan pada dua proyek berat-komputasi lainnya).
Khususnya,
std::bitset
perpustakaan diimplementasikan dengan instruksi jumlah bit khusus oleh g ++ 4.8, sedangkan MSVC 2013 hanya menggunakan loop dari pergeseran bit konvensional.Seperti yang bisa diharapkan, kompilasi dalam 32 atau 64 bit tidak membuat perbedaan.
Penyempurnaan lebih lanjut
Saya perhatikan beberapa kelompok A yang menghasilkan probabilitas yang sama setelah semua operasi pengurangan, tetapi saya tidak bisa mengidentifikasi pola yang memungkinkan untuk mengelompokkan kembali mereka.
Berikut adalah pasangan yang saya perhatikan untuk n = 11:
sumber
terminate called after throwing an instance of 'std::system_error' what(): Unknown error -1 Aborted (core dumped)