Wyzwanie polega na napisaniu najszybszego możliwego kodu do obliczenia stałej macierzy .
Stała n
-by- n
matrix A
= ( a
i,j
) jest zdefiniowana jako
Tutaj S_n
reprezentuje zestaw wszystkich permutacji [1, n]
.
Jako przykład (z wiki):
W tym pytaniu macierze są kwadratowe i mają tylko wartości -1
i 1
na nich.
Przykłady
Wkład:
[[ 1 -1 -1 1]
[-1 -1 -1 1]
[-1 1 -1 1]
[ 1 -1 -1 1]]
Stały:
-4
Wkład:
[[-1 -1 -1 -1]
[-1 1 -1 -1]
[ 1 -1 -1 -1]
[ 1 -1 1 -1]]
Stały:
0
Wkład:
[[ 1 -1 1 -1 -1 -1 -1 -1]
[-1 -1 1 1 -1 1 1 -1]
[ 1 -1 -1 -1 -1 1 1 1]
[-1 -1 -1 1 -1 1 1 1]
[ 1 -1 -1 1 1 1 1 -1]
[-1 1 -1 1 -1 1 1 -1]
[ 1 -1 1 -1 1 -1 1 -1]
[-1 -1 1 -1 1 1 1 1]]
Stały:
192
Wkład:
[[1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1],
[1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, 1, -1],
[-1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, -1],
[-1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, -1],
[-1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1],
[1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1],
[1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1],
[1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
[1, -1, -1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1],
[-1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1],
[-1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1],
[1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1],
[-1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, -1, 1],
[1, 1, -1, -1, -1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1],
[1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
[1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1],
[-1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1],
[1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1],
[1, 1, 1, -1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1],
[-1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1]]
Stały:
1021509632
Zadanie
Powinieneś napisać kod, który podany n
przez n
macierz, wyprowadza swój stały.
Ponieważ będę musiał przetestować kod, pomocne byłoby podanie prostego sposobu na przekazanie macierzy jako danych wejściowych do kodu, na przykład poprzez czytanie ze standardowego w.
Ostrzegamy, że permanent może być duży (skrajna macierz wszystkich 1s).
Wyniki i krawaty
Przetestuję twój kod na losowych matrycach + -1 o coraz większym rozmiarze i zatrzymam się, gdy twój kod po raz pierwszy zajmie więcej niż 1 minutę na moim komputerze. Macierze oceny będą spójne dla wszystkich wniosków, aby zapewnić uczciwość.
Jeśli dwie osoby otrzymają ten sam wynik, zwycięzcą jest ta, która jest najszybsza dla tej wartości n
. Jeśli są one w odległości 1 sekundy od siebie, to jest to pierwszy.
Języki i biblioteki
Możesz użyć dowolnego dostępnego języka i bibliotek, które ci się podobają, ale nie ma wcześniejszej funkcji do obliczenia stałej. Tam, gdzie jest to wykonalne, dobrze byłoby móc uruchomić kod, więc proszę podać pełne wyjaśnienie, jak uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe.
Referencyjne implementacje
Jest już pytanie o kodegolfa z dużą ilością kodu w różnych językach do obliczania stałej dla małych matryc. Zarówno Mathematica, jak i Maple mają również stałe implementacje, jeśli masz do nich dostęp.
Moja maszyna Czasy będą działać na moim 64-bitowym komputerze. Jest to standardowa instalacja ubuntu z 8 GB pamięci RAM, ośmiordzeniowym procesorem AMD FX-8350 i Radeon HD 4250. Oznacza to również, że muszę mieć możliwość uruchomienia kodu.
Informacje niskiego poziomu o mojej maszynie
cat /proc/cpuinfo/|grep flags
daje
flagi: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good nopl fqqm_sfs_sf_sfs_sfs 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_core perfctr_nb cpb hw_psts vmcall vmmcall bmw
Zadam ściśle powiązane, wielojęzyczne pytanie, które nie cierpi z powodu dużego problemu Int, więc miłośnicy Scali , Nima , Julii , Rusty i Basha mogą również pochwalić się swoimi językami.
Tablica liderów
- n = 33 (45 sekund. 64 sekundy dla n = 34). Ton Hospel w C ++ z g ++ 5.4.0.
- n = 32 (32 sekundy). Dennis w C z gcc 5.4.0 przy użyciu flag gcc Ton Hospel.
- n = 31 (54 sekund). Christian Sievers w Haskell
- n = 31 (60 sekund). primo w rpython
- n = 30 (26 sekund). ezrast in Rust
- n = 28 (49 sekund). xnor z Python + pypy 5.4.1
- n = 22 (25 sekund). Shebang z Python + pypy 5.4.1
Uwaga . W praktyce terminy Dennisa i Tona Hospela są bardzo różne z tajemniczych powodów. Na przykład wydają się być szybsze po załadowaniu przeglądarki internetowej! Podane czasy są najszybsze we wszystkich testach, które przeprowadziłem.
źródło
Odpowiedzi:
gcc C ++ n ≈ 36 (57 sekund w moim systemie)
Używa formuły Glynn z szarym kodem do aktualizacji, jeśli wszystkie sumy kolumn są parzyste, w przeciwnym razie używa metody Rysera. Gwintowane i wektoryzowane. Zoptymalizowany dla AVX, więc nie oczekuj dużo na starszych procesorach. Nie przejmuj
n>=35
się matrycą zawierającą tylko +1, nawet jeśli twój system jest wystarczająco szybki, ponieważ podpisany 128-bitowy akumulator się przepełni. W przypadku macierzy losowych prawdopodobnie nie trafisz do przepełnienia. Dlan>=37
wewnętrznych mnożników zacznie się przepełniać dla całej1/-1
macierzy. Dlatego używaj tego programu tylko don<=36
.Po prostu podaj elementy macierzy na STDIN oddzielone dowolnym rodzajem białych znaków
permanent.cpp
:źródło
2 << (n-1)
na końcu, co oznacza, że mój akumulator int128 przelał się znacznie przed tym punktem.C99, n ≈ 33 (35 sekund)
Wejście jest obecnie nieco uciążliwe; jest pobierany z wierszami jako argumentami wiersza poleceń, gdzie każdy wpis jest reprezentowany przez jego znak, tj. + oznacza 1, a - oznacza -1 .
Testowe uruchomienie
źródło
popcnt
). Jeśli to pozwoli zaoszczędzić czas, następną dużą przeszkodą jest liczba całkowita. W przypadku losowo generowanych macierzy wartość stała jest stosunkowo niewielka. Jeśli znajdę prosty sposób na obliczenie granicy przed wykonaniem rzeczywistych obliczeń, mogę zawrzeć całość w dużej warunku.Python 2, n ≈ 28
Używa formuły Glynn z szarym kodem do aktualizacji.
n=23
Za chwilę podbiega do mojej maszyny. Z pewnością można to zrobić lepiej, stosując szybszy język i lepsze struktury danych. Nie korzysta to z tego, że macierz ma wartość ± 1.Implementacja formuły Ryser jest bardzo podobna, sumując wszystkie wektory 0/1 współczynników zamiast ± 1 wektorów. To zajmuje około dwa razy więcej niż formuła Glynna, ponieważ dodaje ponad 2 ^ n takich wektorów, podczas gdy Glynn dzieli połowę tego, że używa symetrii tylko na te, które zaczynają się od
+1
.źródło
pypy
było to w stanie łatwo obliczyćn=28
w 44,6 sekundy. System Lembika wydaje się być dość podobny do mojego pod względem prędkości, jeśli nie trochę szybszy.Haskell, n = 31 (54s)
Z wieloma nieocenionymi wkładami @Angs: używaj
Vector
, używaj produktów zwarciowych, spójrz na nieparzyste n.Moje pierwsze próby paralelizmu w Haskell. W historii zmian można zobaczyć wiele kroków optymalizacji. O dziwo, były to głównie bardzo małe zmiany. Kod oparty jest na formule w sekcji „Formuła Balasubramanian-Bax / Franklin-Glynn” w artykule na temat obliczania stałego .
p
oblicza stałą. Nazywa się to, za pomocąpt
którego przekształca macierz w sposób, który jest zawsze poprawny, ale szczególnie przydatny w przypadku macierzy, które tu otrzymujemy.Kompiluj z
ghc -O2 -threaded -fllvm -feager-blackholing -o <name> <name>.hs
. Aby uruchomić z parallelisation, dać to runtime parametry jak poniżej:./<name> +RTS -N
. Dane wejściowe pochodzą ze standardowego wejścia z zagnieżdżonymi listami oddzielonymi przecinkami w nawiasach, tak[[1,2],[3,4]]
jak w poprzednim przykładzie (znaki nowej linii są dozwolone wszędzie).źródło
Data.Vector
. Zmiany wyłączeniem zmienione rodzaje funkcji: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
). To dało mi tylko ~ 10%. Zmieniono kod, tak aby wektory zawierały tylkoInt
s. W porządku, ponieważ są one dodawane, duże liczby pochodzą z mnożenia. To było ~ 20%. Próbowałem tej samej zmiany ze starym kodem, ale wtedy to spowolniło. Próbowałem jeszcze raz, ponieważ pozwala to na użycie wektorów bez pudełka , co bardzo pomogło!x p _ m _ = m * (sum $ V.foldM' (\a b -> if b==0 then Nothing else Just $ a*fromIntegral b) 1 p)
- produkt jako monadic fold, gdzie 0 to szczególny przypadek. Wydaje się być korzystny częściej niż nie.Transversable
(widzę, że twojaproduct
niezmienność nie była błędem ...) dla ghc np. Ze stabilnej wersji Debiana. Wykorzystuje formę danych wejściowych, ale wydaje się to w porządku: nie polegamy na tym, a jedynie optymalizujemy. Sprawia, że czas jest znacznie bardziej ekscytujący: moja losowa matryca 30x30 jest nieco szybsza niż 29x29, ale potem 31x31 zajmuje 4x czas. - Wydaje się, że INLINE nie działa dla mnie. AFAIK jest ignorowany dla funkcji rekurencyjnych.product
ale zapomniałem. Wydaje się, że tylko parzyste długości mają zerap
, więc dla nieparzystej długości powinniśmy używać zwykłego produktu zamiast zwarcia, aby uzyskać to, co najlepsze z obu światów.Rdza + extprim
Ten prosty Ryser z implementacją Graya zajmuje około
6590 sekund, aby uruchomić n = 31 na moim laptopie.Wyobrażam sobie, że twoja maszyna dotrze tam znacznie poniżej 60 lat.Używam extprim 1.1.1 dlai128
.Nigdy nie korzystałem z Rust i nie mam pojęcia, co robię. Żadnych opcji kompilatora innych niż cokolwiek
cargo build --release
. Komentarze / sugestie / optymalizacje są mile widziane.Inwokacja jest identyczna z programem Dennisa.
źródło
git clone https://gitlab.com/ezrast/permanent.git; cd permanent; cargo build --release
jeśli chcesz mieć taką samą konfigurację jak ja. Ładunek poradzi sobie z zależnościami. Binary wchodzitarget/release
.Mathematica, n ≈ 20
Za pomocą
Timing
polecenia macierz 20x20 wymaga około 48 sekund w moim systemie. Nie jest to tak wydajne jak inne, ponieważ opiera się na fakcie, że stałe można znaleźć jako współczynnik iloczynu wielomianów z każdego rzędu macierzy. Efektywne mnożenie wielomianowe odbywa się poprzez tworzenie list współczynników i wykonywanie splotów za pomocąListConvolve
. Wymaga to około O (2 n n 2 ) założenia, że splot jest wykonywany przy użyciu szybkiej transformaty Fouriera lub podobnej, która wymaga czasu O ( n log n ).źródło
Python 2, n = 22 [Odwołanie]
Jest to implementacja „referencyjna”, którą wczoraj podzieliłem z Lembikiem, brakuje jej
n=23
wykonania o kilka sekund na jego komputerze, na mojej maszynie robi to w około 52 sekund. Aby osiągnąć te prędkości, musisz uruchomić to przez PyPy.Pierwsza funkcja oblicza stałą podobnie do sposobu wyznaczania wyznacznika, przechodząc przez każdą podwielokrotkę, aż pozostanie 2x2, do którego można zastosować podstawową regułę. Jest niesamowicie wolny .
Druga funkcja to ta implementująca funkcję Rysera (drugie równanie wymienione w Wikipedii). Zestaw
S
jest zasadniczo zestawem liczb{1,...,n}
(zmiennyms_list
w kodzie).źródło
RPython 5.4.1, n ≈ 32 (37 sekund)
Aby skompilować, pobierz najnowsze źródło PyPy i wykonaj następujące czynności:
Wynikowy plik wykonywalny zostanie nazwany
matrix-permanent-c
lub podobny w bieżącym katalogu roboczym.Począwszy od PyPy 5.0, prymitywy wątków RPython są znacznie mniej prymitywne niż kiedyś. Nowo odrodzone wątki wymagają GIL, który jest mniej lub bardziej bezużyteczny w obliczeniach równoległych. Użyłem
fork
zamiast tego, więc może nie działać zgodnie z oczekiwaniami w systemie Windows,chociaż nie przetestowałem,aby się nie skompilować (unresolved external symbol _fork
).Plik wykonywalny akceptuje maksymalnie dwa parametry wiersza poleceń. Pierwszy to liczba wątków, drugi opcjonalny parametr to
n
. Jeśli zostanie podana, zostanie wygenerowana losowa macierz, w przeciwnym razie zostanie odczytana ze standardowego wejścia. Każdy wiersz musi być oddzielony znakiem nowej linii (bez końcowego znaku nowej linii), a każda przestrzeń wartości oddzielona. Trzeci przykładowy przykład będzie podany jako:Przykładowe użycie
metoda
Użyłem formuły Balasubramanian-Bax / Franklin-Glynn ze złożonością czasową O (2 n n) . Jednak zamiast iterować δ w szarej kolejności kodu, zamiast tego zamieniłem mnożenie przez wektor-wiersz pojedynczą operacją xor (mapowanie (1, -1) → (0, 1)). Sumę wektorową można również znaleźć w jednej operacji, biorąc n minus dwukrotność liczby popcount.
źródło
Rakieta 84 bajtów
Poniższa prosta funkcja działa dla mniejszych matryc, ale zawiesza się na mojej maszynie dla większych matryc:
Nie golfowany:
Kod można łatwo zmodyfikować dla nierównej liczby wierszy i kolumn.
Testowanie:
Wydajność:
Jak wspomniałem powyżej, testowanie polega na testowaniu następujących elementów:
źródło