Pregunta Memoization & Project Euler Problema 15 en Haskell


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. Enlace aquí

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é esta en Haskell Cafe que intenté adaptarme ingenuamente, 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)

Lo cual se ve mal, y funciona horriblemente (mucho más lento que una versión ingenua). El problema es que realmente no entiendo cómo funciona la memoización de Haskell.

Usando mi código como ejemplo, ¿a alguien le importaría explicar a) por qué el mío es tan lento?
 b) cómo debería hacerse (sin usar mutables, que fue una solución que encontré)
c) ¿Cómo funciona la memoria en este caso?


5
2017-07-31 21:11


origen


Respuestas:


Tirar en un par de trace puntos

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 has memorizado en absoluto.

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

Reutilizar subcomputas es programación dinámica.

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!


5
2017-08-01 00:07



En mi opinión, la "memoria" está muy sobrevalorada. No hay una técnica de memoria de talla única (en cualquier programación lenguaje) que convierte cada cálculo de un solo caso en un cálculo general Tienes que entender cada problema, y organiza cosas para controlar la cantidad de memoria que necesitas usar.

En este caso, para obtener el número de caminos para un n x m rectángulo, no necesita recordar los totales para todas rectángulos más pequeños, Solo para los rectángulos que son un paso más pequeños en cualquier dirección. Para que pueda acumular fila por fila, olvidando todos los totales para rectángulos más pequeños a medida que avanza.

En Haskell, la pereza es perfecta para este tipo de situación. Alivia de todo el trabajo de mantener de seguimiento de exactamente qué recordar y qué olvidar: simplemente calcula una cuadrícula infinita de los totales para Todos los rectángulos posibles, y dejar que Haskell haga el resto del trabajo.

Para cero filas, solo tienes la línea inferior. No importa cuánto tiempo sea, solo hay una única ruta hasta el final, por lo que los números de rutas son repeat 1.

Para calcular una fila en la cuadrícula de la fila anterior, comienza con 1 (solo un camino hacia abajo, no importa qué tan alto esté), A continuación, en cada paso se agrega la entrada correspondiente en el 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 forma instantánea para mí en el indicador GHCi.


10
2017-08-01 13:44



Lo que ocurre 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 pude encontrar 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

Eso se mantiene muy cerca de su intención expresada, pero creo que hay mejores maneras de hacer memoria, al usar un Data.Map y dejar que el patrón de llamada real determine qué valores se memorizan.


0
2017-08-02 15:29