7

在阅读了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)

这可行，但是当我将最后一行更改为以下代码时，记忆突然无法按预期工作（程序再次变慢）：

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

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

4

2 回答 2

6

它是关于显式与隐式共享的。当你明确命名一个事物时，它自然是可以共享的，即作为单独的实体存在于内存中，并且可以重用。（当然，共享本身不是语言的一部分，我们只能稍微推动编译器共享某些东西）。

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

您的第一个变体相当于

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似乎重新引入了共享，并随之提高了速度。

于 2012-08-18T21:05:43.773 回答
3

momoized_fib = ...- 这是顶级的简单定义。它可能被读取为一个恒定的惰性值（在扩展它之前不需要绑定任何额外的参数。这有点像你的记忆值的“来源”。

当您使用(memoizer fib) (n-2)创建新的值源时，它与它没有关系，memoized_fib因此它不会被重用。实际上，由于您(map fib [0 ..])在第二个变体中产生了很多序列，因此您在这里移动了很多 GC 负载。

还要考虑更简单的例子：

f = \n -> sq !! n where sq = [x*x | x <- [0 ..]]
g n = sq !! n where sq = [x*x | x <- [0 ..]]

首先将生成单个f并与之关联，sq因为声明头中没有n。Second 将为每个不同的值生成一系列列表f n并在其上移动（不限于实际值）以获取值。

于 2012-08-18T16:37:32.673 回答