Мемоизация и задача Эйлера 15 в Хаскеле

Question

Я изучал Хаскель и решал задачи проекта Эйлера на ходу. Меня не очень беспокоит ответ на проблему Эйлера (которую я могу с радостью применить грубой силой или сделать это на каком-то другом языке), но метод.

Я застрял на выполнении Задачи 15 в разумные сроки. Он запрашивает количество маршрутов, не требующих отслеживания, от верхнего левого до нижнего правого угла сетки 20x20. Ссылка здесь

Я бы сказал, что вполне очевидно, что идея состоит в том, чтобы запомнить (sp?) Функцию, но я не совсем уверен, как это сделать. Я погуглил и наткнулся на это в кафе Haskell, которое я наивно пытался адаптировать, но в итоге получилось:

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)

Что выглядит плохо и работает ужасно (намного медленнее, чем наивная версия). Проблема в том, что я не очень понимаю, как работает запоминание на Хаскеле.

Используя мой код в качестве примера, кто-нибудь захочет объяснить а) почему мой код такой медленный
б) как это должно быть сделано (без использования изменяемых таблиц, с которым я столкнулся)
в) как работает памятка в этом случае?

Answer 1

На мой взгляд, «памятка» сильно переоценена.Не существует универсальной методики запоминания (на любом языке программирования), которая превращает каждый отдельный случай в общий расчет.Вы должны понимать каждую проблему и организовывать вещи, чтобы контролировать объем памяти, который вам нужно использовать.

В этом случае, чтобы получить количество путей для прямоугольника n x m, вам не нужнозапомните итоги для всех меньших прямоугольников, только для прямоугольников, которые на один шаг меньше в любом направлении.Таким образом, вы можете строить ряд за строкой, забывая все итоговые значения для меньших прямоугольников по ходу движения.

В Haskell лень идеально подходит для такой ситуации.Это избавляет вас от всей работы по отслеживанию того, что именно нужно запомнить и что забыть - просто вычислите бесконечную сетку итогов для всех возможных прямоугольников, и пусть Haskell сделает всю остальную работу.

Для нулевых строк у вас есть только нижняя строка.Независимо от того, как долго это будет, есть только один путь до конца, поэтому число путей равно repeat 1.

Чтобы вычислить строку в сетке из предыдущего ряда, вы начинаете с 1 (только один путь вниз, независимо от того, насколько вы высоки), затем на каждом шаге вы складываете соответствующую запись в предыдущей строке и предыдущий шаг в текущей строке.Всего у нас есть:

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

Это мгновенно вычисляет ответ для меня в приглашении GHCi.

Answer 2

Бросок за пару 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)

чтобы увидеть, что вы вообще не запомнили.

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

Повторное использование подкомпьютеров динамическое программирование .

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

Обратите внимание, что алгоритм неверен, но, по крайней мере, легко быстро получить плохой ответ!

Answer 3

Что происходит, так это то, что ваша таблица напоминаний пересчитывается при каждом вызове memRoute. Не по своей сути (к счастью!), Но, по крайней мере, работа, проделанная за один звонок, не передается остальным. Самое простое переписывание, которое я мог придумать, было:

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

Это действительно близко к вашему выраженному намерению, но я думаю, что есть лучшие способы сделать памятку, используя Data.Map и позволяя фактическому образцу вызова определять, какие значения запоминаются.