Tantangannya adalah untuk menulis kode tercepat yang mungkin untuk menghitung Hafnian dari sebuah matriks .
The Hafnian dari simetris 2n
-by- 2n
matriks A
didefinisikan sebagai:
Di sini S 2n mewakili himpunan semua permutasi bilangan bulat dari 1
ke 2n
, yaitu [1, 2n]
.
Tautan wikipedia juga memberikan rumus tampilan berbeda yang mungkin menarik (dan bahkan metode yang lebih cepat ada jika Anda melihat lebih jauh di web). Halaman wiki yang sama berbicara tentang matriks kedekatan tetapi kode Anda juga bisa digunakan untuk matriks lain. Anda dapat mengasumsikan nilai-nilai semua akan menjadi bilangan bulat tetapi bukan berarti semuanya positif.
Ada juga algoritma yang lebih cepat tetapi tampaknya sulit untuk dipahami. dan Christian Sievers adalah yang pertama mengimplementasikannya (dalam Haskell).
Dalam pertanyaan ini semua matriks berbentuk bujur sangkar dan simetris dengan dimensi genap.
Implementasi referensi (perhatikan ini menggunakan metode paling lambat yang mungkin).
Berikut ini beberapa contoh kode python dari Mr. Xcoder.
from itertools import permutations
from math import factorial
def hafnian(matrix):
my_sum = 0
n = len(matrix) // 2
for sigma in permutations(range(n*2)):
prod = 1
for j in range(n):
prod *= matrix[sigma[2*j]][sigma[2*j+1]]
my_sum += prod
return my_sum / (factorial(n) * 2 ** n)
print(hafnian([[-1, 1, 1, -1, 0, 0, 1, -1], [1, 0, 1, 0, -1, 0, -1, -1], [1, 1, -1, 1, -1, -1, 0, -1], [-1, 0, 1, -1, -1, 1, -1, 0], [0, -1, -1, -1, -1, 0, 0, -1], [0, 0, -1, 1, 0, 0, 1, 1], [1, -1, 0, -1, 0, 1, 1, 0], [-1, -1, -1, 0, -1, 1, 0, 1]]))
4
M = [[1, 1, 0, 0, 0, 0, 0, 1, 0, 0], [1, 1, -1, 0, -1, 1, 1, 1, 0, -1], [0, -1, -1, -1, 0, -1, -1, 0, -1, 1], [0, 0, -1, 1, -1, 1, -1, 0, 1, -1], [0, -1, 0, -1, -1, -1, -1, 1, -1, 1], [0, 1, -1, 1, -1, 1, -1, -1, 1, -1], [0, 1, -1, -1, -1, -1, 1, 0, 0, 0], [1, 1, 0, 0, 1, -1, 0, 1, 1, -1], [0, 0, -1, 1, -1, 1, 0, 1, 1, 1], [0, -1, 1, -1, 1, -1, 0, -1, 1, 1]]
print(hafnian(M))
-13
M = [[-1, 0, -1, -1, 0, -1, 0, 1, -1, 0, 0, 0], [0, 0, 0, 0, 0, -1, 0, 1, -1, -1, -1, -1], [-1, 0, 0, 1, 0, 0, 0, 1, -1, 1, -1, 0], [-1, 0, 1, -1, 1, -1, -1, -1, 0, -1, -1, -1], [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, -1, 0], [-1, -1, 0, -1, 0, 0, 1, 1, 1, 1, 1, 0], [0, 0, 0, -1, 0, 1, 1, -1, -1, 0, 1, 0], [1, 1, 1, -1, 0, 1, -1, 1, -1, -1, -1, -1], [-1, -1, -1, 0, 0, 1, -1, -1, -1, 1, -1, 0], [0, -1, 1, -1, 1, 1, 0, -1, 1, -1, 1, 1], [0, -1, -1, -1, -1, 1, 1, -1, -1, 1, 0, -1], [0, -1, 0, -1, 0, 0, 0, -1, 0, 1, -1, 1]]
print(hafnian(M))
13
M = [[-1, 1, 0, 1, 0, -1, 0, 0, -1, 1, -1, 1, 0, -1], [1, -1, 1, -1, 1, 1, -1, 0, -1, 1, 1, 0, 0, -1], [0, 1, 1, 1, -1, 1, -1, -1, 0, 0, -1, 0, -1, -1], [1, -1, 1, -1, 1, 0, 1, 1, -1, -1, 0, 0, 1, 1], [0, 1, -1, 1, 0, 1, 0, 1, -1, -1, 1, 1, 0, -1], [-1, 1, 1, 0, 1, 1, -1, 0, 1, -1, -1, -1, 1, -1], [0, -1, -1, 1, 0, -1, -1, -1, 0, 1, -1, 0, 1, -1], [0, 0, -1, 1, 1, 0, -1, 0, 0, -1, 0, 0, 0, 1], [-1, -1, 0, -1, -1, 1, 0, 0, 1, 1, 0, 1, -1, 0], [1, 1, 0, -1, -1, -1, 1, -1, 1, 1, 1, 0, 1, 0], [-1, 1, -1, 0, 1, -1, -1, 0, 0, 1, -1, 0, -1, 0], [1, 0, 0, 0, 1, -1, 0, 0, 1, 0, 0, 1, 1, 1], [0, 0, -1, 1, 0, 1, 1, 0, -1, 1, -1, 1, 1, -1], [-1, -1, -1, 1, -1, -1, -1, 1, 0, 0, 0, 1, -1, -1]]
print(hafnian(M))
83
Tugas
Anda harus menulis kode itu, diberikan 2n
oleh 2n
matriks, menampilkan Hafniannya.
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. Saya akan menguji kode Anda dalam matriks yang dipilih secara acak dengan elemen. dipilih dari {-1, 0, 1}. Tujuan pengujian seperti ini adalah untuk mengurangi peluang Hafnian akan menjadi nilai yang sangat besar.
Idealnya kode Anda akan dapat dibaca dalam matriks persis seperti yang saya miliki dalam contoh-contoh dalam pertanyaan ini langsung dari standar masuk. Itu adalah input akan terlihat seperti [[1,-1],[-1,-1]]
misalnya. Jika Anda ingin menggunakan format input lain, tanyakan dan saya akan melakukan yang terbaik untuk mengakomodasi.
Skor dan dasi
Saya akan menguji kode Anda pada matriks acak dengan 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 itu adalah dalam 1 detik satu sama lain maka itu adalah yang diposting pertama.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa dan pustaka yang tersedia yang Anda suka tetapi tidak ada fungsi yang sudah ada sebelumnya untuk menghitung Hafnian. Jika memungkinkan, alangkah baiknya untuk dapat menjalankan kode Anda jadi harap sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di Linux jika memungkinkan. `
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.
Panggil jawaban dalam lebih banyak bahasa
Akan sangat bagus untuk mendapatkan jawaban dalam bahasa pemrograman super cepat favorit Anda. Untuk memulai, bagaimana dengan fortran , nim dan rust ?
Papan peringkat
- 52 oleh miles menggunakan C ++ . 30 detik.
- 50 oleh ngn menggunakan C . 50 detik.
- 46 oleh Christian Sievers menggunakan Haskell . 40 detik.
- 40 oleh miles menggunakan Python 2 + pypy . 41 detik.
- 34 oleh ngn menggunakan Python 3 + pypy . 29 detik.
- 28 oleh Dennis menggunakan Python 3 . 35 detik. (Pypy lebih lambat)
Jawaban:
Haskell
Ini mengimplementasikan variasi Algoritma 2 dari Andreas Björklund: Menghitung Pencocokan Sempurna secepat Ryser .
Kompilasi menggunakan
ghc
dengan opsi waktu kompilasi-O3 -threaded
dan gunakan opsi run time+RTS -N
untuk paralelisasi. Mengambil input dari stdin.sumber
parallel
danvector
harus diinstal?Python 3
Cobalah online!
sumber
C ++ (gcc)
Cobalah online! (13d untuk n = 24)
Berdasarkan implementasi Python yang lebih cepat di posting saya yang lain. Edit baris kedua ke
#define S 3
pada mesin 8-core Anda dan kompilasi dengang++ -pthread -march=native -O2 -ftree-vectorize
.Membagi pekerjaan menjadi dua, jadi nilai
S
seharusnyalog2(#threads)
. Jenis dapat dengan mudah diubah antaraint
,long
,float
, dandouble
dengan memodifikasi nilai#define TYPE
.sumber
tr -d \ < matrix52.txt > matrix52s.txt
Python 3
Ini menghitung haf (A) sebagai jumlah memoised (A [i] [j] * haf (A tanpa baris dan cols i dan j)).
sumber
C
Impl lain dari makalah Andreas Björklund , yang jauh lebih mudah dipahami jika Anda juga melihat kode Haskell Christian Sievers . Untuk beberapa level pertama rekursi, ia mendistribusikan putaran-robin di atas CPU yang tersedia. Level terakhir dari rekursi, yang merupakan setengah dari doa, dioptimalkan dengan tangan.
Mengkompilasi dengan:
gcc -O3 -pthread -march=native
; terima kasih @Dennis untuk 2x percepatann = 24 dalam 24 detik pada TIO
Algoritma:
Matriks, yang simetris, disimpan dalam bentuk segitiga kiri bawah. Indeks segitiga
i,j
sesuai dengan indeks linier diT(max(i,j))+min(i,j)
manaT
merupakan makro untuki*(i-1)/2
. Elemen matriks adalah polinomial derajatn
. Polinomial direpresentasikan sebagai larik koefisien yang diurutkan dari suku konstan (p[0]
) ke koefisien x n (p[n]
). Nilai matriks -1,0,1 awal dikonversi terlebih dahulu ke const polinomials.Kami melakukan langkah rekursif dengan dua argumen: setengah-matriks (yaitu segitiga)
a
dari polinomial dan polinomial terpisahp
(disebut beta dalam makalah). Kami mengurangim
masalah ukuran (awalnyam=2*n
) secara rekursif menjadi dua masalah ukuranm-2
dan mengembalikan perbedaan hafnianya. Salah satunya adalah menggunakan yang samaa
tanpa dua baris terakhir, dan yang samap
. Lain adalah menggunakan segitigab[i][j] = a[i][j] + shmul(a[m-1][i],a[m-2][j]) + shmul(a[m-1][j],a[m-2][i])
(di manashmul
adalah operasi shift-multiply pada polinomial - itu seperti produk polinom seperti biasa, juga dikalikan dengan variabel "x"; kekuatan yang lebih tinggi dari x ^ n diabaikan), dan polinomial yang terpisahq = p + shmul(p,a[m-1][m-2])
. Ketika rekursi hits ukuran-0a
, kita kembali koefisien utama p:p[n]
.Operasi shift-and-multiply diimplementasikan dalam fungsi
f(x,y,z)
. Itu memodifikasiz
di tempat. Secara longgar, itu benarz += shmul(x,y)
. Ini tampaknya menjadi bagian yang paling kritis terhadap kinerja.Setelah rekursi selesai, kita perlu memperbaiki tanda hasil dengan mengalikannya dengan (-1) n .
sumber
-march=native
akan membuat perbedaan besar di sini. Setidaknya pada TIO, hampir memotong waktu dinding menjadi dua.Python
Ini cukup mudah, implementasi referensi Algoritma 2 dari makalah yang disebutkan . Satu-satunya perubahan adalah hanya menjaga nilai B saat ini , menjatuhkan nilai β dengan hanya memperbarui g ketika i ∈ X , dan memotong perkalian polinomial dengan hanya menghitung nilai hingga derajat n .
Cobalah online!
Ini adalah versi yang lebih cepat dengan beberapa optimasi yang mudah.
Cobalah online!
Untuk tambahan kesenangan, berikut ini adalah implementasi referensi dalam J.
sumber
pmul
, gunakanfor j in range(n-i):
dan hindariif
j != k
denganj < k
. Ini menyalin submatrix dalam kasus lain yang dapat dihindari ketika kita menangani dan menghapus dua terakhir bukan dua baris dan kolom pertama. Dan ketika ia menghitung denganx={1,2,4}
dan kemudian denganx={1,2,4,6}
itu mengulangi perhitungannya hinggai=5
. Saya mengganti struktur dua loop luar dengan looping pertamai
dan kemudian secara rekursif mengasumsikani in X
dani not in X
. - BTW, Mungkin menarik untuk melihat pertumbuhan waktu yang dibutuhkan dibandingkan dengan program lain yang lebih lambat.Oktaf
Ini pada dasarnya adalah salinan entri Dennis , tetapi dioptimalkan untuk Oktaf. Optimalisasi utama dilakukan dengan menggunakan matriks input penuh (dan transposinya) dan rekursi hanya menggunakan indeks matriks, daripada membuat matriks yang dikurangi.
Keuntungan utama adalah mengurangi penyalinan matriks. Sementara Oktaf tidak memiliki perbedaan antara pointer / referensi dan nilai-nilai dan secara fungsional hanya melewati nilai, itu cerita yang berbeda di belakang layar. Di sana, copy-on-write (lazy copy) digunakan. Itu berarti, untuk kode
a=1;b=a;b=b+1
, variabelb
hanya disalin ke lokasi baru di pernyataan terakhir, ketika diubah. Karenamatin
danmatransp
tidak pernah berubah, mereka tidak akan pernah dengan cara disalin. Kerugiannya adalah bahwa fungsi menghabiskan lebih banyak waktu menghitung indeks yang benar. Saya mungkin harus mencoba variasi yang berbeda antara indeks numerik dan logis untuk mengoptimalkan ini.Catatan penting: matriks input seharusnya
int32
! Simpan fungsi dalam file yang disebuthaf.m
Contoh skrip pengujian:
Saya sudah mencoba menggunakan TIO dan MATLAB (sebenarnya saya tidak pernah menginstal Octave). Saya membayangkan membuatnya bekerja sesederhana itu
sudo apt-get install octave
. Perintahoctave
akan memuat GUI Oktaf. Jika lebih rumit dari ini, saya akan menghapus jawaban ini sampai saya memberikan instruksi instalasi yang lebih rinci.sumber
Baru-baru ini Andreas Bjorklund, Brajesh Gupt dan saya sendiri menerbitkan algoritma baru untuk Hafnians dari matriks kompleks: https://arxiv.org/pdf/1805.12498.pdf . Untuk matriks n \ kali n, matriks akan berskala seperti n ^ 3 2 ^ {n / 2}.
Jika saya mengerti dengan benar, algoritma asli Andreas dari https://arxiv.org/pdf/1107.4466.pdf berskala seperti n ^ 4 2 ^ {n / 2} atau n ^ 3 log (n) 2 ^ {n / 2} jika Anda menggunakan transformasi Fourier untuk melakukan perkalian polinomial.
Algoritme kami secara khusus disoroti untuk matriks kompleks sehingga tidak akan secepat yang dikembangkan di sini untuk matriks {-1,0,1}. Namun saya ingin tahu apakah seseorang dapat menggunakan beberapa trik yang Anda gunakan untuk meningkatkan implementasi kami? Juga jika orang tertarik saya ingin melihat bagaimana implementasi mereka lakukan ketika diberi bilangan kompleks bukan bilangan bulat. Akhirnya, setiap komentar, kritik, perbaikan, bug, perbaikan disambut di repositori kami https://github.com/XanaduAI/hafnian/
Bersulang!
sumber