Memoization & Project Euler Problem 15 in Haskell

Question

Ich habe etwas Haskell gelernt und mache Euler-Probleme, während ich gehe. Ich bin nicht wirklich beunruhigt über die Antwort auf das Euler-Problem (das ich gerne brute, oder in einer anderen Sprache), sondern die Methode.

Ich bin auf Problem 15 in angemessener Zeit stecken. Es fragt nach der Anzahl der nicht zurückverfolgenden Routen von oben links nach unten rechts eines 20x20-Gitters. Link here

Ich würde sagen, es ist ziemlich offensichtlich, dass die Idee ist, die Funktion zu memoize (sp?), Aber ich bin nicht ganz sicher, wie es geht. Ich googeln, und kam über this auf Haskell Cafe, dass ich naiv anzupassen versucht, aber am Ende mit:

memRoute :: (Int,Int) -> Int 
memRoute (x,y) = fromJust $ lookup (x,y) $ map (\t -> (t,route t)) [(x,y) | x <- [0..20], y <- [0..20]] 

route (0,0) = 0 
route (_,0) = 1 
route (0,_) = 1 
route (x,y) = memRoute (x-1,y) + memRoute (x,y-1) 

Welche sieht schlecht aus und führt schrecklich (viel langsamer als eine naive Version). Das Problem ist, dass ich nicht wirklich verstehe, wie Haskell Memoization funktioniert.

Mit meinem Code als Beispiel, würde jemand dafür interessieren a) zu erklären, warum mein so langsam
b) ist, wie es (ohne mutables getan werden soll, was eine Lösung war ich über kam)
c) wie Die Memoisierung funktioniert in diesem Fall?

Answer 1

Toss in ein paar trace Punkte

memRoute :: (Int,Int) -> Int 
memRoute (x,y) = trace ("mem: " ++ show (x,y)) 
       fromJust $ 
       lookup (x,y) $ 
       map (\t -> (t,route t)) 
       [(x,y) | x <- [0..20], y <- [0..20]] 

route (0,0) = 0 
route (_,0) = 1 
route (0,_) = 1 
route (x,y) = trace ("route: " ++ show (x,y)) 
       memRoute (x-1,y) + memRoute (x,y-1) 

zu sehen, dass Sie überhaupt nicht memoized haben.

ghci> memRoute (2,2) 
mem: (2,2) 
route: (2,2) 
mem: (1,2) 
route: (1,2) 
mem: (0,2) 
mem: (1,1) 
route: (1,1) 
mem: (0,1) 
mem: (1,0) 
mem: (2,1) 
route: (2,1) 
mem: (1,1) 
route: (1,1) 
mem: (0,1) 
mem: (1,0) 
mem: (2,0) 
6

Weiternutzung subcomputations ist dynamic programming.

import Data.Array 

routes :: (Int,Int) -> Int 
routes = (rte !) 
    where rte = array ((1,1), (n,n)) 
        [ ((x,y), route (x,y)) | x <- [1 .. n], 
              y <- [1 .. n] ] 
     route (1,1) = 0 
     route (_,1) = 1 
     route (1,_) = 1 
     route (x,y) = rte ! (x-1,y) + rte ! (x,y-1) 
     n = 20 

Beachten Sie, dass der Algorithmus falsch ist, aber es ist einfach, schnell eine schlechte Antwort zu erhalten!

Answer 2

Meiner Meinung nach wird "Memoization" stark überbewertet. Es gibt keine one-size-fits-all Memo-Technik (in jeder Programmiersprache ), die jede Einzelfallrechnung in eine allgemeine Berechnung umwandelt. Sie müssen jedes Problem verstehen, und Dinge organisieren, um die Menge an Speicher zu steuern, die Sie benötigen zu verwenden.

In diesem Fall die Anzahl der Pfade für ein n x m Rechteck zu bekommen, Sie die Summen für alle kleinere Rechtecke nicht merken müssen, nur für die Rechtecke, die einen Schritt kleiner in jeder Richtung sind. So können Sie Zeile für Zeile aufbauen, vergessen Sie alle Summen für kleinere Rechtecke, wie Sie gehen.

In Haskell ist Faulheit perfekt für diese Art von Situation. Es entlastet Sie von all der Arbeit der Spurhaltung von genau was zu erinnern und was zu vergessen - berechnen Sie einfach ein unendliches Raster der Summen für alle möglichen Rechtecke, und lassen Sie Haskell den Rest der Arbeit tun.

Für Null-Zeilen haben Sie nur die untere Zeile. Egal wie lang es ist, gibt es nur einen einzigen Pfad bis zum Ende, so dass die Anzahl der Pfade repeat 1 ist.

auf eine Zeile in dem Raster von der vorhergehenden Zeile zu berechnen, sie mit 1 (nur einem Pfad gerade nach unten, unabhängig davon, wie hoch Sie sind) beginnen, dann bei jedem Schritt fügen Sie zusammen, um den entsprechenden Eintrag in den vorherige Zeile und der vorherige Schritt in der aktuellen Zeile. Insgesamt haben wir:

iterate (scanl (+) 1 . tail) (repeat 1) !! 20 !! 20 

Das berechnet die Antwort sofort für mich an der GHCi-Eingabeaufforderung.

Answer 3

Was passiert ist, dass Ihre Memoisierungstabelle bei jedem Aufruf von memRoute neu berechnet wird. Nicht in seiner Gesamtheit (glücklicherweise!), Aber zumindest die Arbeit, die in einem Anruf geleistet wurde, wird nicht mit dem Rest geteilt. Die einfachste Rewrite ich tun konnte, war:

memRoute = let table = map (\t -> (t,route t)) [(x,y) | x <- [0..20], y <- [0..20]] 
      in \(x,y) -> fromJust $ lookup (x,y) $ table 

Das ganz in der Nähe Ihrer ausdrücklichen Absicht bleibt, aber ich denke, es gibt bessere Möglichkeiten der memoization tun, indem Sie eine Data.Map mit und lassen die tatsächliche Anrufmuster, welche Werte bestimmen sind notiert.