Leck im Listenprogramm

Question

Ich löse gerade einige Probleme des Projekts Euler in Haskell. Ich habe ein Programm für ein Rätsel darin geschrieben und es hat nicht so funktioniert, wie ich es erwartet hatte.

Als ich bei der Ausführung des Programms in den Task-Manager schaute, sah ich, dass es mehr als 1 Gigabyte RAM auf dem Ghc verbrauchte. Ein Freund von mir schrieb ein Programm mit der gleichen Bedeutung in Java und schaffte es in 7 Sekunden.

import Data.List

opl = find vw $ map (\x-> fromDigits (x++[0,0,9]) ) 
        $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re]

vw x = hh^2 == x
    where hh = (round.sqrt.fromIntegral) x

re = [0..9]

fromDigits x = foldl1 (\n m->10*n+m) x

Ich weiß, dass dieses Programm die gewünschte Zahl ausgeben würde, wenn es genügend Arbeitsspeicher und Zeit hätte, aber es muss doch einen besseren Weg geben.

Answer 1

Das Hauptproblem dabei ist, dass die Sequenz ein Leck hat. Sie ist wie folgt definiert:

sequence [] = [[]]
sequence (xs:xss) = [ y:ys | y <- xs, ys <- sequence xss ]

Das Problem ist also, dass die Liste, die durch den rekursiven Aufruf sequence xss wird für jedes der Elemente von xs und kann daher erst am Ende entsorgt werden. Eine Version ohne das Leck ist

myseq :: [[a]] -> [[a]]
myseq xs = go (reverse xs) []
 where
  go [] acc = [acc]
  go (xs:xss) acc = concat [ go xss (x:acc) | x <- xs ]

PS. die Antwort scheint zu sein Just 1229314359627783009

bearbeiten Version zur Vermeidung von Konkaten:

seqlists :: [[a]] -> [[a]]
seqlists xss = go (reverse xss) [] []
 where
   go []       acc rest = acc : rest
   go (xs:xss) acc rest = foldr (\y r -> go xss (y:acc) r) rest xs

Beachten Sie, dass diese beiden Versionen die Ergebnisse in einer anderen Reihenfolge als die Standardversion erzeugen sequence und können daher, obwohl sie für dieses Problem geeignet sind, nicht als eine spezielle Version von sequence .

Answer 2

In Anlehnung an die Antwort von Simon Marlow hier eine Version der Sequenz, die das Leerzeichen vermeidet und ansonsten genau wie das Original funktioniert, einschließlich der Beibehaltung der Reihenfolge.

Der einzige Unterschied besteht darin, dass eine gefälschte Datenabhängigkeit eingeführt wird, die verhindert, dass der rekursive Aufruf gemeinsam genutzt wird.

sequenceDummy d [] = d `seq` [[]]
sequenceDummy _ (xs:xss) = [ y:ys | y <- xs, ys <- sequenceDummy (Just y) xss ]

sequenceUnshared = sequenceDummy Nothing

Ich denke, dass dies ein besserer Weg ist, um die gemeinsame Nutzung zu vermeiden, die zu einem Raumleck führt.

Ich würde das übermäßige Teilen auf die Umwandlung in "völlige Faulheit" schieben. Normalerweise ist diese Transformation sehr gut geeignet, um eine gemeinsame Nutzung zu ermöglichen, die Neukompositionen vermeidet, aber manchmal ist eine Neukomposition sehr viel effizienter als die Speicherung gemeinsamer Ergebnisse.

Es wäre schön, wenn es eine direktere Möglichkeit gäbe, dem Compiler mitzuteilen, dass er einen bestimmten Ausdruck nicht teilen soll - der obige Dummy Maybe Argument funktioniert und ist effizient, aber es ist im Grunde ein Hack, der gerade kompliziert genug ist, dass ghc nicht erkennen kann, dass es keine echte Abhängigkeit gibt. (In einer strikten Sprache haben Sie diese Probleme nicht, weil Sie nur Sharing haben, wo Sie eine Variable explizit an einen Wert binden).

Answer 3

EDIT: Ich glaube, ich bin hier falsch - ich ändere die Typsignatur in :: Vielleicht Word64 (was genug Bits für dieses Problem wäre, denke ich) dauert auch ewig / hat ein Leck, so dass es nicht der alte Integer-Bug sein könnte.

Ihr Problem scheint ein alter GHC-Bug zu sein (von dem ich dachte, er sei behoben), bei dem Integer ein Leck verursacht. Der folgende Code endet in etwa 150 ms, wenn mit -O2 kompiliert.

import Data.List
import Data.Word

main = print opl

opl :: Maybe Word32
opl = find vw $ map (\x-> fromDigits (x++[0,0,9]) ) $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re]

vw x = hh^2 == x
    where hh = (round.sqrt.fromIntegral) x

re = [0..9]

fromDigits x = foldl1 (\n m->10*n+m) x

Answer 4

Da Sie nach einer neunzehnstelligen Zahl mit den Merkmalen von vw suchen, würde ich versuchen, die Konstruktion in der abgebildeten Funktion zu vereinfachen, indem ich einfach sage fromDigits x*1000+9 für den Anfang. Das Anhängen an eine Liste ist O(Länge-der-linken-Liste), so dass das Anhängen der letzten drei Ziffern am Ende die Berechnungszeit erheblich verkürzt.

Nebenbei bemerkt (für Sie beide): Wenn Sie die strenge Version der Falte ( foldl1' ) wird ebenfalls helfen.