Memoization & Project Euler Problema 15 en Haskell

Question

He estado aprendiendo algo de Haskell, y estoy haciendo proyectos de problemas de Euler a medida que avanzo. Realmente no me molesta la respuesta al problema de Euler (que felizmente puedo usar como fuerza bruta, o hacerlo en otro idioma), sino el método.

Estoy atascado en hacer el problema 15 en un tiempo razonable. Solicita la cantidad de rutas que no retroceden desde la parte superior izquierda hasta la parte inferior derecha de una cuadrícula de 20x20. Link here

Yo diría que es bastante obvio que la idea es memorizar (sp?) La función, pero no estoy seguro de cómo hacerlo. Busqué en Google y encontré this en Haskell Cafe que ingenuamente intentado adaptarse, pero terminó con:

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) 

¿Qué se ve mal, y realiza horrible (mucho más lento que una versión ingenua). El problema es que realmente no entiendo cómo funciona la memoria de Haskell.

Usando mi código como un ejemplo, alguien le importa explicar a) por qué la mía es tan lento
b) la forma en que debe hacerse (sin utilizar mutables, que era una solución que me encontré)
c) cómo la memorización funciona en este caso?

Answer 1

Toss en un par de puntos trace

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) 

para ver que no haya memoized en absoluto.

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

subcomputaciones La reutilización es 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 

Tenga en cuenta que el algoritmo es incorrecto, pero al menos es fácil obtener una respuesta incorrecta rápidamente.

Answer 2

En mi opinión, la "memoria" está muy sobrevalorada. No existe una técnica de memorización de un tamaño para todos ( ) (en cualquier lenguaje de programación ) que convierta cada cálculo de caso único en un cálculo general . Debe comprender cada problema, y organizar cosas para controlar la cantidad de memoria que necesita para usar.

En este caso, para obtener el número de caminos para un rectángulo n x m, que no es necesario recordar los totales de todas las rectángulos más pequeños, sólo por los rectángulos que son un paso más pequeño en una u otra dirección. Para que pueda construir fila por fila, olvidando todos los totales para rectángulos más pequeños sobre la marcha.

En Haskell, la pereza es perfecta para este tipo de situación. Alivia de todo el trabajo de mantener un registro de exactamente qué recordar y qué olvidar, simplemente calcule una grilla infinita de los totales para todos los rectángulos posibles, y deje que Haskell haga el resto del trabajo.

Para filas cero, solo tiene la línea inferior. No importa cuánto dure, solo hay una ruta al final, por lo que el número de rutas es repeat 1.

para calcular una fila de la cuadrícula de la fila anterior, se empieza con 1 (sólo un camino recto hacia abajo, no importa qué tan alto que lo son), continuación, en cada paso que se suman a la entrada correspondiente en la fila anterior y el paso anterior en la fila actual. En total, tenemos:

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

Eso calcula la respuesta de manera instantánea para mí en el prompt de GHCi.

Answer 3

Lo que sucede es que su tabla de memorización se vuelve a calcular en cada llamada a memRoute. No en su totalidad (¡afortunadamente!) Pero al menos el trabajo hecho en una llamada no se comparte con el resto. La reescritura más simple que pudiera venir fue:

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

que se queda muy cerca de su intención expresa, pero creo que hay mejores formas de hacer memoization, mediante el uso de un Data.Map y dejar que el patrón de llamada real a determinar qué valores son memorados