8

此页面上显示了以下使用 memoization 的函数示例：

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)

但是，如果我们想记住一个多参数函数怎么办？例如，我们可以创建一个“乘法斐波那契”，定义为f(m,n) = m*f(m,n-2) + m*f(m,n-1). 我为这个“乘法斐波那契”函数修改了上面的代码，如下所示：

mult_fib :: Integer -> Int -> Integer
mult_fib mult = (map (m_fib mult) [0..] !!)
    where m_fib _ 0 = 0
          m_fib _ 1 = 1
          m_fib m n = m*(mult_fib m (n-2)) + m*(mult_fib m (n-1))

修改后的函数的运行时间是指数的，即使原始函数是线性的。为什么这种技术在第二种情况下不起作用？另外，如何修改函数以利用记忆（不使用库函数）？

4

2 回答 2

8

正如 Vitus 所说，在您的示例中可以非常简单地完成。这个想法的正确实现：

multFib :: Integer -> Int -> Integer
multFib mult = multFib'
    where multFib' = (map m_fib [0..] !!)
          m_fib 0 = 0
          m_fib 1 = 1
          m_fib n = mult * (multFib' $ n-2) + mult * (multFib' $ n-1)

但是，记忆功能不如您在此处的示例强大：它仅用于优化单个函数调用，但结果列表通常不会在multFib具有相同mult参数的后续调用之间存储。

为此，您需要对两个参数的记忆化查找进行索引，如下所示：

multFibFullMemo :: Int -> Int -> Integer
multFibFullMemo = \mult n -> memo_table !! mult !! n
 where memo_table = [ [m_fib mult' n' | n'<-[0..]] | mult' <- [0..] ]
       m_fib _ 0 = 0
       m_fib _ 1 = 1
       m_fib mult n = m * (multFibFullMemo mult $ n-2) + m * (multFibFullMemo mult $ n-1)
        where m = toInteger mult

很明显，如果您打算将它与更大的参数一起使用，这将不会有效mult：它总是需要跳到具有该数字长度的列表。

MemoTrie等库提供了不受此类问题影响的更复杂的记忆。

于 2013-08-19T00:48:39.927 回答
1

这是使用MemoTrie的版本：

import Data.MemoTrie

multFib :: Integer -> Int -> Integer          
multFib = memo2 multFib'
  where multFib' m 0 = 0
        multFib' m 1 = 1
        multFib' m n = m * (multFib m (n-2)) + m * (multFib m (n-1))
于 2013-12-26T02:09:16.757 回答