W związku z ostatnim uderzeniem w Python , oto próba pokazania mocnych stron Pythona. Twoim wyzwaniem jest napisanie programu, który oblicza silnię tak dużej liczby, jak to możliwe, w ciągu 10 sekund.n
Twój wynik będzie (highest n for your program on your machine)/(highest n for my program on your machine)
Zasady
- Musisz obliczyć dokładne rozwiązanie liczb całkowitych. Ponieważ silnia byłaby znacznie wyższa niż to, co może zmieścić się w 64-bitowej liczbie całkowitej bez znaku, możesz użyć ciągów, jeśli twój język nie obsługuje dużych liczb całkowitych
- Standardowe luki są zabronione. W szczególności nie można używać żadnych zasobów zewnętrznych.
- Tylko część obliczeniowa (obejmuje czas na wszelkie obejścia wykorzystujące ciągi) dodaje do całkowitego czasu, który powinien być średnio poniżej 10 sekund.
- Tylko programy jednowątkowe.
- Musisz przechowywać dane wyjściowe w formie łatwej do wydrukowania (ponieważ drukowanie wymaga czasu) (patrz mój program poniżej), ciąg znaków, zmienna, tablica znaków itp.
EDYTOWAĆ:
- Twój program musi dawać prawidłowe dane wyjściowe dla wszystkich
n
:1 <= n <= (your highest n)
EDYCJA 2:
- Nienawidzę mówić tego wprost, ale korzystanie z wbudowanych funkcji czynnikowych twojego języka podlega standardowym lukom http://meta.codegolf.stackexchange.com/a/1078/8766 Przepraszamy Mathematica i Sage
Mój program
from __future__ import print_function
import time
def factorial( n ):
return reduce( ( lambda x , y : x * y ) , xrange( 1 , n + 1 ) , 1 )
start = time.clock()
answer = factorial( 90000 )
end = time.clock()
print ( answer )
print ( "Time:" , end - start , "sec" )
Najwyższy wynik wygrywa. Dla przypomnienia, mój kod może zarządzać n = 90000
w około 9.89
sekundach na Pentium 4 3,0 GHz
EDYCJA: Czy każdy może dodać wynik, a nie tylko najwyższą liczbę n . Po prostu najwyższy n
nie ma żadnego znaczenia, ponieważ zależy od twojego sprzętu. W przeciwnym razie nie można mieć obiektywnego kryterium wygranej. Odpowiedź ali0sha robi to poprawnie.
Mamy zwycięzcę. Nie zaakceptowałem odpowiedzi java /codegolf//a/26974/8766, ponieważ to rodzaj spódnic blisko http://meta.codegolf.stackexchange.com/a/1080/8766
źródło
operator.mul
zamiast funkcji lambdafactorial(Inf)
zwracaInf
w ułamku sekundy.Odpowiedzi:
C ++ z GMP, wynik = 55,55 (10 000 000/180 000)
źródło
Python 2.7
42,575 = (6,812 000/160 000) ok
Kod:
Test:
Wynik:
Jak to działa:
Większe zwielokrotnienia zajmują więcej czasu, dlatego chcemy wykonać jak najwięcej małych zwielokrotnień. Jest to szczególnie prawdziwe w Pythonie, gdzie dla liczb mniejszych niż
2^64
używamy arytmetyki sprzętowej, a powyżej używamy oprogramowania. Tak więc,m(L)
zaczynamy od listyL
; jeśli ma nieparzystą długość, usuwamy jedną liczbę z rozważań, aby była jeszcze większa. Następnie mnożymy element1
przez element-2
, element za3
pomocą-4
itd., AbyTakie podejście zapewnia, że używamy arytmetyki sprzętowej tak długo, jak to możliwe, po czym przełączamy się na wydajną bibliotekę arytmetyczną gmc.
W
fac2
, przyjmujemy również bardziej klasyczne podejście dziel i zwyciężaj, w którym dzielimy każdą wielokrotność 2 i przesuwamy je pod koniec bitów, aby uzyskać trywialny wzrost wydajności. Umieściłem go tutaj, ponieważ zwykle jest o około 0,5% szybszy niżfac1
.Wersja w golfa
fac1
(bo mogę), 220Bźródło
gmpy2
? $ python Python 2.7.3 (domyślnie, 27 lutego 2014, 19:58:35) [GCC 4.6.3] na linux2 Wpisz „pomoc”, „prawo autorskie”, „kredyty” lub „licencja”, aby uzyskać więcej informacji. >>> z gmpy2 import mpz Traceback (ostatnie połączenie ostatnio): Plik „<stdin>”, wiersz 1, w <module> ImportError: Brak modułu o nazwie gmpy2 >>>while len(L): ...
tego zrobićwhile len(L)>1: ...
?Java - 125,15 (21 400 000 / 171,000)
Również bezwstydnie skopiowane z repozytorium Github Petera Luschnego (dzięki @ semi-extrinsic) i licencjonowane na licencji MIT, wykorzystuje algorytm „pierwiastkowania zagnieżdżonego do kwadratu”, jak zaproponowali Albert Schönhage i in. (zgodnie ze stroną opisu algorytmów czynnikowych Luschnego ).
Lekko dostosowałem algorytm, aby używał BigInteger Javy i nie używał tabeli odnośników dla n <20.
Skompilowany z gcj, który używa GMP do implementacji BigInteger i działał na Linuksie 3.12.4 (Gentoo), na Core i7 4700MQ przy 2,40 GHz
źródło
gcj -O3 --main=PrimeSieveFactorialSchoenhage PrimeSieveFactorialSchoenhage.java -o pf_nest_square_fact
Python 3, n = 100000
Wystarczyła prosta zmiana algorytmu, aby podnieść kod przykładowy o 10000.
Oczywiście nie jest to najbardziej kreatywna odpowiedź, ale tak naprawdę jest tylko jeden sposób, aby zrobić czynnik.
źródło
Perl + C, n = około 3 milionów
Tutaj używam biblioteki Math :: BigInt :: GMP dostępnej na CPAN, która zapewnia ogromne przyspieszenie podstawowych obiektów Perla Math :: BigInt.
Pamiętaj, że mój komputer jest prawdopodobnie nieco wolniejszy od twojego. Używając twojego oryginalnego skryptu Python, mogę obliczyć tylko
factorial(40000)
w 10 sekund;factorial(90000)
zajmuje dużo dłużej. (Wcisnąłem Ctrl + C po minucie.) Na twoim sprzęcie, używając Math :: BigInt :: GMP, możesz być w stanie obliczyć silnię 5 milionów lub więcej w mniej niż 10 sekund.Jedną z rzeczy, które możesz zauważyć, jest to, że chociaż silnia jest obliczana niewiarygodnie szybko, wydrukowanie wyniku jest bardzo wolne, zajmuje około trzy razy więcej niż pierwotne obliczenie. Wynika to z tego, że GMP wewnętrznie używa reprezentacji binarnej zamiast dziesiętnej, a wydrukowanie go wymaga konwersji binarnej na dziesiętną.
źródło
Math::BigInt
Python 2.7
5,94 = 1'200'000 / 202'000
Wykorzystuje względną łatwość mnożenia wielu grup małych liczb, a następnie mnożenia ich w porównaniu do dużej liczby mnożeń z udziałem dużej liczby.
źródło
C #: 0,48 (77 000/160 000)
Nie jestem z tego zadowolony.
Czy C # jest tak wolny?
Ale i tak jest mój wpis.
Gdy n = 77000 trzeba
00:00:09:8708952
obliczyć.Pracuję w trybie Release, poza Visual Studio, używając Core i3-2330M @ 2.2GHz.
Edycja: Ponieważ nie robię niczego inteligentnego, akceptuję ten wynik. Być może .NET Framework 4.5 dodaje trochę narzutu (lub BigInteger nie jest tak szybki).
źródło
n
zero approached by
operatora, aby był ładniejszy (na przykład zacznij od,n = ... + 1
a potem zróbwhile (0 <-- n) result *= n;
)bc, wynik = 0,19
Co do cholery, oto mój pretendent do „Ile możesz powoli pomnożyć?”
bc jest „językiem kalkulatora o dowolnej precyzji”, ale niestety raczej powolnym:
W około 10 sekund na moim MacBooku Pro z połowy 2012 roku (2,3 GHz Intel Core i7) odpowiedź na python referencyjny może obliczyć 122000 !, ale ten skrypt bc może obliczyć tylko 23600 !.
Z drugiej strony 10000! zajmuje 1.5s ze skryptem referencyjnym Pythona, ale skrypt bc zajmuje 50s.
O jej.
źródło
read()
, więc pobiegłemtime sed 's/read()/28000/' factorial.bc | bc
.Bash: wynik = 0,001206 (181/150000)
Ukradłem funkcje matematyczne Rosettacode - długie mnożenie, którego nie analizowałem ani nie próbowałem zoptymalizować.
Możesz zmienić algorytm lub wypróbować inną metodę podziału ciągów.
źródło
Python 3, Advanced Algo autor: Peter Luschny: 8,25x (1 280 000/155 000)
Bezwstydnie skopiowane od Petera Luschnego,
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm ,
który udostępnia ten kod na licencji „Creative Commons Uznanie autorstwa-Na tych samych warunkach 3.0”.
Jest to właściwie dość zaawansowany algorytm, wykorzystujący coś, co nazywa się „zmiennym silnikiem” i listą liczb pierwszych. Podejrzewam, że mogłoby być jeszcze szybciej, gdyby podobało się wielu innym odpowiedziom i wykonał większość multiplikacji z 32-bitowymi liczbami całkowitymi.
źródło
Java - 10.9
n = 885000
Mergesort-y.
BigInteger
s są powolne.Zalecenia dotyczące bibliotek liczb całkowitych Java o dowolnej precyzji? : P
źródło
C ++ (specyficzny dla x86_64) - 3.0 (390000/130000)
(łatwo przenośny na x86-32, przenoszenie na inne architektury oznacza znaczną utratę prędkości)
Oto moja własna mikro-implementacja długiej arytmetyki.
Samo obliczenie zajmuje 10 sekund, a mimo że wydruk jest łatwy do wydrukowania (zobacz
operator<<
przeciążenie), wydrukowanie go zajmuje więcej czasu.źródło
g++ -O2 factorial.cc -o factorial
i jego wynik wynosi 3,90 = 382000 / 98000.r
wzrostu. Jeśli tak, i możesz zrobić wyższąr
w 10 sekund, twój wynik spada.Python 3: 280000/168000
Czas działania programu: pomiędzy
9.87585953253
i10.3046453994
. Czas działania mojego programu: około10.35296977897559
.Przeczytałem tę odpowiedź na cs.SE i postanowiłem spróbować ją zaimplementować w Pythonie. Jednak przypadkowo odkryłem, że
n! = (⌊n / 2⌋)! * 2**(⌊n / 2⌋) * n!!
(uwaga:!!
jest podwójnym silnikiem ). Przekształciłem to w formę nierekurencyjną.Komentarze pokazują moją próbę uniknięcia ponownego obliczenia podwójnej silni, ale odkryłem, że przechowywanie każdej wartości było zbyt kosztowne dla pamięci, co spowodowało, że mój komputer działał jeszcze wolniej. Mogę to poprawić, przechowując tylko to, co jest potrzebne.
O dziwo zaimplementowałem naiwne proste mnożenie w Pythonie 3 i robi to lepiej niż twój program:
n = 169000
w 10 sekund .:źródło
Ruby 2.1
wynik = 1,80 = 176_000 / 98_000
EDYCJA: poprawiona z
1.35 = 132_000 / 98_000Wziąłem pomysły z algorytmu czynnikowego GMP . Ten program używa standardowej biblioteki do generowania liczb pierwszych. Ruby to zły wybór, ponieważ mnożenie wydaje się wolniejsze w Rubim niż w Pythonie.
Tak, mój plik binarny
ruby 2.1.0p0 (2013-12-25 revision 44422) [x86_64-openbsd]
linków przeciwko GMP. Ruby 2.1 dodał funkcję do korzystania z GMP do dużego mnożenia, ale nadal wydaje się wolniejszy niż Python 2.7.źródło
Julia - wynik = 15,194
Wykorzystując dokładnie to samo podejście, co w programie referencyjnym ...
Wykorzystuje więc redukcję, podstawową operację mnożenia binarnego i zakres (w tym przypadku użycie dużej (n) do wymuszenia wykonania obliczeń w BigInt zamiast Int64). Z tego rozumiem
Na moim komputerze, z programem referencyjnym działającym z wejściem 154000, otrzymuję
Time: 10.041181 sec
dane wyjściowe (uruchom przy użyciupython ./test.py
, gdzie test.py to nazwa pliku zawierającego kod referencyjny)źródło
tcl, 13757
Moja odpowiedź to sprawdzić limity tcl.
Pierwszy wiersz służy tylko do ustawienia parametru wejściowego:
Pozostałe to sam algorytm:
Przetestowałem swój kod na http://rextester.com/live/WEL36956 ; Jeśli powiększę n, dostanę SIGKILL; may n może stać się większy na lokalnym tłumaczu tcl, którego nie mam.
źródło