Jak poprawić wydajność dzięki programowaniu funkcjonalnemu?

Niedawno zapoznałem się z przewodnikiem „ Naucz się świetnego dobrego Haskella” i jako praktykę chciałem rozwiązać z nim problem dotyczący projektu Euler 5 , który określa:

Jaka jest najmniejsza liczba dodatnia, która jest równomiernie podzielna przez wszystkie liczby od 1 do 20?

Postanowiłem najpierw napisać funkcję określającą, czy daną liczbę można podzielić przez te liczby:

divisable x = all (\y -> x `mod` y == 0)[1..20]

Następnie obliczyłem najmniejszy, używając head:

sm = head [x | x <- [1..], divisable x]

I w końcu napisał wiersz, aby wyświetlić wynik:

main = putStrLn $ show $ sm

Niestety zajęło to około 30 sekund. Robienie tego samego z liczbami od 1 do 10 daje wynik niemal natychmiast, ale z drugiej strony wynik jest znacznie mniejszy niż rozwiązanie dla 1 do 20.

Rozwiązałem go wcześniej w C i tam wynik dla 1 do 20 został również obliczony prawie natychmiast. To prowadzi mnie do wniosku, że nie rozumiem, jak interpretować ten problem dla Haskella. Przejrzałem rozwiązania innych ludzi i znalazłem to:

main = putStrLn $ show $ foldl1 lcm [1..20]

To prawda, wykorzystuje to wbudowaną funkcję, ale dlaczego wynik końcowy jest o wiele wolniejszy, gdy robisz to sam? Tamte tutoriale pokazują, jak używać Haskell, ale nie widzę wiele pomocy w przekształcaniu algorytmów w szybki kod.

Najpierw musisz się upewnić, że masz zoptymalizowany plik binarny, zanim pomyślisz, że problem stanowi język. Przeczytaj rozdział Profilowanie i optymalizacja w Real Wolrd Haskell. Warto zauważyć, że w większości przypadków wysoki poziom języka kosztuje co najmniej część wydajności.

Zauważ jednak, że inne rozwiązanie nie jest szybsze, ponieważ wykorzystuje wbudowaną funkcję, ale po prostu dlatego, że wykorzystuje znacznie szybszy algorytm : aby znaleźć najmniejszą wspólną wielokrotność zestawu liczb, potrzebujesz tylko kilku GCD. Porównaj to ze swoim rozwiązaniem, które przewija wszystkie liczby od 1 do foldl lcm [1..20]. Jeśli spróbujesz z 30, różnica między środowiskami uruchomieniowymi będzie jeszcze większa.

Spójrz na złożoność: twój algorytm ma O(ans*N)środowisko ansuruchomieniowe , gdzie jest odpowiedź i Nliczba, do której sprawdzasz podzielność (w twoim przypadku 20).
Drugi algorytm wykonuje jednak Nczasy , a GCD ma złożoność . Dlatego drugi algorytm ma złożoność . Możesz sam ocenić, co jest szybsze.lcmlcm(a,b) = a*b/gcd(a,b)O(log(max(a,b)))O(N*log(ans))

Podsumowując:
Twoim problemem jest algorytm, a nie język.

Zauważ, że istnieją wyspecjalizowane języki, które są zarówno funkcjonalne, jak i skupiają się na programach matematycznych, takich jak Mathematica, które w przypadku problemów matematycznych są prawdopodobnie szybsze niż prawie wszystko inne. Ma bardzo zoptymalizowaną bibliotekę funkcji i obsługuje paradygmat funkcjonalny (co prawda obsługuje także programowanie imperatywne).

Moją pierwszą myślą było to, że tylko liczby podzielne przez wszystkie liczby pierwsze <= 20 będą podzielne przez wszystkie liczby mniejsze niż 20. Więc wystarczy wziąć pod uwagę liczby, które są wielokrotnościami 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 . Takie rozwiązanie sprawdza 1/9 699 690 tylu liczb, co podejście brutalnej siły. Ale twoje szybkie rozwiązanie Haskell działa lepiej.

Jeśli rozumiem rozwiązanie „szybkiego Haskella”, używa ono foldl1, aby zastosować funkcję lcm (najmniejszą wspólną wielokrotność) do listy liczb od 1 do 20. Tak więc zastosowałby lcm 1 2, dając 2. Następnie lcm 2 3, uzyskując 6 Następnie lcm 6 4 daje 12 i tak dalej. W ten sposób funkcja lcm jest wywoływana tylko 19 razy, aby uzyskać odpowiedź. W notacji Big O to operacje O (n-1) mające na celu znalezienie rozwiązania.

Twoje wolne rozwiązanie Haskell przechodzi przez cyfry 1-20 dla każdej liczby od 1 do twojego rozwiązania. Jeśli nazwiemy rozwiązanie s, wówczas rozwiązanie wolno-Haskell wykonuje operacje O (s * n). Wiemy już, że s wynosi ponad 9 milionów, więc to prawdopodobnie tłumaczy powolność. Nawet jeśli wszystkie skróty i osiągają średnią w połowie listy liczb 1-20, to wciąż tylko O ​​(s * n / 2).

Wywołanie headnie oszczędza cię przed wykonaniem tych obliczeń, należy je wykonać, aby obliczyć pierwsze rozwiązanie.

Dzięki, to było interesujące pytanie. To naprawdę poszerzyło moją wiedzę o Haskell. W ogóle nie byłbym w stanie na nie odpowiedzieć, gdybym nie studiował algorytmów zeszłej jesieni.

Początkowo nie planowałem pisać odpowiedzi. Ale powiedziano mi, gdy inny użytkownik stwierdził dziwne twierdzenie, że zwykłe pomnożenie pierwszych liczb pierwszych jest droższe obliczeniowo niż wielokrotne stosowanie lcm. Oto dwa algorytmy i niektóre testy porównawcze:

Mój algorytm:

Algorytm pierwszej generacji, dający mi nieskończoną listę liczb pierwszych.

isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = all ((/= 0) . mod n) (takeWhile ((<= n) . (^ 2)) primes)

toPrime :: Int -> Int
toPrime n 
    | isPrime n = n 
    | otherwise = toPrime (n + 1)

primes :: [Int]
primes = 2 : map (toPrime . (+ 1)) primes

Teraz za pomocą tej listy głównej obliczamy wynik dla niektórych N:

solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 $ takeWhile (<= n) (fromIntegral <$> primes)

Teraz inny algorytm oparty na lcm, który wprawdzie jest dość zwięzły, głównie dlatego, że zaimplementowałem generowanie liczb pierwszych od zera (i nie użyłem algorytmu zrozumienia zwięzłej listy ze względu na jego słabą wydajność), podczas gdy lcmzostał po prostu zaimportowany z Prelude.

solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without `flip` on `lcm`

Teraz dla testów porównawczych kod, którego użyłem dla każdego był prosty: ( -prof -fprof-auto -O2wtedy +RTS -p)

main :: IO ()
main = print $ solvePrime n
-- OR
main = print $ solveLcm n

Do n = 100,000, solvePrime:

total time = 0.04 secs
total alloc = 108,327,328 bytes

vs solveLcm:

total time = 0.12 secs
total alloc = 117,842,152 bytes

Do n = 1,000,000, solvePrime:

total time = 1.21 secs
total alloc = 8,846,768,456 bytes

vs solveLcm:

total time = 9.10 secs
total alloc = 8,963,508,416 bytes

Do n = 3,000,000, solvePrime:

total time = 8.99 secs
total alloc = 74,790,070,088 bytes

vs solveLcm:

total time = 86.42 secs
total alloc = 75,145,302,416 bytes

Myślę, że wyniki mówią same za siebie.

Profiler wskazuje, że pierwsze generowanie zajmuje coraz mniejszy procent czasu pracy n. Więc to nie jest wąskie gardło, więc na razie możemy to zignorować.

Oznacza to, że naprawdę porównujemy sprawdzanie, lcmgdzie jeden argument przechodzi od 1 do n, a drugi geometrycznie od 1 do ans. Do dzwonienia *w tej samej sytuacji i dodatkowej korzyści polegającej na pomijaniu każdego niepierwszego numeru (asymptotycznie za darmo, ze względu na droższy charakter *).

I dobrze wiadomo, że *jest szybszy niż lcm, co lcmwymaga wielokrotnego stosowania modi modjest asymptotycznie wolniejszy (w O(n^2)porównaniu ~O(n^1.5)).

Tak więc powyższe wyniki i krótka analiza algorytmu powinny wyraźnie pokazać, który algorytm jest szybszy.