To wyzwanie jest częściowo wyzwaniem algorytmicznym, wymaga pewnej matematyki, a częściowo jest po prostu najszybszym wyzwaniem w kodzie.
Dla pewnej dodatniej liczby całkowitej n
rozważ jednolicie losowy ciąg 1
si i 0
s długości n
i wywołaj go A
. Teraz rozważ także drugi losowo wybrany losowo ciąg długości, n
którego wartości są -1
, 0,
lub 1
wywołaj go B_pre
. Teraz niech B
będzie B_pre
+ B_pre
. To jest B_pre
połączone z samym sobą.
Rozważmy teraz wewnętrzną produkt A
i B[j,...,j+n-1]
i nazwać Z_j
i indeks z 1
.
Zadanie
Dane wyjściowe powinny być listą n+1
ułamków. i
Th termin na wyjściu powinien być dokładny prawdopodobieństwo, że wszystko z pierwszych i
terminów Z_j
z j <= i
równym 0
.
Wynik
Największy, n
dla którego Twój kod zapewnia prawidłowe wyjście w mniej niż 10 minut na moim komputerze.
Tie Breaker
Jeśli dwie odpowiedzi mają ten sam wynik, wygrywa ten, który przesłał pierwszy.
W (bardzo, bardzo) mało prawdopodobnym przypadku, gdy ktoś znajdzie sposób na uzyskanie nieograniczonej liczby punktów, zostanie zaakceptowany pierwszy ważny dowód takiego rozwiązania.
Wskazówka
Nie próbuj rozwiązywać tego problemu matematycznie, jest to zbyt trudne. Moim zdaniem najlepszym sposobem jest powrót do podstawowych definicji prawdopodobieństwa z liceum i znalezienie sprytnych sposobów, aby kod wykonał wyczerpujące wyliczenie możliwości.
Języki i biblioteki
Możesz używać dowolnego języka, który ma swobodnie dostępny kompilator / tłumacz / etc. dla systemu Linux i dowolnych bibliotek, które są również bezpłatnie dostępne dla systemu Linux.
Moja maszyna Czasy zostaną uruchomione na moim komputerze. Jest to standardowa instalacja ubuntu na ośmiordzeniowym procesorze AMD FX-8350. Oznacza to również, że muszę być w stanie uruchomić Twój kod. W związku z tym korzystaj tylko z łatwo dostępnego bezpłatnego oprogramowania i dołącz pełne instrukcje, jak skompilować i uruchomić kod.
Niektóre wyjścia testowe. Rozważ tylko pierwsze wyjście dla każdego n
. Wtedy to i=1
. Dla n
od 1 do 13 powinny być.
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
Możesz również znaleźć ogólną formułę i=1
na http://oeis.org/A081671 .
Tabela liderów (w podziale na język)
- n = 15. Python + równoległy python + pypy w 1min49s przez Jakube
- n = 17. C ++ w 3min37s autorstwa Keitha Randalla
- n = 16. C ++ w 2min38s autorstwa kuroi neko
źródło
Odpowiedzi:
C ++, n = 18 w 9 minut na 8 wątków
(Daj mi znać, jeśli na twoim komputerze będzie to mniej niż 10 minut).
Korzystam z kilku form symetrii w tablicy B. Są one cykliczne (przesunięcie o jedną pozycję), odwrócenie (odwróć kolejność elementów) i znak (weź minus każdego elementu). Najpierw obliczam listę Bs, którą musimy wypróbować i ich wagę. Następnie każdy B jest uruchamiany przez szybką procedurę (przy użyciu instrukcji bitcount) dla wszystkich 2 ^ n wartości A.
Oto wynik dla n == 18:
Skompiluj poniższy program za pomocą
g++ --std=c++11 -O3 -mpopcnt dot.cc
źródło
-pthread
znowu pamiętać . Wchodzęn=17
na moją maszynę.Python 2 używa pypy i pp: n = 15 w 3 minuty
Również zwykła brutalna siła. Ciekawe, że mam prawie taką samą prędkość jak kuroi neko z C ++. Mój kod może dotrzeć
n = 12
w ciągu około 5 minut. I uruchamiam go tylko na jednym wirtualnym rdzeniu.edycja: Zmniejsz przestrzeń wyszukiwania o współczynnik
n
Zauważyłem, że cyklicznie wektor
A*
zA
produkuje te same numery jak prawdopodobieństw (te same numery) jako oryginalnego wektoraA
kiedy iteracyjnegoB
. Np Wektor(1, 1, 0, 1, 0, 0)
ma takie same prawdopodobieństwa jak każdy z wektorów(1, 0, 1, 0, 0, 1)
,(0, 1, 0, 0, 1, 1)
,(1, 0, 0, 1, 1, 0)
,(0, 0, 1, 1, 0, 1)
i(0, 1, 1, 0, 1, 0)
przy wyborze losowymB
. Dlatego nie muszę iterować każdego z tych 6 wektorów, ale tylko około 1 i zastąpićcount[i] += 1
jecount[i] += cycle_number
.Zmniejsza to złożoność od
Theta(n) = 6^n
doTheta(n) = 6^n / n
. Dlategon = 13
jest to około 13 razy szybsze niż moja poprzednia wersja. Oblicza sięn = 13
w ciągu około 2 minut i 20 sekund. Bon = 14
wciąż jest trochę za wolno. Zajmuje to około 13 minut.edycja 2: Programowanie wielordzeniowe
Niezbyt zadowolony z następnej poprawy. Postanowiłem także spróbować uruchomić mój program na wielu rdzeniach. Na moich rdzeniach 2 + 2 mogę teraz obliczyć
n = 14
w około 7 minut. Tylko współczynnik poprawy 2.Kod jest dostępny w tym repozytorium github: Link . Wielordzeniowe programowanie sprawia, że jest trochę brzydkie.
edycja 3: Zmniejszenie przestrzeni wyszukiwania
A
wektorów iB
wektorówZauważyłem tę samą lustrzaną symetrię wektorów,
A
co kuroi neko. Nadal nie jestem pewien, dlaczego to działa (i czy działa dla każdegon
).Zmniejszenie przestrzeni wyszukiwania
B
wektorów jest nieco sprytniejsze. Generację wektorów (itertools.product
) zastąpiłem własną funkcją. Zasadniczo zaczynam od pustej listy i umieszczam ją na stosie. Dopóki stos nie będzie pusty, usuwam listę, jeśli nie ma takiej samej długości jakn
, generuję 3 inne listy (dodając -1, 0, 1) i wypychając je na stos. Jeśli lista ma taką samą długośćn
, mogę ocenić sumy.Teraz, gdy sam generuję wektory, mogę je filtrować w zależności od tego, czy mogę osiągnąć sumę = 0, czy nie. Np. Jeśli mój wektor
A
jest(1, 1, 1, 0, 0)
i mój wektorB
wygląda(1, 1, ?, ?, ?)
, wiem, że nie mogę wypełnić?
wartości, więc toA*B = 0
. Więc nie muszę powtarzać tych wszystkich 6 wektorówB
formularza(1, 1, ?, ?, ?)
.Możemy to poprawić, jeśli zignorujemy wartości dla 1. Jak zauważono w pytaniu, wartościami
i = 1
są sekwencja A081671 . Istnieje wiele sposobów ich obliczania. Wybieram proste nawrotom:a(n) = (4*(2*n-1)*a(n-1) - 12*(n-1)*a(n-2)) / n
. Ponieważ możemy obliczyći = 1
w zasadzie w krótkim czasie, możemy filtrować więcej wektorówB
. NpA = (0, 1, 0, 1, 1)
aB = (1, -1, ?, ?, ?)
. Możemy zignorować wektory, gdzie pierwszy? = 1
, ponieważA * cycled(B) > 0
, dla wszystkich tych wektorów. Mam nadzieję, że możesz śledzić. To chyba nie najlepszy przykład.Dzięki temu mogę obliczyć
n = 15
w 6 minut.edycja 4:
Szybko wprowadzono świetny pomysł kuroi neko, który mówi, że
B
i-B
daje te same wyniki. Przyspieszenie x2. Wdrożenie to tylko szybki hack.n = 15
za 3 minuty.Kod:
Aby uzyskać pełny kod, odwiedź Github . Poniższy kod stanowi jedynie przedstawienie głównych funkcji. Pominąłem importowanie, programowanie wielordzeniowe, drukowanie wyników, ...
Stosowanie:
Musisz zainstalować pypy (dla Python 2 !!!). Równoległy moduł python nie jest portowany dla Pythona 3. Następnie musisz zainstalować równoległy moduł python pp-1.6.4.zip . Wyodrębnij go
cd
do folderu i zadzwońpypy setup.py install
.Następnie możesz wywołać mój program za pomocą
pypy you-do-the-math.py 15
Automatycznie określi liczbę procesorów. Po zakończeniu programu mogą pojawić się komunikaty o błędach, po prostu je zignoruj.
n = 16
powinno być możliwe na twoim komputerze.Wynik:
Uwagi i pomysły:
A & B
i policzyć 01 i 10 bloków. Cyklowanie można wykonać, przesuwając wektor i używając masek ... Właściwie to wszystko zaimplementowałem, można to znaleźć w niektórych moich starszych wersjach na Githubie. Okazało się jednak, że jest wolniejszy niż w przypadku list. Chyba pypy naprawdę optymalizuje operacje na listach.źródło
woolly bully - C ++ - zdecydowanie za wolny
Cóż, ponieważ lepszy programista przyjął implementację C ++, wzywam do tego.
Budowanie pliku wykonywalnego
Jest to samodzielne źródło C ++ 11, które kompiluje się bez ostrzeżeń i działa płynnie na:
Jeśli kompilujesz za pomocą g ++, użyj: g ++ -O3 -pthread -std = c ++ 11
zapomnienie o
-pthread
utworzy miły i przyjazny zrzut pamięci .Optymalizacje
Ostatni człon Z jest równy pierwszemu (Bpre x A w obu przypadkach), więc dwa ostatnie wyniki są zawsze równe, co zrezygnuje z obliczenia ostatniej wartości Z.
Zysk jest pomijalny, ale kodowanie nic nie kosztuje, więc równie dobrze możesz go użyć.
Jak odkrył Jakube, wszystkie wartości cykliczne danego wektora A dają takie same prawdopodobieństwa.
Można je obliczyć za pomocą pojedynczego wystąpienia A i pomnożyć wynik przez liczbę możliwych obrotów. Grupy rotacji można łatwo wstępnie obliczyć w nieistotnym czasie, więc jest to ogromny wzrost prędkości netto.
Ponieważ liczba permutacji wektora długości n wynosi n-1, złożoność spada z o (6 n ) do o (6 n / (n-1)), zasadniczo idąc krok dalej w tym samym czasie obliczeń.
Wydaje się, że pary wzorów symetrycznych również generują takie same prawdopodobieństwa. Na przykład 100101 i 101001.
Nie mam matematycznego dowodu na to, ale intuicyjnie, gdy zostaną przedstawione wszystkie możliwe wzorce B, każda symetryczna wartość A zostanie spleciona z odpowiednią symetryczną wartością B dla tego samego wyniku globalnego.
Pozwala to na zgrupowanie kilku wektorów A, w celu około 30% zmniejszenia liczby grup A.
ŹLE
Z jakiegoś na wpół tajemniczego powodu wszystkie wzory zawierające tylko jeden lub dwa bity dają ten sam rezultat. Nie reprezentuje to tak wielu odrębnych grup, ale nadal można je łączyć praktycznie bez żadnych kosztów.Wektory B i -B (B ze wszystkimi składnikami pomnożonymi przez -1) dają takie same prawdopodobieństwa.
(na przykład [1, 0, -1, 1] i [-1, 0, 1, -1]).
Z wyjątkiem wektora zerowego (wszystkie składniki równe 0), B i -B tworzą parę różnych wektorów.
Pozwala to zmniejszyć liczbę wartości B o połowę, biorąc pod uwagę tylko jedną z każdej pary i mnożąc jej udział przez 2, dodając znany globalny udział zerowy B do każdego prawdopodobieństwa tylko raz.
Jak to działa
Liczba wartości B jest ogromna (3 n ), więc ich wstępne obliczenie wymagałoby nieprzyzwoitej ilości pamięci, co spowolniłoby obliczenia i ostatecznie wyczerpało dostępną pamięć RAM.
Niestety nie mogłem znaleźć prostego sposobu wyliczenia połowy zestawu zoptymalizowanych wartości B, więc postanowiłem zakodować dedykowany generator.
Potężny generator B był świetną zabawą w kodowaniu, chociaż języki obsługujące mechanizmy wydajności pozwoliłyby na programowanie go w znacznie bardziej elegancki sposób.
To, co robi w skrócie, to „szkielet” wektora Bpre jako wektora binarnego, gdzie 1s reprezentują rzeczywiste wartości -1 lub +1.
Spośród wszystkich tych wartości potencjału + 1 / -1 pierwsza jest ustalona na +1 (w ten sposób wybierając jeden z możliwych wektorów B / -B), a wszystkie pozostałe możliwe kombinacje + 1 / -1 są wyliczone.
Wreszcie, prosty system kalibracji zapewnia, że każdy wątek roboczy przetworzy zakres wartości w przybliżeniu tego samego rozmiaru.
Wartości są silnie filtrowane w celu przegrupowania w odpowiednie części.
Odbywa się to w fazie obliczeń wstępnych, w których brutalna siła sprawdza wszystkie możliwe wartości.
Ta część ma pomijalny czas wykonania O (2 n ) i nie musi być optymalizowana (kod jest już wystarczająco nieczytelny, jak jest!).
Aby ocenić iloczyn wewnętrzny (który należy przetestować tylko w odniesieniu do zera), komponenty -1 i 1 B są zgrupowane w wektorach binarnych.
Iloczyn wewnętrzny jest zerowy, jeśli (i tylko wtedy) istnieje równa liczba + 1s i -1s wśród wartości B odpowiadających niezerowym wartościom A.
Można to obliczyć za pomocą prostych operacji maskowania i liczenia bitów,
std::bitset
co pomoże wygenerować dość wydajny kod liczby bitów bez konieczności uciekania się do brzydkich instrukcji wewnętrznych.Praca jest równo podzielona między rdzenie, z wymuszonym powinowactwem do procesora (co nieco pomaga, a przynajmniej tak mówią).
Przykładowy wynik
Występy
Wielowątkowość powinna na tym doskonale działać, chociaż tylko „prawdziwe” rdzenie w pełni przyczynią się do szybkości obliczeń. Mój procesor ma tylko 2 rdzenie dla 4 procesorów, a zysk w stosunku do wersji jednowątkowej wynosi „tylko” około 3,5.
Kompilatory
Początkowy problem z wielowątkowością doprowadził mnie do wniosku, że kompilatory GNU działały gorzej niż Microsoft.
Po dokładniejszych testach okazuje się, że g ++ po raz kolejny wygrywa, generując około 30% szybszy kod (ten sam współczynnik, który zauważyłem w dwóch innych projektach wymagających dużej mocy obliczeniowej).
W szczególności
std::bitset
biblioteka jest implementowana z dedykowanymi instrukcjami liczenia bitów przez g ++ 4.8, podczas gdy MSVC 2013 wykorzystuje tylko pętle konwencjonalnych przesunięć bitów.Jak można się było spodziewać, kompilacja w 32 lub 64 bitach nie ma znaczenia.
Dalsze udoskonalenia
Zauważyłem kilka grup A wytwarzających takie same prawdopodobieństwa po wszystkich operacjach redukcji, ale nie mogłem zidentyfikować wzoru, który pozwoliłby je zgrupować.
Oto pary, które zauważyłem dla n = 11:
źródło
terminate called after throwing an instance of 'std::system_error' what(): Unknown error -1 Aborted (core dumped)