Wie kann die Effizienz durch funktionale Programmierung verbessert werden?

Ich habe vor kurzem den Leitfaden „ Lernen Sie eine Haskell für großartige Gutes“ durchgearbeitet und wollte in der Praxis das Projekt Euler-Problem 5 damit lösen , in dem Folgendes angegeben ist:

Was ist die kleinste positive Zahl, die durch alle Zahlen von 1 bis 20 gleichmäßig teilbar ist?

Ich habe mich dazu entschlossen, zuerst eine Funktion zu schreiben, die bestimmt, ob eine bestimmte Zahl durch diese Zahlen teilbar ist:

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

Dann habe ich den kleinsten berechnet mit head:

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

Und schließlich schrieb die Zeile, um das Ergebnis anzuzeigen:

main = putStrLn $ show $ sm

Leider dauerte dies etwa 30 Sekunden. Wenn Sie mit den Zahlen 1 bis 10 dasselbe tun, erhalten Sie fast sofort ein Ergebnis, aber das Ergebnis ist wiederum viel kleiner als die Lösung für 1 bis 20.

Ich habe es früher in C gelöst und dort wurde das Ergebnis für 1 bis 20 auch fast sofort berechnet. Dies lässt mich glauben, dass ich die Interpretation dieses Problems für Haskell missverstehe. Ich habe die Lösungen anderer Leute durchgesehen und Folgendes festgestellt:

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

Gut, dies verwendet eine eingebaute Funktion, aber warum ist das Endergebnis so viel langsamer, wenn Sie es selbst tun? In den Tutorials erfahren Sie, wie Sie Haskell verwenden, aber ich sehe keine große Hilfe bei der Umwandlung von Algorithmen in schnellen Code.

Zuerst müssen Sie sicherstellen, dass Sie eine optimierte Binärdatei haben, bevor Sie glauben, dass die Sprache das Problem ist. Lesen Sie das Kapitel Profilerstellung und Optimierung in Real Wolrd Haskell. Es ist erwähnenswert, dass in den meisten Fällen die hohe Qualität der Sprache Sie zumindest einen Teil der Leistung kostet.

Beachten Sie jedoch, dass die andere Lösung nicht schneller ist, weil sie eine integrierte Funktion verwendet, sondern einfach, weil sie einen viel schnelleren Algorithmus verwendet : Um das am wenigsten verbreitete Vielfache eines Satzes von Zahlen zu finden, müssen Sie nur wenige GCDs finden. Vergleichen Sie dies mit Ihrer Lösung, die alle Zahlen von 1 bis durchläuft foldl lcm [1..20]. Wenn Sie es mit 30 versuchen, ist der Unterschied zwischen den Laufzeiten sogar noch größer.

Betrachten Sie die Komplexität: Ihr Algorithmus hat eine O(ans*N)Laufzeit, in der ansdie Antwort und Ndie Zahl angegeben sind, bis zu der Sie die Teilbarkeit überprüfen (in Ihrem Fall 20).
Der andere Algorithmus führt NZeiten lcmjedoch lcm(a,b) = a*b/gcd(a,b), und GCD hat Komplexität O(log(max(a,b))). Daher ist der zweite Algorithmus komplex O(N*log(ans)). Sie können selbst beurteilen, was schneller ist.

Um es zusammenzufassen:
Ihr Problem ist Ihr Algorithmus, nicht die Sprache.

Beachten Sie, dass es spezielle Sprachen gibt, die sowohl funktional sind als auch sich auf mathematisch anspruchsvolle Programme konzentrieren, wie Mathematica, das für mathematisch relevante Probleme wahrscheinlich schneller ist als fast alles andere. Es verfügt über eine sehr optimierte Funktionsbibliothek und unterstützt das Funktionsparadigma (zugegebenermaßen unterstützt es auch die imperative Programmierung).

Mein erster Gedanke war, dass nur Zahlen, die durch alle Primzahlen <= 20 teilbar sind, durch alle Zahlen unter 20 teilbar sind. Sie müssen also nur Zahlen berücksichtigen, die ein Vielfaches von 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 sind . Eine solche Lösung überprüft 1 / 9,699,690 so viele Zahlen wie der Brute-Force-Ansatz. Aber Ihre schnelle Haskell-Lösung kann noch mehr.

Wenn ich die "schnelle Haskell" -Lösung verstehe, verwendet sie foldl1, um die lcm-Funktion (kleinstes gemeinsames Vielfaches) auf die Liste der Zahlen von 1 bis 20 anzuwenden. Dann würde lcm 1 2 angewendet, was 2 ergibt. Dann lcm 2 3 ergibt 6 Dann lcm 6 4 ergibt 12 und so weiter. Auf diese Weise wird die lcm-Funktion nur 19 Mal aufgerufen, um Ihre Antwort zu erhalten. In der Big O-Notation sind das O (n-1) Operationen, um zu einer Lösung zu gelangen.

Ihre Slow-Haskell-Lösung geht die Nummern 1-20 für jede Nummer von 1 bis zu Ihrer Lösung durch. Wenn wir die Lösung s aufrufen, führt die Slow-Haskell-Lösung O (s * n) -Operationen aus. Wir wissen bereits, dass s über 9 Millionen beträgt, was wahrscheinlich die Langsamkeit erklärt. Selbst wenn alle Verknüpfungen und der Durchschnitt auf halbem Weg durch die Liste der Nummern 1-20 liegen, ist das immer noch nur O (s * n / 2).

Wenn headSie anrufen , können Sie diese Berechnungen nicht verhindern. Sie müssen ausgeführt werden, um die erste Lösung zu berechnen.

Danke, das war eine interessante Frage. Es hat mein Haskell-Wissen wirklich erweitert. Ich würde es überhaupt nicht beantworten können, wenn ich nicht im letzten Herbst Algorithmen studiert hätte.

Ich hatte ursprünglich nicht vor, eine Antwort zu schreiben. Aber ich wurde dazu aufgefordert, nachdem ein anderer Benutzer die seltsame Behauptung aufgestellt hatte, dass das einfache Multiplizieren der ersten Primzahlen rechenintensiver sei, als das wiederholte Anwenden lcm. Hier sind also die beiden Algorithmen und einige Benchmarks:

Mein Algorithmus:

Der Algorithmus zur Generierung von Primzahlen gibt mir eine unendliche Liste von Primzahlen.

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

Verwenden Sie nun diese Primliste, um das Ergebnis für einige zu berechnen N:

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

Jetzt ist der andere lcm-basierte Algorithmus, der zugegebenermaßen ziemlich präzise ist, hauptsächlich deshalb, weil ich die Generierung von Grund auf neu implementiert habe (und den Algorithmus für das superkurze Listenverständnis aufgrund seiner schlechten Leistung nicht verwendet habe), während er lcmeinfach aus dem importiert wurde Prelude.

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

Nun zu den Benchmarks der Code , den ich für jede verwendete war einfach: ( -prof -fprof-auto -O2dann +RTS -p)

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

Für 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

Für 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

Für 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

Ich denke, die Ergebnisse sprechen für sich.

Der Profiler gibt an, dass die Primegeneration mit nzunehmender Laufzeit immer weniger Zeit in Anspruch nimmt. Es ist also nicht der Engpass, also können wir ihn vorerst ignorieren.

Das heißt, wir vergleichen wirklich den Aufruf, lcmbei dem ein Argument von 1 nach nund das andere geometrisch von 1 nach geht ans. Zum Telefonieren *mit der gleichen Situation und dem zusätzlichen Vorteil, jede Nicht-Primzahl überspringen zu können (asymptotisch kostenlos, aufgrund des teureren Charakters von *).

Und es ist allgemein bekannt, dass *es schneller ist lcm, als lcmes wiederholte Anwendungen erfordern mod, und modasymptotisch langsamer ist ( O(n^2)vs ~O(n^1.5)).

Die obigen Ergebnisse und die kurze Analyse des Algorithmus sollten also deutlich machen, welcher Algorithmus schneller ist.