Какие функции кэшируются в Haskell? - PullRequest
Новая
       16

Какие функции кэшируются в Haskell?

0 голосов
/ 28 октября 2018

У меня есть следующий код: 

memoize f = (map f [0 ..] !!)

fib' 0 = 1
fib' 1 = 1
fib' n = fib' (n - 1) + fib' (n - 2)

fibMemo n = memoize fib' n
fibMemo'  = memoize fib'

(я знаю, что реализация Фибоначчи имеет экспоненциальную временную сложность и не использует кэш)

При первом выполнении fibmemo' 30 это занимает 3 секунды, а второй раз - ~ 0 секунд, потому что результат кэшируется.Но первая версия, fibmemo, не получает результат в кеше, выполнение всегда занимает 3 секунды.Единственное отличие - это определение (которое, насколько я знаю, эквивалентно).

Итак, мой вопрос: какие функции кэшируются в Haskell?

Я уже прочитал https://wiki.haskell.org/Memoization и не решает мой вопрос.

1 Ответ

0 голосов
/ 28 октября 2018

По существу, определенные вами функции ведут себя следующим образом: 

fibMemo n = let m = map fib' [0..] in m !! n
fibMemo'  = let m = map fib' [0..] in (m !!)

Почему fibMmemo' более эффективен?Что ж, мы можем переписать его как 

fibMemo'  = let m = map fib' [0..] in \n -> m !! n

, что делает более понятным, что единый список m создается до того, как n будет взята в качестве ввода.Это означает, что все вызовы fibMemo' будут использовать один и тот же m.Первый вызов оценивает часть m медленно, и последующие вызовы будут повторно использовать этот кэшированный результат (конечно, при условии, что вызов попадает в кэш, в противном случае другая часть m оценивается и кэшируется).

Вместо этого fibMemo эквивалентно 

fibMemo = \n -> let m = map fib' [0..] in m !! n

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

Порядок лямбды \n -> против let m = .. имеет большое значение всроки исполнения.Поскольку m = .. не использует n, технически let m = .. может быть перемещен наружу, по существу превращая fibMemo в fibMemo', не затрагивая семантику.Однако, как вы обнаружили, в целом это не сохраняет производительность!

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

...