To kontynuacja tego, jak bardzo wolno jest Python? (Lub jak szybki jest twój język?) .
Okazuje się, że dla mojego ostatniego pytania trochę za łatwo było uzyskać przyspieszenie x100. Dla tych, którzy lubili wyzwania, ale chcą czegoś trudniejszego, w którym mogliby naprawdę wykorzystać swoje umiejętności niskiego poziomu, oto część II. Wyzwanie polega na uzyskaniu przyspieszenia x100 dla następującego kodu python przetestowanego na moim komputerze.
Aby utrudnić, tym razem używam pypy. Obecny czas dla mnie to 1 minuta i 7 sekund przy użyciu pypy 2.2.1.
Zasady
- Pierwsza osoba, która prześle kod, który mogę uruchomić, jest poprawna i jest 100 razy szybsza na moim komputerze, otrzyma nagrodę w wysokości 50 punktów.
- Zwycięstwo przyznam najszybszemu kodowi po tygodniu.
import itertools
import operator
import random
n = 8
m = 8
iters = 1000
# creates an array of 0s with length m
# [0, 0, 0, 0, 0, 0, 0, 0]
leadingzerocounts = [0]*m
# itertools.product creates an array of all possible combinations of the
# args passed to it.
#
# Ex:
# itertools.product("ABCD", "xy") --> Ax Ay Bx By Cx Cy Dx Dy
# itertools.product("AB", repeat=5) --> [
# ('A', 'A', 'A', 'A', 'A'),
# ('A', 'A', 'A', 'A', 'B'),
# ('A', 'A', 'A', 'B', 'A'),
# ('A', 'A', 'A', 'B', 'B'),
# etc.
# ]
for S in itertools.product([-1,1], repeat = n+m-1):
for i in xrange(iters):
F = [random.choice([-1,0,0,1]) for j in xrange(n)]
# if the array is made up of only zeros keep recreating it until
# there is at least one nonzero value.
while not any(F):
F = [random.choice([-1,0,0,1]) for j in xrange(n)]
j = 0
while (j < m and sum(map(operator.mul, F, S[j:j+n])) == 0):
leadingzerocounts[j] +=1
j += 1
print leadingzerocounts
Dane wyjściowe powinny być podobne do
[6335185, 2526840, 1041967, 439735, 193391, 87083, 40635, 19694]
Musisz użyć losowego ziarna w kodzie, a dowolny generator liczb losowych, który jest wystarczająco dobry, aby dać odpowiedzi zbliżone do powyższego, zostanie zaakceptowany.
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.
Objaśnienie kodu
Ten kod iteruje wszystkie tablice S o długości n + m-1, które składają się na -1s i 1s. Dla każdej tablicy S próbkuje 1000 niezerowych losowych tablic F o długości n składającej się z -1,0 lub 1 z prawdopodobieństwem 1/4, 1/2, / 14 pobrania każdej wartości. Następnie oblicza iloczyn wewnętrzny między F i każdym oknem S o długości n, aż znajdzie niezerowy iloczyn wewnętrzny. Dodaje 1 do leadingzerocounts
każdej pozycji, w której znalazł zero wewnętrznego produktu.
Status
Perl . 2,7 razy spowolnienie przez @tobyink. (W porównaniu do pypy nie cpython.)
J . 39-krotne przyspieszenie o @Eelvex.
- C . 59 razy przyspieszyć @ace.
- Julia . 197 razy szybszy, nie wliczając czasu rozruchu o jeszcze jedną minutę. 8,5 razy szybsze, w tym czas rozruchu (w tym przypadku jest szybszy przy użyciu 4 procesorów niż 8).
- Fortran . 438 razy przyspieszenie o @ semi-extrinsic.
- Rpython . 258 razy przyspieszyć @primo.
- C ++ . 508 razy przyspieszenie @ilmale.
(Przestałem mierzyć czas nowych ulepszeń, ponieważ są one zbyt szybkie, a iteracja była za mała).
Zwrócono uwagę, że czasy poniżej jednej sekundy są niewiarygodne, a także niektóre języki mają koszty początkowe. Argument jest taki, że jeśli chcesz dołączyć, powinieneś również uwzględnić czas kompilacji C / C ++ itp. Oto czasy najszybszego kodu z liczbą iteracji zwiększoną do 100 000.
- Julia . 42 sekundy do @ jeszcze minuty.
- C ++ . 14 sekund autorstwa @GuySirton.
- Fortran . 14s @ semi-extrinsic.
- C ++ . 12s przez @ilmale.
- Rpython . 18s @primo.
- C ++ . 5s @Stefan.
Zwycięzcą jest ... Stefan!
Opublikowane wyzwanie uzupełniające. Jak wysoko możesz iść? (Wyzwanie kodowania + algorytmy) . Ten jest trudniejszy.
źródło
Odpowiedzi:
C ++ nieco magiczna
~ 16 ms wielowątkowy, 56 ms jednokierunkowy. ~ 4000 przyspieszenia.
(przyspieszenie oparte jest na kodzie wielowątkowym na moim i7-2820QM i 1 min 9 sekundach wymienionych w pytaniu. Ponieważ system OP ma gorszą wydajność pojedynczego wątku niż mój procesor, ale lepszą wydajność wielowątkową, spodziewam się, że ta liczba będzie dokładna)
Część wielowątkowa jest dość nieefektywna z powodu pojawiania się wątków. Prawdopodobnie mógłbym zrobić to lepiej, korzystając z mojej niestandardowej biblioteki zadań, ale ta zawiera błędy w systemach unixowych. Aby uzyskać wyjaśnienie i prawie identyczny kod bez wątków, odwiedź https://codegolf.stackexchange.com/a/26485/20965 .
edytować
Każdemu wątkowi nadałem swój własny RNG i skróciłem długość bitu do 32, co skróciło czas działania o kilka ms.
Przykładowe dane wyjściowe:
źródło
C ++
x150x450x530Zamiast tablicy użyłem bitów (i czarnej magii).
Dzięki @ace za szybszą losową funkcję.
Jak to działa: pierwsze 15 bitów liczby całkowitej
s
reprezentuje tablicęS[15]
; zera oznaczają -1, te zera +1. TablicaF
jest budowana w podobny sposób. Ale z dwoma bitami dla każdego symbolu.Przyczyna
S
iF
mają inną reprezentację muszę przeplatająS
się ze sobą, aby były porównywalne zF
.F
)F
)Teraz możemy po prostu użyć Carnota do obliczenia produktu wewnętrznego. Pamiętaj, że jedna zmienna może przyjmować tylko wartość 00 lub 11
0. 00 = 11 (-1 * -1 = +1)
0. 01 = 10 (-1 * 0 = 0)
0. 10 = 01 (-1 * 0 = 0)
0. 11 = 00 (-1 * +1 = -1)
1. 00 = 00 (+1 * -1 = -1)
1. 10 = 10 (+1 * 0 = 0)
1. 01 = 01 (+1 * 0 = 0)
1. 11 = 11 (+1 * +1 = +1)
Dla mnie wygląda to nie na xor. :)
Podsumowując, to tylko gra polegająca na zmianie i maskowaniu, nic naprawdę skomplikowanego.
Oto przykładowy wynik:
Program został skompilowany z:
na Fedorze 20 z gcc 4.8.2 CPU to i7 8core.
Prawdopodobnie uda mi się uzyskać kilka ms poprawiających parametry kompilatora.
Chociaż jest to czas rozwiązania OP na moim komputerze:
Edytować:
Po prostu dodając openmp i zmieniając kolejność for, mam zysk x3, co prowadzi do poprawy wydajności x450 względem kodu OP. : D W tym przypadku
leadingZero
tablica musi być atomowa. Losowe globalne ... są losowe, będą bardziej losowe.trzeba dodać
-fopenmp
do flagi kompilatoraEdycja: 2 Jako sugestia użytkownika 71404 Zmieniłem funkcje sumOnes i sumArray i teraz jest niesamowicie szybki.
Z Openmp jest wolniejszy, ponieważ atomika dodaje zbyt dużo narzutu.
Bez atomów jest jeszcze szybciej, ale mam błędny wynik.
2137992 1147218 619297 321243 155815 70946 32919 15579
Aby zrozumieć sumArray, należy wziąć pod uwagę, że 16-bitowa reprezentacja i tablica 8 liczb.
00 nie ma 1 i reprezentuje -1
01, a 10 ma jeden 1 i reprezentuje 0
11 ma dwa 1s i reprezentuje 1
Tak więc wbudowane liczenie liczby bitów ustawione na 1 [ http://en.wikipedia.org/wiki/ Hamming_weight] i do każdej grupy usuwamy 1. Cool.
sumOnes to tylko czarna magia.
Oto najnowsze flagi i kod kompilacji.
gcc -std = c ++ 11 -mfpmath = sse -O3 -flto -march = natywny -funroll-loop -Wall -lstdc ++
źródło
inline int32_t sumOnes(int32_t v) { /* 0xAAAA == 0b1010 1010 1010 1010 */ return !! (0xAAAA & (v ^ ~(v << 1))); } inline int32_t sumArray(int32_t v) { return __builtin_popcount(v) - 8; }
zostało to zasugerowane przez @ user71404Julia: 0,7 s, 120x szybciej
Jak pokazał user20768, prosty port kodu do Julii jest około dwa razy szybszy niż PyPy. Ale możemy zrobić o wiele więcej.
Możesz uruchomić to za pomocą
julia -p 8 -e 'require("golf.jl");main()'
(8 to liczba procesów, z którymi możesz się pobawić). W najnowszej wersji wstępnej Julii zajmuje to 0,7s vs. 1m22s dla PyPy.Jeśli masz wystarczającą liczbę rdzeni na swoim komputerze i być może rozpalisz kilka instancji AWS, powinieneś być w stanie trochę się ogolić :)
źródło
C, 1,210s
Z kodem OP działającym na moim komputerze 1m45.729s.
Kompilacja:
Specjalne podziękowania: @dyp za flagi kompilacji i pomysły na optymalizacje.
Przykładowe dane wyjściowe:
źródło
-march=native -fwhole-program -fstrict-aliasing -ftree-vectorize
Btw. Doszedłem do <4 s, używając trochę C ++ 11, w tym MT19937 plus auniform_int_distribution
.F
.n
jest równy8
, prawdopodobnie możesz użyć AVX (lub 2 * SSE), aby obliczyć produkt dot z odpowiedniąS
pamięcią.smmintrin.h
)Perl
Nie jest to tak szybkie jak rozwiązanie C, ale myślę, że jest dość szybkie w przypadku języka interpretowanego wysokiego poziomu. Zmniejsza to o 40% czas działania implementacji Pythona.
Algorytm :: kombinatoryka jest dostępny w Ubuntu (
sudo apt-get install libalgorithm-combinatorics-perl
). Pozostałe używane moduły to podstawowe moduły Perla, więc powinny być już zainstalowane jako część podstawowej instalacji Ubuntu.źródło
0..N-1
w ostatnim jest zasięgmap
, prawda? Zapomniałeśuse warnings
? :-) Chociaż logika w OP jest myląca, przesuwane okno nigdy nie przechodzi do ostatniego elementuS
.warnings
pozwalając traktować brakujące elementy jako zero.N-1
poprawia to. I faktycznie nieznacznie poprawia prędkość - jest teraz około 40% szybsza niż implementacja Pythona.any
można alternatywnie znaleźć w List :: MoreUtils, który choć nie jest modułem podstawowym, jest jednym z najczęściej używanych modułów CPAN.Julia: 4,66x wolniej!
Naprawdę zaczynam wątpić w statystyki na ich stronie internetowej ...
Zauważ, że poniższy kod Julii jest faktycznie bezpośrednią transkrypcją kodu Pythona OP bez żadnych optymalizacji. Używam tej
time()
funkcji, aby wykluczyć wolny czas uruchamiania Julii ...Julia: 5 m 32,912 s
Kod OP w PyPy: 1 m 11.506 s
Wyjście Julii:
źródło
RPython 0,187 s (258x szybciej)
Oryginalne źródło w / PyPy2.2.1: 1m 6.718s
Teraz z wątkami, porzucono wsparcie dla standardowego Pythona. Liczbę wątków roboczych można określić jako parametr wiersza poleceń, domyślnie jest to dwa.
RPython jest ograniczonym podzbiorem Pythona, który można przetłumaczyć na C, a następnie skompilować za pomocą RPython Toolchain . Jego wyraźnym celem jest pomoc w tworzeniu tłumaczy językowych, ale można go również używać do kompilacji prostych programów, takich jak ten powyżej. Większość „bardziej wyrafinowanych” funkcji Pythona, takich jak
itertools
lub nawetmap
nie są dostępne.Aby skompilować, utwórz lokalny klon bieżącego repozytorium pypy i uruchom następujące polecenie:
Wynikowy plik wykonywalny zostanie nazwany
convolution-c
lub podobny w bieżącym katalogu roboczym.Sparametryzowałem zmienne wejściowe, więc program powinien zostać uruchomiony jako:
aby dopasować przykładowy kod.
Uwagi dotyczące wdrażania
S in itertools.product([-1,1], repeat = n+m-1)
staje sięS in xrange(1<<n+m-1)
, interpretującS
jako mapę bitową: [0
,1
] → [-1
,1
]Podobnie
F
jest mapa bitowa z każdych dwóch bitów reprezentujących pojedyncze wartości:[
00
,01
,10
,11
] → [-1
,0
,0
,1
]Tablica prawdy służy do wyszukiwania produktu, a nie do wykonywania wielu prób.
Ponieważ używane są 32-bitowe liczby całkowite ze znakiem, nie
n
mogą być większe niż 15 in+m
nie większe niż 31. Arbitralną obsługę liczb całkowitych można uzyskać za pomocą parametrurpython.rlib.rbigint
razie potrzeby moduł .Pierwsza iteracja pętli iloczyn iloczynu jest rozwijana i łączona z testem nieważności
F
.Używany jest domowy PRNG, źródło wymienione. Autor artykułu pokazuje okres 2 32 -1 i twierdzi, że pomyślnie przeszedł wszystkie testy Dieharda z wyjątkiem jednego, chociaż osobiście tego nie potwierdziłem.
Losowe ziarno zmienia się co milisekundę, co jest tak samo dobre, jak pozwala na to znacznik czasu. Ponadto każdy wątek roboczy ma
xor
swój identyfikator procesu o tej wartości, aby mieć pewność, że każdy ma inne ziarno.Przykładowe czasy
2 wątki robocze:
4 wątki robocze:
8 wątków roboczych:
Oryginalne źródło OP:
Czas dla 100000 iteracji:
źródło
Julia: 1 min 21,4s (2,2x szybciej) (modyfikacja kodu Armana)
Kod operacji w PyPy: 3 min 1,4 s
Oba wykonano w REPL, nie licząc czasu na załadowanie pakietów.
Występują pewne problemy z kodem Armana, który powoduje, że jest on bardzo wolny: Używa wielu anonimowych funkcji i funkcji wyższego rzędu niepotrzebnie. Aby sprawdzić, czy cały wektor F jest równy zero, dlaczego po prostu nie napisać wszystkich (F == 0) zamiast wszystkich (x-> x == 0, F)? Jest krótszy i dosłownie tysiąc razy szybszy.
Używa także sumy (mapa (*, x, y)) jako iloczynu kropkowego zamiast po prostu kropki (x, y). Pierwsza wersja 650 razy wolniejsza dla wektora 10k podwaja się. A funkcja iloczynu jest zaimplementowana jako pętla for w czystej Julii.
Również interpretacje tablic są powolne. Lepiej jest napisać [0,1,0, -1] [rand (1: 4, n)] zamiast [[-1 0 0 1] [rand (1: 4)] dla j = 1: n] .
Wreszcie, zmienne globalne są złe juju w Julii. Julia jest szybka tylko wtedy, gdy piszesz kod w sposób umożliwiający działanie JIT i wnioskowania typu. Dużą część tego stanowi stabilność typu: kompilator musi mieć pewność, że typ zmiennej nie zmieni się na przykład w pętli.
źródło
Nimrod
Przykładowe dane wyjściowe:
Nimrod kompiluje się do C, dlatego wybór kompilatora C również ma znaczenie.
Używając clang, skompiluj z:
Używając gcc, skompiluj z:
Pomiń,
--passc:-flto
jeśli masz starszy kompilator C, który nie obsługuje LTO. Pomiń tę--cc=...
opcję, jeśli nie masz nic przeciwko domyślnemu wyborowi kompilatora C. Kod wymaga Nimrod 0.9.4 lub 0.9.5 .Na moim quadcore iMac (rdzeń i5 2,66 GHz) kod działa w około .15 sekund z gcc 4.9, .16 sekund z clang, w porównaniu do 88 sekund dla PyPy 2.2.1 (tj. Przyspieszenie ponad 500 razy). Niestety nie mam dostępu do maszyny z więcej niż czterema rdzeniami, która ma również zainstalowany PyPy lub w której mógłbym łatwo zainstalować PyPy, chociaż dostaję około .1 sekundy (z dużą ilością szumów pomiarowych) na 64-rdzeniowym AMD Opteron 6376 1,4 GHz (zgodnie z / proc / cpuinfo) z gcc 4.4.6.
Implementacja stara się być wierna oryginalnemu, a nie optymalizować kod kosztem czytelności, nie rezygnując z oczywistych optymalizacji. Co ciekawe, rekurencja w ogonie
initVecRand()
jest nieco szybsza niż pętla z instrukcją break z gcc i clang. Ręczne rozwijanie jednej iteracjiconvolve
pętli testowej w pętli głównej również spowodowało przyspieszenie, prawdopodobnie z powodu lepszego przewidywania gałęzi.źródło
Jawa
Przetłumaczyłem powyższe rozwiązanie C ++ na Javę:
Na moim komputerze otrzymuję następujące dane wyjściowe dla programu Java:
Program OPs działa na moim komputerze około 53 sekund:
Program c ++ wykonał tylko około 0,15 sekundy:
To około 2,5 razy szybciej niż odpowiednie rozwiązanie Java (nie wykluczyłem uruchamiania VM). Te rozwiązania Java są około 142 razy szybsze niż program wykonywany za pomocą PyPy.
Ponieważ byłem osobiście zainteresowany, ustawiłem
iters
na 100_000 dla Java i C ++, ale współczynnik 2,5 nie spadł na korzyść Javy, jeśli coś się powiększyło.EDYCJA: Uruchomiłem programy na 64-bitowym komputerze Arch Linux.
EDIT2: Chcę dodać, że zacząłem od zgrubnego tłumaczenia kodu python:
Ten program działał około 3,6 sekundy:
Co jest około 14 razy szybsze niż rozwiązanie PyPy. (Wybranie standardowej funkcji losowej zamiast funkcji fastRandom prowadzi do wykonania 5 sekund)
źródło
Python 3.5 + numpy 1.10.1, 3,76 sekundy
Testy zostały przeprowadzone na moim Macbooku Pro. Kod OP zajął ~ 6 minut na tej samej maszynie.
Odpowiadam na to pytanie, ponieważ nie mam 10 reputacji i nie mogę odpowiedzieć na część I :-p
W ciągu ostatnich kilku dni starałem się dowiedzieć, jak skutecznie wykonywać ogromne zwoje przy pomocy numpy (bez polegania na pakiecie innej firmy, nawet scipy). Kiedy natknąłem się na tę serię wyzwań podczas moich badań, postanowiłem spróbować. Być może przyjechałem do tej gry za późno, ale oto moja próba użycia Pythona 3.5 i numpy 1.10.1.
Wstępnie obliczyłem tablice S i F i spłaszczyłem tablicę S podczas wykonywania splotu, który (na podstawie moich eksperymentów) mógłby skorzystać z prędkości np. Konwolucji. Innymi słowy, ponieważ nie znalazłem procedury wektoryzacji wektoryzacji, podrobiłem wektoryzację kodu przez spłaszczenie całej tablicy i miałem nadzieję, że np. Konwój zrobi dla mnie wektoryzację pod maską, która wydawała się działać. Uwaga: Użyłem mode = „same” i przyciąłem wiodące i końcowe elementy, które były bezużyteczne.
Na moim Macbooku Pro wyniki testu dają 3,76 sekundy . Kiedy uruchomiłem kod OP (zmodyfikowany do Python 3.5), mam około 6 minut . Przyspieszenie jest około 100 razy.
Jedną wadą jest to, że ponieważ tablice S i F mają być przechowywane, zapotrzebowanie na pamięć może stanowić problem, jeśli rozmiary są zbyt duże.
Użyłem tej samej metody w części I i uzyskałem przyspieszenie ~ 60-100x na moim laptopie.
Ponieważ zrobiłem wszystko na moim Macbooku Pro, jeśli ktoś mógłby przetestować mój kod i dać mi znać, jak działa na twoim komputerze, byłbym bardzo wdzięczny!
źródło
J, przyspieszenie
130x~ 50x?Czasy na losowym debianie:
Myślę, że jest miejsce na poprawę.
źródło
pypy
, a niepython
, dlatego wydaje się, że twój skrypt przyspiesza 130x.C ++: x200 (4-rdzeniowy i7, powinien być skalowany do x400 na 8-rdzeniowym)
Próbowanie prostszego C ++ 11 (testowane z VS 2012, gcc i clang) z równoległością.
Aby to skompilować i uruchomić pod Linuksem z gcc 4.8.1:
W systemie Linux potrzebujemy również
std::launch::async
wymusić wiele wątków. Brakowało mi tego we wcześniejszej wersji.W programie Visual Studio (2012+) powinno to po prostu działać, ale należy utworzyć kompilację wydania dla pomiaru czasu ...
Na moim starszym dwurdzeniowym i3 działa to w ~ 0,9 sekundy. Na moim czterordzeniowym rdzeniu i7 jest to 0.319s vs. pypy 66 sekund.
Na 8-rdzeniowym i7 powinno to być w zakresie przyspieszenia x400. Przejście na tablice w stylu C przyspieszy to, ale byłem zainteresowany pozostaniem z kontenerami C ++. Dla mnie ciekawie jest zobaczyć przyspieszenie, które można uzyskać, pozostając stosunkowo blisko problematycznej domeny i na stosunkowo wysokim poziomie, w czym myślę, że C ++ jest naprawdę dobry. Na uwagę zasługuje również względna łatwość sparametryzowania przy użyciu konstrukcji C ++ 11.
@ Rozwiązanie bitowe ilmale jest bardzo fajne i działa dla -1/1/0. Można również rzucić SSE i może uzyskać znaczne przyspieszenie.
Poza paralelizacją jest jeszcze jedna „sztuczka”, która zmniejsza liczbę sumowań. Przykładowe wyniki: 6332947 2525357 1041957 438353 193024 87331 40902 19649
źródło
Fortran: 316x
Dobra, Fortran: Mam to do
106x155x160x316x gdy używam Xorshift RNG i OpenMP na 4-rdzeniowym procesorze i7. Poza tym nie ma wielkich sztuczek. Aby iterator skonstruował S, po prostu używam binarnej reprezentacji 16-bitowej liczby całkowitej i. Zauważysz, że oprócz wbudowanego RNG i „iteratora” / mapowania od i do S, kod jest tak samo wysoki, jak kod Pythona.Edycja: usunięto „if” w Xorshift, teraz używając „r = abs (w / ...)” zamiast „r = w / ...”. Zwiększa od 106x do 155x.
Edycja2: Generuje 15 razy więcej liczb losowych niż rozwiązanie C ++. Jeśli ktoś ma zerowe narzutowe rozwiązanie do przekształcania losowej liczby int w tablicę zer i jedynek w Fortranie, to jestem cały w uszach. Wtedy moglibyśmy pokonać C ++ :)
Edycja3: Pierwsza edycja wprowadziła błąd, jak zauważył Lembik. Jest to teraz naprawione, z niewielką poprawą przyspieszenia. Spróbuję skorzystać z sugestii Eelvex, aby uzyskać większe przyspieszenie.
Edycja4: Profilowanie wskazało, że konwersja do wartości rzeczywistej i powrót do liczby całkowitej za pomocą nint () była powolna. Zamieniłem to na jedną liczbę całkowitą, która wykonuje zarówno skalowanie, jak i zaokrąglanie, przechodząc od przyspieszenia 160x do 316x.
Połącz z:
Przykładowe dane wyjściowe:
Kod PO:
źródło