Teraz, gdy wszyscy rozwinęli swoją (często zadziwiającą) wiedzę na temat kodowania niskiego poziomu na temat tego, jak bardzo wolno jest Python? (Lub jak szybki jest twój język?) I jak powolny jest Python (część II)? nadszedł czas na wyzwanie, które również zwiększy Twoją zdolność do ulepszania algorytmu.
Poniższy kod oblicza listę długości 9. Pozycja i
na liście zlicza, ile razy co najmniej i
kolejne zera zostały znalezione podczas obliczania produktów wewnętrznych pomiędzy F
i S
. Aby to zrobić dokładnie, iteruje wszystkie możliwe listy F
długości n
i listy S
długości n+m-1
.
#!/usr/bin/python
import itertools
import operator
n=8
m=n+1
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n+m-1):
for F in itertools.product([-1,1], repeat = n):
i = 0
while (i<m and sum(map(operator.mul, F, S[i:i+n])) == 0):
leadingzerocounts[i] +=1
i+=1
print leadingzerocounts
Dane wyjściowe to
[4587520, 1254400, 347648, 95488, 27264, 9536, 4512, 2128, 1064]
Jeśli zwiększysz n do 10,12,14,16,18,20 za pomocą tego kodu, bardzo szybko staje się on zbyt wolny.
Zasady
- Wyzwanie polega na podaniu prawidłowej wartości wyjściowej dla możliwie największej wartości n. Istotne są tylko parzyste wartości n.
- Jeśli jest remis, wygrana trafia do najszybszego kodu na mojej maszynie dla największej liczby n.
- Zastrzegam sobie prawo do nie testowania kodu, który zajmuje więcej niż 10 minut.
- Możesz zmienić algorytm w dowolny sposób, o ile daje on poprawny wynik. W rzeczywistości będziesz musiał zmienić algorytm, aby zrobić porządny postęp w kierunku wygranej.
- Zwycięzca zostanie nagrodzony tydzień po ustaleniu pytania.
- Nagroda zostanie przyznana w odpowiednim czasie, co jest nieco później niż po przyznaniu zwycięzcy.
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.
Status .
- C . n = 12 w 49 sekund przez @Fors
- Java . n = 16 w 3:07 przez @PeterTaylor
- C ++ . n = 16 w 2:21 przez @ilmale
- Rpython . n = 22 w 3:11 przez @primo
- Java . n = 22 w 6:56 przez @PeterTaylor
- Nimrod . n = 24 w 9:28 sekund przez @ReimerBehrends
Zwycięzcą został Reimer Behrends z wpisem do Nimrod!
Jako sprawdzenie, wyjście dla n = 22 powinno wynosić [12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]
.
Konkurs się skończył, ale ... Oferuję 200 punktów za każde zgłoszenie, które wzrasta n o 2 (w ciągu 10 minut na moim komputerze), aż skończą mi się punkty. Ta oferta jest otwarta na zawsze .
źródło
Odpowiedzi:
Nimrod (N = 22)
Połącz z
(Nimrod można pobrać tutaj .)
Działa to w wyznaczonym czasie dla n = 20 (i dla n = 18, gdy używa się tylko jednego wątku, w tym drugim przypadku zajmuje to około 2 minut).
Algorytm wykorzystuje wyszukiwanie rekurencyjne, przycinając drzewo wyszukiwania za każdym razem, gdy napotkany zostanie niezerowy produkt wewnętrzny. Skróciliśmy również przestrzeń poszukiwań o połowę, obserwując to dla dowolnej pary wektorów
(F, -F)
musimy wziąć pod uwagę tylko jeden, ponieważ drugi wytwarza dokładnie takie same zestawy produktów wewnętrznych (S
również przez negację ).Wdrożenie wykorzystuje funkcje metaprogramowania Nimrod do rozwijania / wstawiania pierwszych kilku poziomów wyszukiwania rekurencyjnego. To oszczędza trochę czasu, gdy używasz gcc 4.8 i 4.9 jako backendu Nimroda i sporej kwoty na clang.
Przestrzeń wyszukiwania można dodatkowo przyciąć, obserwując, że musimy wziąć pod uwagę tylko wartości S, które różnią się parzystą liczbą pierwszych N pozycji od naszego wyboru F. Jednak złożoność lub potrzeby pamięciowe tego nie są skalowane dla dużych wartości z N, biorąc pod uwagę, że w takich przypadkach ciało pętli jest całkowicie pomijane.
Tabulowanie, gdzie iloczyn wewnętrzny jest zerowy, wydaje się być szybsze niż używanie jakiejkolwiek funkcji liczenia bitów w pętli. Najwyraźniej dostęp do stołu ma całkiem niezłą lokalizację.
Wygląda na to, że problem powinien być podatny na programowanie dynamiczne, biorąc pod uwagę, jak działa wyszukiwanie rekurencyjne, ale nie ma widocznego sposobu, aby to zrobić przy rozsądnej ilości pamięci.
Przykładowe wyniki:
N = 16:
N = 18:
N = 20:
Dla celów porównania algorytmu z innymi implementacjami, N = 16 zajmuje około 7,9 sekundy na mojej maszynie przy użyciu jednego wątku i 2,3 sekundy przy użyciu czterech rdzeni.
N = 22 zajmuje około 15 minut na 64-rdzeniowej maszynie z gcc 4.4.6, ponieważ backend Nimroda przepełnia 64-bitowe liczby całkowite
leadingZeros[0]
(być może nie podpisane, nie oglądałem).Aktualizacja: Znalazłem miejsce na kilka ulepszeń. Po pierwsze, dla danej wartości
F
możemy dokładnie wyliczyć pierwsze 16 pozycji odpowiednichS
wektorów, ponieważ muszą się one różnić dokładnie w różnychN/2
miejscach. Więc wstępnego wyliczenia listy bitowych wektorów wielkościN
, które mająN/2
bitów zestawu i korzystają z nich czerpać początkową częśćS
zF
.Po drugie, możemy ulepszyć wyszukiwanie rekurencyjne, obserwując, że zawsze znamy wartość
F[N]
(ponieważ MSB ma zero w reprezentacji bitowej). To pozwala nam dokładnie przewidzieć, w której gałęzi wracamy z produktu wewnętrznego. Chociaż faktycznie pozwoliłoby nam to przekształcić całe wyszukiwanie w pętlę rekurencyjną, tak naprawdę zdarza się, że dość spieszy przewidywanie gałęzi, więc utrzymujemy najwyższe poziomy w oryginalnej formie. Wciąż oszczędzamy trochę czasu, przede wszystkim poprzez zmniejszenie liczby rozgałęzień, które wykonujemy.W przypadku niektórych porządków kod używa teraz liczb całkowitych bez znaku i naprawia je w wersji 64-bitowej (na wypadek, gdyby ktoś chciał uruchomić to w architekturze 32-bitowej).
Ogólne przyspieszenie wynosi od współczynnika x3 do x4. N = 22 nadal potrzebuje więcej niż ośmiu rdzeni, aby uruchomić się w czasie krótszym niż 10 minut, ale na 64-rdzeniowej maszynie jest to teraz około czterech minut (z
numThreads
odpowiednio zwiększone). Nie sądzę jednak, aby było dużo więcej miejsca na ulepszenia bez innego algorytmu.N = 22:
Zaktualizowano ponownie, wykorzystując dalsze możliwe ograniczenia przestrzeni wyszukiwania. Działa za około 9:49 minut dla N = 22 na mojej maszynie quadcore.
Ostatnia aktualizacja (myślę). Lepsze klasy równoważności dla wyborów F, skrócenie czasu działania dla N = 22 do
3:19 minut57 sekund (edycja: przypadkowo uruchomiłem to z tylko jednym wątkiem) na mojej maszynie.Ta zmiana wykorzystuje fakt, że para wektorów wytwarza te same zera wiodące, jeśli jeden można przekształcić w drugi, obracając go. Niestety, dość krytyczna optymalizacja niskiego poziomu wymaga, aby górny bit F w reprezentacji bitów był zawsze taki sam, a podczas korzystania z tej równoważności nieco zmniejszył przestrzeń wyszukiwania i skrócił czas działania o około jedną czwartą w porównaniu z użyciem innej przestrzeni stanów redukcja F, narzut związany z eliminacją optymalizacji niskiego poziomu bardziej niż ją zrównoważył. Okazuje się jednak, że problem ten można wyeliminować również biorąc pod uwagę fakt, że F, które są odwrotne względem siebie, są również równoważne. Wprawdzie nieco to skomplikowało obliczenia klas równoważności, ale pozwoliło mi również zachować wspomnianą optymalizację niskiego poziomu, co doprowadziło do przyspieszenia około x3.
Jeszcze jedna aktualizacja do obsługi 128-bitowych liczb całkowitych dla zgromadzonych danych. Aby skompilować z 128 bitowych liczb całkowitych, trzeba
longint.nim
z tutaj i skompilować-d:use128bit
. N = 24 nadal zajmuje więcej niż 10 minut, ale dla zainteresowanych zainteresowałem się poniższym wynikiem.N = 24:
źródło
Java (
n=22
?)Myślę, że większość odpowiedzi jest lepsza niż
n=16
podobne podejście, chociaż różnią się symetriami, które wykorzystują i sposobem podziału zadania między wątkami.Wektory zdefiniowane w pytaniu można zastąpić ciągami bitów, a iloczyn wewnętrzny za pomocą XOR nakładającego się na siebie okna i sprawdzania, czy dokładnie
n/2
ustawione są bity (a tym samymn/2
bity usuwane). Istniejąn! / ((n/2)!)
(środkowy współczynnik dwumianowy) ciągin
bitów zn/2
zestawem bitów (które nazywam ciągami zrównoważonymi ), więc dla każdego z nichF
istnieje tak wiele okien,S
które dają zerowy iloczyn wewnętrzny. Ponadto czynność przesuwania sięS
wzdłuż jednego i sprawdzania, czy nadal możemy znaleźć przychodzący bit, który daje zerowy iloczyn wewnętrzny, odpowiada szukaniu krawędzi na wykresie, którego węzłami są okna, a których krawędzie łączą węzełu
z węzłem,v
którego pierwsze bity z .n-1
bity są ostatnien-1
u
Na przykład za pomocą
n=6
iF=001001
otrzymujemy ten wykres:i dla
F=001011
otrzymujemy ten wykres:Następnie musimy liczyć na siebie
i
od0
don
ilu ścieżki o długościi
istnieją zsumowanie na wykresach dla każdegoF
. Myślę, że większość z nas korzysta z wyszukiwania w głąb.Zauważ, że wykresy są rzadkie: łatwo jest udowodnić, że każdy węzeł ma stopień co najwyżej 1, a stopień co najwyżej jeden. Oznacza to również, że jedynymi możliwymi strukturami są proste łańcuchy i proste pętle. To trochę upraszcza DFS.
Wykorzystuję kilka symetrii: zbalansowane łańcuchy są zamknięte pod odwrotnym bitem (
~
operacja w wielu językach z rodziny ALGOL) i pod rotacją bitów, dzięki czemu możemy grupować razem wartości,F
które są powiązane tymi operacjami i wykonują tylko DFS pewnego razu.Na moim rdzeniu 2 2,5 GHz dostaję
Ponieważ komputer Lembika ma 8 rdzeni i wykonał mój poprzedni program jednowątkowy dwa razy szybciej niż mój, jestem optymistą, że uruchomi się on
n=22
w mniej niż 8 minut.źródło
do
Jest to w zasadzie tylko nieco zoptymalizowana implementacja algorytmu w pytaniu. Może zarządzać
n=12
w terminie.Uruchomienie testowe
n=12
, w tym kompilacja:Komentarz: Właśnie włączyłem swój mózg i użyłem prostych kombinacji kombinatoryki, aby obliczyć, że zawsze pierwsza wartość będzie
n! / ((n / 2)!)^2 * 2^(n + m - 1)
. Wydaje mi się, że musi istnieć całkowicie algebraiczne rozwiązanie tego problemu.źródło
Jawa,
n=16
Dla dowolnej wartości
F
istnieją\binom{n}{n/2}
wektory, które mają zerowy iloczyn wewnętrzny. Możemy więc zbudować wykres, którego wierzchołki to pasujące wektory i których krawędzie odpowiadają przesunięciuS
, a następnie wystarczy policzyć ścieżki długości don
wykresu.Nie próbowałem mikrooptymalizować tego poprzez zamianę operacji warunkowych na operacje bitowe, ale każda podwójna inkrementacja
n
zwiększa czas działania około 16-krotnie, więc nie zrobi to wystarczającej różnicy, chyba że jestem dość blisko progu. Na moim komputerze nie jestem.Na moim rdzeniu 2 2,5 GHz dostaję
źródło
f
i początkowe wierzchołki, iteruj wszystkief_xor_g
z dokładnien/2
ustawionymi bitami. Dla każdego z nich powtórz wszystkof
i weźg = f ^ f_xor_g
.RPython, N = 22 ~ 3: 23
Wielowątkowy, wykorzystujący rekurencyjne zejście bez stosu. Program akceptuje dwa argumenty wiersza poleceń: N i liczbę wątków roboczych.
Kompilować
Stwórz lokalny klon repozytorium PyPy przy użyciu mercurial, git lub cokolwiek innego. Wpisz następującą inkantację (zakładając, że powyższy skrypt ma nazwę
convolution-high.py
):gdzie
%PYPY_REPO%
reprezentuje zmienną środowiskową wskazującą na właśnie sklonowane repozytorium. Kompilacja zajmuje około minuty.Przykładowe czasy
N = 16, 4 wątki:
N = 18, 4 wątki:
N = 20, 4 wątki:
N = 22, 4 wątki:
źródło
Python 3.3, N = 20, 3,5 min
Oświadczenie: moim zamiarem NIE jest publikowanie tego jako mojej własnej odpowiedzi, ponieważ algorytm, którego używam, jest tylko bezwstydnym portem z rozwiązania RPython primo . Moim celem tutaj jest pokazanie, co możesz zrobić w Pythonie, jeśli połączysz magię Numpy i Numba modułów .
Numba wyjaśnił w skrócie:
Aktualizacja 1 : Zauważyłem po rzuceniu liczbami, że możemy po prostu całkowicie pominąć niektóre z nich. Więc teraz maxf staje się (1 << n) // 2, a maxs staje się maxf 2 **. Przyspieszy to nieco proces. n = 16 zajmuje teraz tylko ~ 48 s (w porównaniu z 4,5 min). Mam też inny pomysł, który spróbuję sprawdzić, czy uda mi się przyspieszyć.
Aktualizacja 2: Zmieniony algorytm (rozwiązanie primo). Chociaż mój port nie obsługuje jeszcze wielowątkowości, dodanie go jest dość proste. Możliwe jest nawet wydanie CPython GIL przy użyciu Numba i ctypów. To rozwiązanie działa jednak bardzo szybko również na jednym rdzeniu!
I w końcu:
Działa to na moim komputerze w 212688ms lub ~ 3.5min.
źródło
C++ N=16
I'm testing on a EEEPC with an atom.. my time don't make a lot of sense. :D
The atom solve n=14 in 34 seconds. And n=16 in 20 minutes. I want to test n = 16 on OP pc. I'm optimistic.
The ideas is that every time we find a solution for a given F we have found 2^i solution because we can change the lower part of S leading to the same result.
to compile:
gcc 26459.cpp -std=c++11 -O3 -march=native -fstrict-aliasing -ftree-vectorize -Wall -pedantic -o 26459
źródło
JAVASCRIPT n:12
In my computer it took 231.242 seconds. In the Demo I'm using webworkers to prevent freezing the browser. This sure can be further improved with parallel workers. I know JS don't stand a chance in this challenge but I did it for fun!
Click to run the online Demo
źródło
n=22
[235388928,86292480,19031048,5020640,1657928,783920,545408,481256,463832,460256,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744]
i.imgur.com/FIJa2Ch.pngFortran: n=12
I just made a quick'n'dirty version in Fortran, no optimizations except OpenMP. It should squeeze in at just below 10 minutes for n=12 on the OPs machine, it takes 10:39 on my machine which is sligthly slower.
64-bit integers have a negative performance impact indeed; guess I would have to rethink the whole algorithm for this to be much faster. Don't know if I'm going to bother, I think I'll rather spend some time thinking up a good challenge that's more to my own tastes. If anyone else wants to take this and run with it, go ahead :)
źródło
Lua: n = 16
Disclaimer: my intention is NOT to post this as my own answer, since the algorithm I'm using is shamelessly stolen from Anna Jokela's clever answer. which was shamelessly stolen from ilmale's clever answer.
Besides, it's not even valid - it has inaccuracies caused by floating point numbers (it would be better if Lua would support 64-bit integers). However, I'm still uploading it, just to show how fast this solution is. It's a dynamic programming language, and yet I can calculate n = 16 in reasonable time (1 minute on 800MHz CPU).
Run with LuaJIT, standard interpreter is too slow.
źródło
long long
instead ofdouble
with a compilation setting), not LuaJIT.