Tantangannya adalah untuk menulis kode tercepat yang mungkin untuk menghitung permanen dari sebuah matriks .
Permanen dari n
-by- n
matrix A
= ( a
i,j
) didefinisikan sebagai
Di sini S_n
mewakili set semua permutasi dari [1, n]
.
Sebagai contoh (dari wiki):
Dalam pertanyaan ini semua matriks berbentuk bujur sangkar dan hanya akan memiliki nilai -1
dan 1
di dalamnya.
Contohnya
Memasukkan:
[[ 1 -1 -1 1]
[-1 -1 -1 1]
[-1 1 -1 1]
[ 1 -1 -1 1]]
Permanen:
-4
Memasukkan:
[[-1 -1 -1 -1]
[-1 1 -1 -1]
[ 1 -1 -1 -1]
[ 1 -1 1 -1]]
Permanen:
0
Memasukkan:
[[ 1 -1 1 -1 -1 -1 -1 -1]
[-1 -1 1 1 -1 1 1 -1]
[ 1 -1 -1 -1 -1 1 1 1]
[-1 -1 -1 1 -1 1 1 1]
[ 1 -1 -1 1 1 1 1 -1]
[-1 1 -1 1 -1 1 1 -1]
[ 1 -1 1 -1 1 -1 1 -1]
[-1 -1 1 -1 1 1 1 1]]
Permanen:
192
Memasukkan:
[[1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1],
[1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, 1, -1],
[-1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, -1],
[-1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, -1],
[-1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1],
[1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1],
[1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1],
[1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
[1, -1, -1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1],
[-1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1],
[-1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1],
[1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1],
[-1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, -1, 1],
[1, 1, -1, -1, -1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1],
[1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
[1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1],
[-1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1],
[1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1],
[1, 1, 1, -1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1],
[-1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1]]
Permanen:
1021509632
Tugas
Anda harus menulis kode yang, diberikan n
oleh n
matriks, menghasilkan permanen.
Karena saya perlu menguji kode Anda, akan sangat membantu jika Anda dapat memberikan cara sederhana bagi saya untuk memberikan matriks sebagai input ke kode Anda, misalnya dengan membaca dari standar di.
Berhati-hatilah karena permanen bisa besar (semua matriks 1s adalah kasus ekstrim).
Skor dan dasi
Saya akan menguji kode Anda secara acak + -1 matriks ukuran yang meningkat dan menghentikan pertama kali kode Anda membutuhkan lebih dari 1 menit di komputer saya. Matriks penilaian akan konsisten untuk semua pengiriman untuk memastikan keadilan.
Jika dua orang mendapatkan skor yang sama maka pemenangnya adalah yang tercepat untuk nilai tersebut n
. Jika mereka berada dalam 1 detik satu sama lain maka itu adalah yang diposting terlebih dahulu.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa dan pustaka yang tersedia yang Anda suka tetapi tidak ada fungsi yang sudah ada sebelumnya untuk menghitung permanen. Jika memungkinkan, alangkah baiknya untuk dapat menjalankan kode Anda, jadi silakan sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di Linux jika memungkinkan. `
Implementasi referensi
Sudah ada pertanyaan pertanyaan codegolf dengan banyak kode dalam berbagai bahasa untuk menghitung permanen untuk matriks kecil. Mathematica dan Maple juga memiliki implementasi permanen jika Anda dapat mengaksesnya.
Mesin Saya Pengaturan waktu akan dijalankan pada mesin 64-bit saya. Ini adalah instalasi ubuntu standar dengan RAM 8GB, Prosesor Delapan-Core AMD FX-8350 dan Radeon HD 4250. Ini juga berarti saya harus dapat menjalankan kode Anda.
Informasi tingkat rendah tentang mesin saya
cat /proc/cpuinfo/|grep flags
memberi
Flags flag: fpu vme de pse tc tl msr pae mce cx8 apic mc mcr pge mca f16c lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs xop skinit wdt lwp fma4 tce nodeid_msr tbm topoext perfctr_nb cpb hw_memilikibataspermukaantidakmemilikibubuhmemutuskanmemutuskanmemutakhirkansampai3dakmemutakhirkandenganmemutakhirkankekdot
Saya akan mengajukan pertanyaan multi-bahasa lanjutan yang tidak terkait dengan masalah Int besar sehingga pecinta Scala , Nim , Julia , Rust , Bash dapat memamerkan bahasa mereka juga.
Papan pemimpin
- n = 33 (45 detik. 64 detik untuk n = 34). Ton Hospel dalam C ++ dengan g ++ 5.4.0.
- n = 32 (32 detik). Dennis dalam C dengan gcc 5.4.0 menggunakan bendera gcc Ton Hospel.
- n = 31 (54 detik). Christian Sievers di Haskell
- n = 31 (60 detik). primo dengan rpython
- n = 30 (26 detik). ezrast di Rust
- n = 28 (49 detik). xnor dengan Python + pypy 5.4.1
- n = 22 (25 detik). Shebang dengan Python + pypy 5.4.1
Catatan . Dalam praktiknya penentuan waktu untuk Dennis dan Ton Hospel sangat bervariasi karena alasan misterius. Misalnya mereka tampaknya lebih cepat setelah saya memuat peramban web! Pengaturan waktu yang dikutip adalah yang tercepat dalam semua tes yang telah saya lakukan.
sumber
Jawaban:
gcc C ++ n ≈ 36 (57 detik di sistem saya)
Menggunakan rumus Glynn dengan kode Grey untuk pembaruan jika semua jumlah kolom genap, jika tidak menggunakan metode Ryser. Berurutan dan vektor. Dioptimalkan untuk AVX, jadi jangan berharap banyak pada prosesor yang lebih lama. Jangan repot-repot dengan
n>=35
untuk matriks dengan hanya +1 bahkan jika sistem Anda cukup cepat karena akumulator 128 bit yang ditandatangani akan melimpah. Untuk matriks acak Anda mungkin tidak akan mencapai overflow. Untukn>=37
pengganda internal akan mulai meluap untuk semua1/-1
matriks. Jadi hanya gunakan program ini untukn<=36
.Berikan saja elemen matriks pada STDIN yang dipisahkan oleh segala jenis spasi
permanent.cpp
:sumber
2 << (n-1)
pada akhirnya yang berarti akumulator int128 saya meluap jauh sebelum titik itu.C99, n ≈ 33 (35 detik)
Input saat ini agak rumit; itu diambil dengan baris sebagai argumen baris perintah, di mana setiap entri diwakili oleh tanda, yaitu, + menunjukkan 1 dan - menunjukkan -1 .
Uji coba
sumber
popcnt
). Jika itu menghemat waktu, rintangan besar berikutnya adalah tipe integer. Untuk matriks yang dihasilkan secara acak, permanen relatif kecil. Jika saya dapat menemukan cara mudah untuk menghitung batasan sebelum melakukan perhitungan yang sebenarnya, saya mungkin membungkus semuanya dalam kondisi besar.Python 2, n ≈ 28
Menggunakan rumus Glynn dengan a kode Grey untuk pembaruan. Berjalan
n=23
dalam semenit di mesin saya. Seseorang pasti dapat melakukan implementasi yang lebih baik dalam bahasa yang lebih cepat dan dengan struktur data yang lebih baik. Ini tidak menggunakan bahwa matriks bernilai ± 1.Implementasi rumus Ryser sangat mirip, menjumlahkan semua 0/1 vektor koefisien daripada ± 1-vektor. Dibutuhkan sekitar dua kali lebih panjang dari rumus Glynn karena menambahkan lebih dari semua vektor seperti itu, sedangkan Glynn membagi dua yang menggunakan simetri hanya dengan yang dimulai dengan
+1
.sumber
pypy
ini dapat dengan mudah menghitungn=28
dalam 44,6 detik. Sistem Lembik tampaknya cukup sebanding dengan tambang dalam kecepatan jika tidak sedikit lebih cepat.Haskell, n = 31 (54d)
Dengan banyak kontribusi yang tak ternilai oleh @Angs: gunakan
Vector
, gunakan produk hubungan pendek, lihat ganjil n.Upaya pertama saya pada paralelisme di Haskell. Anda dapat melihat banyak langkah pengoptimalan melalui riwayat revisi. Hebatnya, sebagian besar perubahannya sangat kecil. Kode ini didasarkan pada rumus di bagian "rumus Balasubramanian-Bax / Franklin-Glynn" dalam artikel Wikipedia tentang menghitung permanen .
p
menghitung permanen. Ini disebut viapt
yang mentransformasikan matriks dengan cara yang selalu valid, tetapi sangat berguna untuk matriks yang kita dapatkan di sini.Kompilasi dengan
ghc -O2 -threaded -fllvm -feager-blackholing -o <name> <name>.hs
. Untuk menjalankan dengan parallelisation, memberikan runtime parameter seperti ini:./<name> +RTS -N
. Masukan dari stdin dengan daftar yang dipisahkan koma bersarang dalam tanda kurung seperti[[1,2],[3,4]]
pada contoh terakhir (baris baru diizinkan di mana-mana).sumber
Data.Vector
. Perubahan diluar yang berubah jenis fungsi:import qualified Data.Vector as V
,x (V.zipWith(-) p v) vs (-m) c' )
,p (v:vs) = x (foldl (V.zipWith (+)) v vs) (map (V.map (2*)) vs) 1 11
,main = getContents >>= print . p . map V.fromList . read
V.product
). Itu hanya memberi saya ~ 10%. Mengubah kode sehingga vektor hanya berisiInt
s. Tidak apa-apa karena hanya ditambahkan, angka besar datang dari perkalian. Lalu ~ 20%. Saya telah mencoba perubahan yang sama dengan kode lama, tetapi pada saat itu memperlambatnya. Saya mencoba lagi karena memungkinkan untuk menggunakan vektor tanpa kotak , yang banyak membantu!x p _ m _ = m * (sum $ V.foldM' (\a b -> if b==0 then Nothing else Just $ a*fromIntegral b) 1 p)
- produk sebagai lipatan monadik di mana 0 adalah kasus khusus. Tampaknya bermanfaat lebih sering daripada tidak.Transversable
(saya melihat Anda tidak mengubah makanproduct
sebelumnya bukan kesalahan ...) untuk ghc dari misalnya Debian stable. Itu menggunakan bentuk input, tapi itu tampaknya baik-baik saja: kami tidak mengandalkan itu, hanya mengoptimalkan untuk itu. Membuat pengaturan waktu jauh lebih menarik: matriks acak 30x30 saya sedikit lebih cepat dari 29x29, tetapi 31x31 membutuhkan waktu 4x. - INLINE itu sepertinya tidak berhasil untuk saya. AFAIK diabaikan untuk fungsi rekursif.product
tetapi lupa. Tampaknya hanya panjang yang memiliki nolp
, jadi untuk panjang ganjil kita harus menggunakan produk reguler alih-alih korsleting untuk mendapatkan yang terbaik dari kedua dunia.Karat + extprim
Ryser langsung dengan implementasi kode Gray ini membutuhkan waktu sekitar
6590 detik untuk menjalankan n = 31 pada laptop saya.Saya membayangkan mesin Anda akan sampai di sana di bawah 60-an.Saya menggunakan extprim 1.1.1 untuki128
.Saya tidak pernah menggunakan Rust dan tidak tahu apa yang saya lakukan. Tidak ada opsi kompiler selain apa pun yang
cargo build --release
dilakukan. Komentar / saran / optimisasi dihargai.Doa identik dengan program Dennis.
sumber
git clone https://gitlab.com/ezrast/permanent.git; cd permanent; cargo build --release
jika Anda ingin memastikan memiliki setup yang sama dengan saya. Cargo akan menangani ketergantungan. Biner masuktarget/release
.Mathematica, n ≈ 20
Menggunakan
Timing
perintah, 20x20 matriks membutuhkan sekitar 48 detik di sistem saya. Ini tidak seefisien yang lain karena bergantung pada fakta bahwa permanen dapat ditemukan sebagai koefisien produk polimomial dari setiap baris matriks. Penggandaan polinomial yang efisien dilakukan dengan membuat daftar koefisien dan melakukan konvolusi menggunakanListConvolve
. Ini membutuhkan waktu O (2 n n 2 ) dengan asumsi konvolusi dilakukan menggunakan Fast Fourier transform atau sejenisnya yang membutuhkan waktu O ( n log n ).sumber
Python 2, n = 22 [Referensi]
Ini adalah implementasi 'referensi' yang saya bagikan dengan Lembik kemarin, ia gagal membuatnya
n=23
beberapa detik di mesinnya, di komputer saya itu melakukannya dalam waktu sekitar 52 detik. Untuk mencapai kecepatan ini, Anda perlu menjalankan ini melalui PyPy.Fungsi pertama menghitung permanen yang mirip dengan bagaimana determinan dapat dihitung, dengan memeriksa setiap submatrix sampai Anda dibiarkan dengan 2x2 yang Anda dapat menerapkan aturan dasar. Ini sangat lambat .
Fungsi kedua adalah yang mengimplementasikan fungsi Ryser (persamaan kedua yang tercantum di Wikipedia). Set
S
pada dasarnya adalah powerset angka{1,...,n}
(variabels_list
dalam kode).sumber
RPython 5.4.1, n ≈ 32 (37 detik)
Untuk mengkompilasi, unduh sumber PyPy terbaru, dan jalankan yang berikut:
Eksekusi yang dihasilkan akan diberi nama
matrix-permanent-c
atau serupa di direktori kerja saat ini.Pada PyPy 5.0, primitif threading RPython jauh lebih primitif daripada dulu. Utas yang baru lahir membutuhkan GIL, yang lebih atau kurang berguna untuk komputasi paralel. Saya telah menggunakan
fork
sebagai gantinya, jadi mungkin tidak berfungsi seperti yang diharapkan pada Windows,meskipun saya belum diujigagal untuk mengkompilasi (unresolved external symbol _fork
).Yang dapat dieksekusi menerima hingga dua parameter baris perintah. Yang pertama adalah jumlah utas, parameter opsional kedua adalah
n
. Jika disediakan, matriks acak akan dihasilkan, jika tidak maka akan dibaca dari stdin. Setiap baris harus dipisahkan baris baru (tanpa baris baru jejak), dan setiap ruang nilai dipisahkan. Input contoh ketiga akan diberikan sebagai:Contoh Penggunaan
metode
Saya telah menggunakan rumus Balasubramanian-Bax / Franklin-Glynn , dengan kompleksitas runtime O (2 n n) . Namun, alih-alih mengulangi δ dalam urutan kode abu-abu, saya malah mengganti multiplikasi vektor-baris dengan operasi xor tunggal (pemetaan (1, -1) → (0, 1)). Jumlah vektor juga dapat ditemukan dalam satu operasi, dengan mengambil n minus dua kali jumlah pop.
sumber
Racket 84 byte
Fungsi sederhana berikut berfungsi untuk matriks yang lebih kecil tetapi tergantung pada mesin saya untuk matriks yang lebih besar:
Tidak Disatukan:
Kode dapat dengan mudah dimodifikasi untuk jumlah baris dan kolom yang tidak sama.
Pengujian:
Keluaran:
Seperti yang saya sebutkan di atas, itu tergantung pada pengujian berikut:
sumber