Projekt Euler 23: Einblick in dieses Stack-Overflow-Programm benötigt

Question

Hallo haskell Stipendiaten. Ich arbeite gerade an der 23rd problem von Project Euler. Wo ich bei atm bin ist, dass mein Code richtig zu mir scheint - nicht in der "guten Algorithmus" Bedeutung, sondern in der "sollte funktionieren" Bedeutung - aber erzeugt einen Stack Speicherüberlauf.

Ich weiß, dass mein Algorithmus nicht perfekt ist (insbesondere könnte ich sicherlich die Berechnung eines so großen Zwischenergebnisses bei jedem Rekursionsschritt in meiner worker Funktion vermeiden).

Obwohl ich gerade dabei bin, Haskell zu lernen, würde ich gerne verstehen, warum dieser Code so kläglich versagt, um diese Art von Fehlern beim nächsten Mal zu vermeiden.

Jeder Einblick, warum dieses Programm falsch ist, wird geschätzt.

import qualified Data.List as Set ((\\)) 

main = print $ sum $ worker abundants [1..28123] 

-- Limited list of abundant numbers 
abundants :: [Int] 
abundants = filter (\x -> (sum (divisors x)) - x > x) [1..28123] 

-- Given a positive number, returns its divisors unordered. 
divisors :: Int -> [Int] 
divisors x | x > 0  = [1..squareRoot x] >>= 
          (\y -> if  mod x y == 0 
            then let d = div x y in 
              if y == d 
              then [y] 
              else [y, d] 
            else []) 
      | otherwise = [] 


worker :: [Int] -> [Int] -> [Int] 
worker (a:[]) prev = prev Set.\\ [a + a] 
worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as))) 


-- http://www.haskell.org/haskellwiki/Generic_number_type#squareRoot 
(^!) :: Num a => a -> Int -> a 
(^!) x n = x^n 

squareRoot :: Int -> Int 
squareRoot 0 = 0 
squareRoot 1 = 1 
squareRoot n = 
    let twopows = iterate (^!2) 2 
     (lowerRoot, lowerN) = 
      last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows 
     newtonStep x = div (x + div n x) 2 
     iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot) 
     isRoot r = r^!2 <= n && n < (r+1)^!2 
    in head $ dropWhile (not . isRoot) iters 

Edit: der genaue Fehler ist Stack space overflow: current size 8388608 bytes.. Erhöhen des Stack-Speicherlimits durch +RTS -K... löst das Problem nicht.

Edit2: über die sqrt-Sache, ich kopiere es einfach eingefügt aus dem Link in den Kommentaren. Um zu vermeiden, dass Integer auf das Doppelte geworfen werden muss und die Rundungsprobleme auftreten müssen ...

Answer 1

In der Zukunft ist es höflich, ein bisschen Minimalisierung auf eigene Faust zu versuchen. Zum Beispiel mit einem bisschen spielen, konnte ich feststellen, dass das folgende Programm auch Stack-Überlauf (mit 8M-Stack):

main = print (worker [1..1000] [1..1000]) 

... die wirklich Nägel gerade nach unten, was Funktion wird Sie über Verschrauben . Lassen Sie uns einen Blick auf worker nehmen:

worker (a:[]) prev = prev Set.\\ [a + a] 
worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as))) 

Auch bei meinem ersten Lese, diese Funktion in meinem Kopf roten Liste steht war, weil es Schwanz-rekursiv ist. Die Schwanzrekursion in Haskell ist im Allgemeinen keine so gute Idee wie in anderen Sprachen; Eine bewusste Rekursion (bei der Sie mindestens einen Konstruktor erzeugen, bevor Sie rekursiv arbeiten, oder eine kleine Anzahl von Wiederholungen durchführen, bevor Sie einen Konstruktor erzeugen) ist im Allgemeinen besser für eine faule Auswertung. Tatsächlich passiert hier, dass jeder rekursive Aufruf an worker im Argument prev einen tiefer und tiefer verschachtelten Thunk aufbaut. Wenn die Zeit kommt, endlich zurück zu kommen, müssen wir sehr tief in eine lange Kette von Set.\\ Anrufe gehen, um herauszufinden, was es war, was wir endlich haben.

Dieses Problem wird leicht durch die Tatsache verschleiert, dass die offensichtliche Strictness-Annotation nicht hilft. Lassen Sie uns worker massieren, bis es funktioniert. Die erste Beobachtung ist, dass die erste Klausel vollständig von der zweiten subsumiert wird. Das ist stilistisch; Es sollte das Verhalten nicht beeinflussen (außer auf leeren Listen).

worker []  prev = prev 
worker (a:as) prev = worker as (prev Set.\\ map (a+) (a:as)) 

nun die offensichtliche Strenge Anmerkung:

worker []  prev = prev 
worker (a:as) prev = prev `seq` worker as (prev Set.\\ map (a+) (a:as)) 

Ich war überrascht zu entdecken, dass diese überläuft noch stapeln! Die hinterhältige Sache ist, dass seq auf Listen nur weit genug auswertet, um zu erfahren, ob die Liste entweder [] oder _:_ entspricht.Die folgende nicht stapelbar Überlauf:

import Control.DeepSeq 

worker []  prev = prev 
worker (a:as) prev = prev `deepseq` worker as (prev Set.\\ map (a+) (a:as)) 

Ich habe nicht diese letzte Version Stecker wieder in den ursprünglichen Code, aber es zumindest arbeitet mit den minimierten main oben. By the way, können Sie die folgende Implementierung Idee gefällt, die auch überläuft stapeln:

import Control.Monad 

worker as bs = bs Set.\\ liftM2 (+) as as 

die aber durch die Verwendung Data.Set statt Data.List und keine Strikt Anmerkungen festgelegt werden kann:

import Control.Monad 
import Data.Set as Set 

worker as bs = toList (fromList bs Set.\\ fromList (liftM2 (+) as as)) 

Answer 2

Ok, Ich lud es auf und gab ihm eine Chance. Daniel Wagners Rat ist ziemlich gut, vermutlich besser als meiner. Das Problem ist in der Tat mit der Worker-Funktion, aber ich würde vorschlagen, mit Data.MemoCombinators stattdessen Ihre Funktion zu memotieren.

Auch Ihr Divisors-Algorithmus ist irgendwie albern. Es gibt einen viel besseren Weg, das zu tun. Es ist irgendwie mathy und würde viel TeX benötigen, also hier ist eine Verbindung zu einer math.stackexchange Seite, wie man das macht. Der eine, über den ich sprach, war die akzeptierte Antwort, obwohl jemand anders eine rekursive Lösung gibt, von der ich denke, dass sie schneller laufen würde. (Es erfordert keine Primfaktorzerlegung.)

https://math.stackexchange.com/questions/22721/is-there-a-formula-to-calculate-the-sum-of-all-proper-divisors-of-a-number

Answer 3

Als Daniel Wagner correctly said, das Problem ist, dass

worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as))) 

eine schlecht verschachtelte thunk baut. Sie können das vermeiden und erhalten eine etwas bessere Leistung als mit deepseq durch Ausnutzen der Tatsache, dass beide Argumente zu worker in dieser Anwendung sortiert sind. So können Sie Inkrementalausgang erhalten, indem das bei jedem Schritt alles in prev kleiner als 2*a unter Hinweis darauf, nicht die Summe von zwei reichlich Zahlen, so

worker (a:as) prev = small ++ worker as (large Set.\\ map (+ a) (a:as)) 
    where 
    (small,large) = span (< a+a) prev 

besser tun. Es ist jedoch immer noch schlecht, weil (\\) die Sortierung der beiden Listen nicht verwenden kann. Wenn Sie es mit

minus xxs@(x:xs) yys@(y:ys) 
    = case compare x y of 
     LT -> x : minus xs yys 
     EQ -> minus xs ys 
     GT -> minus xxs ys 
minus xs _ = xs    -- originally forgot the case for one empty list 

ersetzen (oder verwenden Sie die data-ordlist Paket-Version), die Set-Differenzberechnungs O (Länge) anstelle von O (Länge^2).