Projekt Euler prob 10 mit Haskell

Question

Okay, also habe ich eine kleine Modifikation gemacht, die Haskell eine ganze Menge Unterschied gemacht hat. Hier ist, wie es geht:

Ich implementierte das Sieb von Eratosthenes für Prob 10 von Projekt Euler. Hier ist, wie es geht:

primesBelowN :: Integer -> [Integer] 
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]] 
       where f x = foldr g True [2..truncate(sqrt(fromInteger x))] 
          where g t ac = (x `rem` t /= 0) && ac 

main = print $ sum $ primesBelowN 2000000 

es mit ghc Kompilieren, ich habe eine Laufzeit von 8,95 Sekunden zu erhalten:

$ ghc -O3 010SummationOfPrimes.hs 
$ time 010SummationOfPrimes 
142913828922 
8.739u 0.122s 0:08.95 98.8% 0+0k 2384+0io 1pf+0w 

Ich dachte, ich den Code faul Auswertung durch Ausnutzen von Haskell in der g Funktion optimieren können . Getan werden könnte (oder so dachte ich), indem einfach die ac als erstes Argument zu && platzieren, so dass sie nicht die Ungleichheit, wenn ac == False nicht berechnen:

primesBelowN :: Integer -> [Integer] 
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]] 
       where f x = foldr g True [2..truncate(sqrt(fromInteger x))] 
          where g t ac = ac && (x `rem` t /= 0) 

main = print $ sum $ primesBelowN 2000000 

Erstaunlicherweise macht das Programm 4X Langsamer!. Die Laufzeit nun deutlich größer ist 30.94s:

$ ghc -O3 010SummationOfPrimes.hs 
$ time 010SummationOfPrimes 
142913828922 
30.765u 0.157s 0:30.94 99.9% 0+0k 2384+0io 1pf+0w 

Ich habe keine Ahnung, was falsch gelaufen ist ... irgendwelche Hinweise/Anregungen/Antworten? Danke im Voraus!

EDIT

So wurde ich mit diesem zu spielen, wenn ich über eine andere Sache gestürzt. Sieht aus wie es ist leicht, in Endlosschleifen zu landen, wenn ich dies nur meine Funktion wie modulieren:

primesBelowN :: Integer -> [Integer] 
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]] 
       where f x = foldr g True [m | m <- [2..], 
               m <= truncate(sqrt(fromInteger x))] 
          where g t ac = (x `rem` t /= 0) && ac 

main = print $ sum $ primesBelowN 2000000 

Der Prozess Speicher hält nur in diesem Fall zu großen Zahlen (80Gig, bevor ich sie getötet) explodiert, ohne Ausgänge :

$ ghc -O3 010SummationOfPrimes.hs 
$ time 010SummationOfPrimes 
^C20.401u 7.994s 0:28.42 99.8% 0+0k 2384+0io 1pf+0w 

Irgendwelche Ideen, was schief läuft jetzt?

Answer 1

Zum ersten Teil der Frage merken, wie foldr betreibt:

foldr g x0 [x1, x2, x3, .., xn] = g x1 (g x2 (g x3 (..(..(g xn x0)))..) 

In unserem Fall

foldr g True [2..truncate(sqrt(fromInteger x))] 
     where g t ac = (x `rem` t /= 0) && ac 

entspricht:

foldr g True (map h [2..truncate(sqrt(fromInteger x))]) 
     where g t ac = t && ac 
      h t = x `rem` t /= 0 

was entspricht:

foldr (&&) True (map h [2..truncate(sqrt(fromInteger x))]) 
     where h t = x `rem` t /= 0 

und das wiederum ist äquivalent zu:

(h x1) && ((h x2) && ((h x3) &&(....((h xn) && True)))..) 

Denken Sie daran, dass wir mit einer faulen Sprache zu tun, in der Auswertung durch Musteranpassung geführt wird. && ist nur in seinem ersten Argument strikt, was bedeutet, dass der zweite Argumentausdruck nicht erzeugt werden muss, wenn es notwendig ist, und selbst dann muss er nur fortfahren, bis (h x2) auf der äußersten Ebene ist. Als eine solche weitere/angemessene/Darstellung ist ein solches, wie dieses (teilweise Pseudocode):

(h x1) && {instructions to generate (h x2) && ((h x3) && (....((h xn) && True)))..)} 

Als Ergebnis wird die Speicheranforderung die vollständige & & Ausdruck ist meist konstant zu berechnen. Wir müssen nur (h x1) und die Anweisungen zum Generieren der nächsten Werte beibehalten. Wenn (h x1)False ist, hören wir auf, andernfalls verwerfen wir es und erzeugen ein weiteres Paar Werte und Anweisungen. Dies ist natürlich nicht die Art, wie Hakerk tatsächlich implementiert wird, aber als Modell ausreicht.

Wenn Sie nun die Argumentreihenfolge wechseln, muss && zuerst den Ausdruck des zweiten Arguments auswerten, in dem wiederum && den nächsten Unterausdruck usw. vollständig auswerten muss, wobei alle Zwischenwerte beibehalten werden müssen der Stapel, bis der gesamte Ausdruck vollständig expandiert und nach Bedarf ausgewertet ist. Beachten Sie auch, dass die Restprüfungen in umgekehrter Reihenfolge durchgeführt werden, wodurch das Verfahren noch ineffizienter wird, da es weniger wahrscheinlich ist, dass eine zusammengesetzte Zahl ein Vielfaches einer größeren Primzahl ist als eine kleinere. Infolgedessen sind die Gesamtlaufzeit und der Speicherbedarf schlechter.

In Bezug auf den zweiten (bearbeiteten) Teil der Frage besteht das Problem darin, dass Sie keine endliche Liste mehr verwenden. Die Einschränkung des Listenverständnisses funktioniert als Filterung statt als Grenze. Um foldr mit && abzuschließen, müssen Sie entweder eine leere Liste (die mit der Definition der unendlichen Liste nicht möglich ist) oder eine Musterübereinstimmung mit einem einzelnen Element der Liste bereitstellen, für das das Prädikat False zurückgibt. Leider gibt es Fälle (x ist Primzahl), für die das Prädikat False nicht zurückgibt und foldr wird weiterhin versuchen, eine Übereinstimmung mit einem anderen Element zu finden, für das es geeignet ist. All dies ist sinnlos, da nach einem Punkt wegen der Wache keine weiteren Elemente mehr produziert werden. Es schlägt fehl, für so ziemlich die gleichen Gründe dafür, dass dies nicht gelingt:

head $ filter (const False) [1..]