Zadaniem jest po prostu sprawdzenie, o ile szybciej możesz obliczyć n, wybierz n / 2 (nawet dla n) niż wbudowana funkcja w pythonie. Oczywiście dla dużej n jest to raczej duża liczba, więc zamiast wypisywać liczbę całkowitą powinieneś wypisać sumę cyfr. Na przykład n = 100000
odpowiedź brzmi 135702
. Bo n=1000000
tak jest 1354815
.
Oto kod python:
from scipy.misc import comb
def sum_digits(n):
r = 0
while n:
r, n = r + n % 10, n / 10
return r
sum_digits(comb(n,n/2,exact=True))
Twój wynik to (highest n on your machine using your code)/(highest n on your machine using my code)
. Twój kod musi zostać zakończony za 60 sekund lub krócej.
Twój program musi dać poprawne wyjście dla wszystkich parzystych n: 2 <= n <= (najwyższa n)
Nie można używać wbudowanego kodu ani bibliotek, które obliczają dwumianowe współczynniki lub wartości, które można szybko przekształcić w dwumianowe.
Możesz użyć dowolnego wybranego języka.
Wiodąca odpowiedź Obecna wiodąca odpowiedź z niesamowitym 680.09 pochodzi od justhalf.
n
się do milionów, podczas gdy wątpię, czy funkcja Python poradziłaby sobie z czymś większym niżn = 1e5
bez zadławienia.Odpowiedzi:
C ++ (GMP) - (287,000 000 / 422,000) = 680,09
Bezwstydnie połącz twierdzenie Kummer'a xnor i GMP qwr.
Nadal nie jest nawet blisko rozwiązania Go, nie jestem pewien, dlaczego.Edycja: Dzięki Keith Randall za przypomnienie, że mnożenie jest szybsze, jeśli liczba ma podobny rozmiar. Zaimplementowałem multiplikację wielopoziomową, podobną do koncepcji koalescencji pamięci w zarządzaniu pamięcią. Wynik jest imponujący. To, co kiedyś zajmowało 51 sekund, teraz zajmuje tylko 0,5 sekundy (tj. 100-krotna poprawa !!)
Biegnij za
n=287,000,000
Kod. Połącz z
-lgmp -lgmpxx -O3
źródło
n
18s, obliczanie centralnego współczynnika dwumianowego, a reszta 37s w przekształcaniu wyniku na ciąg i sumowanie cyfry.Idź, 33,96 = (16300000/480000)
Działa poprzez zliczenie wszystkich czynników pierwszych w liczniku i mianowniku i anulowanie dopasowujących czynników. Mnoży resztki, aby uzyskać wynik.
Ponad 80% czasu spędza się na konwersji na bazę 10. Musi istnieć lepszy sposób, aby to zrobić ...
źródło
Python 3 (8,8 = 2,2 miliona / 0,25 miliona)
To jest w Pythonie, który nie jest znany z szybkości, więc prawdopodobnie lepiej poradzisz sobie z przeniesieniem go na inny język.
Generator liczb pierwszych wzięty z tego konkursu StackOverflow .
Główną ideą algorytmu jest użycie twierdzenia Kummer'a, aby uzyskać pierwszą faktoryzację dwumianu. Dla każdej liczby pierwszej uczymy się jej największej mocy, która dzieli odpowiedź, i mnożymy działający produkt przez tę moc liczby pierwszej. W ten sposób musimy pomnożyć tylko raz dla każdej liczby pierwszej w rozkładzie na czynniki pierwsze odpowiedzi.
Dane wyjściowe pokazujące podział czasu:
Zaskakujące jest to, że większość czasu zajmuje konwersja liczby na ciąg znaków w celu zsumowania jego cyfr. Co zaskakujące, konwersja na ciąg znaków była znacznie szybsza niż pobieranie cyfr z powtórzeń
%10
i//10
chociaż cały ciąg należy prawdopodobnie przechowywać w pamięci.Generowanie liczb pierwszych zajmuje mało czasu (a zatem nie czuję się niesprawiedliwie kopiując istniejący kod). Sumowanie cyfr jest szybkie. Rzeczywiste pomnożenie zajmuje jedną trzecią czasu.
Biorąc pod uwagę, że sumowanie cyfr wydaje się być czynnikiem ograniczającym, być może algorytm pomnożenia liczb w postaci dziesiętnej zaoszczędziłby w sumie czas poprzez skrócenie konwersji binarnej / dziesiętnej.
źródło
Java (wynik 22500/365000 = 0,062)
Nie mam Pythona na tym komputerze, więc jeśli ktoś mógłby to zdobyć, byłbym wdzięczny. Jeśli nie, będzie musiał poczekać.
Wąskie gardło jest dodatkiem do obliczenia odpowiedniej sekcji trójkąta Pascala (90% czasu pracy), więc użycie lepszego algorytmu mnożenia nie byłoby tak naprawdę pomocne.
Pamiętaj, że to, co wywołuje pytanie,
n
jest tym, co nazywam2n
. Argument wiersza poleceń jest tym, co wywołuje pytanien
.źródło
javac CodeGolf37270.java
) i wykonuje się w Javie 1.8 (java CodeGolf37270 n
). Nie jestem pewien, czy są jakieś opcje optymalizacji, o których nie wiem. Nie mogę spróbować skompilować z Javą 1.8, ponieważ nie można jej zainstalować z moim pakietem Java ...GMP - 1500000/300000 = 5,0
Chociaż ta odpowiedź nie będzie konkurować z sitami, czasami krótki kod może nadal przynosić rezultaty.
źródło
Java, niestandardowa duża liczba całkowita: 32,9 (120000000/365000)
Główna klasa jest dość prosta:
Opiera się na dużej klasie całkowitej, która jest zoptymalizowana pod kątem mnożenia i
toString()
które stanowią znaczne wąskie gardła w implementacji zjava.math.BigInteger
.Dużym wąskim gardłem jest naiwne mnożenie (60%), a następnie drugie mnożenie (37%) i przesiewanie (3%).
digsum()
Wezwanie jest nieznaczna.Wydajność mierzona za pomocą OpenJDK 7 (wersja 64-bitowa).
źródło
Python 2 (PyPy), 1,134,000 / 486,000 = 2,32
Wynik: 1537 506
Ciekawostka: wąskim gardłem w kodzie jest dodawanie cyfr, a nie obliczanie współczynnika dwumianowego.
źródło
Java (2,020 000 / 491,000) = 4,11
zaktualizowane, poprzednio 2.24
Java
BigInteger
nie jest najszybszym narzędziem liczbowym, ale jest lepsza niż nic.Podstawowa formuła wydaje się być
n! / ((n/2)!^2)
, ale wydaje się, że jest to zbędne mnożenie.Możesz uzyskać znaczne przyspieszenie, eliminując wszystkie czynniki pierwsze znalezione zarówno w liczniku, jak i mianowniku. Aby to zrobić, najpierw uruchamiam proste sito główne. Następnie dla każdej liczby pierwszej liczę, do jakiej mocy trzeba ją podnieść. Przyrost za każdym razem, gdy widzę czynnik w liczniku, zmniejszenie dla mianownika.
Dwójki radzę sobie osobno (i najpierw), ponieważ łatwo je policzyć / wyeliminować przed faktoringiem.
Gdy to zrobisz, masz minimalną liczbę koniecznych mnożenia, co jest dobre, ponieważ mnożenie BigInt jest powolne .
Aha, a suma wyjściowa dla n = 2020000 jest
2735298
dla celów weryfikacji.źródło