为什么记忆不起作用？

Question

在阅读了memoization介绍之后,我通过使用更通用的memoize函数重新实现了Fibonacci示例(仅用于学习目的):

memoizer :: (Int -> Integer) -> Int -> Integer
memoizer f = (map f [0 ..] !!)

memoized_fib :: Int -> Integer
memoized_fib = memoizer fib
    where fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)

这有效,但是当我将最后一行更改为以下代码时,memoization突然无法正常工作(程序再次变慢):

          fib n = memoizer fib (n-2) + memoizer fib (n-1)

记忆化的关键区别在哪里？

Answer 1

它是关于显式与隐式共享.当你明确地命名一个东西时,它自然可以被共享,即在内存中作为单独的实体存在,并被重用._{(当然,共享不是语言本身的一部分,我们只能轻微地推动编译器分享某些事情).}

但是当您将相同的表达式写入两次或三次时,您依赖编译器将公共子表达式替换为一个显式共享实体.那可能会也可能不会发生.

你的第一个变种相当于

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)  where
        fib 0 = 0
        fib 1 = 1
        fib n = memoized_fib (n-2) + memoized_fib (n-1)

在这里,您专门命名一个实体,并通过该名称引用它.但这是一个功能.为了使重用更加确定,我们可以明确地命名在此处共享的实际值列表:

memoized_fib :: Int -> Integer
memoized_fib = (fibs !!)  where
        fibs = map fib [0 ..] 
        fib 0 = 0
        fib 1 = 1
        fib n = memoized_fib (n-2) + memoized_fib (n-1)

最后一行可以在视觉上更明显,明确引用此处共享的实际实体 - fibs我们在上面的步骤中命名的列表:

        fib n = fibs !! (n-2) + fibs !! (n-1)

您的第二个变体等同于:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)  where
        fib 0 = 0
        fib 1 = 1
        fib n = (map fib [0 ..] !!) (n-2) + (map fib [0 ..] !!) (n-1)

这里我们有三个看似独立的map表达式,它们可能会或可能不会被编译器共享.编译它ghc -O2似乎重新引入共享,并与它一起速度.