在非整数键上有效地实现记忆化

Question

我是 Haskell 的新手，一直在通过一些简单的编程挑战来练习。最近 2 天，我一直在尝试实现 the unbounded knapsack problem here. The algorithm I'm using is described on the wikipedia page，尽管对于这个问题，单词 'weight' 被替换为单词 'length'。无论如何，我是从没有记忆的情况下开始编写代码的：

maxValue :: [(Int,Int)] -> Int -> Int
maxValue [] len = 0
maxValue ((l, val): other) len =
    if l > len then 
        skipValue
    else 
        max skipValue takeValue
    where skipValue = maxValue other len
          takeValue = (val + maxValue ([(l, val)] ++ other) (len - l)

我曾希望 haskell 会很好并且有一些像 #pragma memoize 这样的语法来帮助我，但是环顾四周的例子，解决方案是用 this fibonacci problem code 解释的。

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)

在掌握了这个例子背后的概念之后，我感到非常失望 - 使用的方法非常老套，并且只有在 1) 函数的输入是单个整数，以及 2) 函数需要计算值时才有效按 f(0), f(1), f(2), ... 的顺序递归但是如果我的参数是向量或集合呢？ ~~如果我想记住像 f(n) = f(n/2) + f(n/3) 这样的函数，我需要为所有小于 n 的 i 计算 f(i) 的值，而我不需要这些值中的大部分。~~ （其他人指出此说法是错误的）

我尝试通过传递一个备忘录 table 来实现我想要的，我们慢慢将其作为额外参数填写：

maxValue :: (Map.Map (Int, Int) Int) -> [(Int,Int)] -> Int -> (Map.Map (Int, Int) Int, Int)
maxValue m [] len = (m, 0)
maxValue m ((l, val) : other) len =
    if l > len then
        (mapWithSkip, skipValue)
    else
        (mapUnion, max skipValue (takeValue+val))
    where (skipMap, skipValue) = maxValue m other len
          mapWithSkip = Map.insertWith' max (1 + length other, len) skipValue skipMap
          (takeMap, takeValue) = maxValue m ([(l, val)] ++ other) (len - l)
          mapWithTake = Map.insertWith' max (1 + length other, len) (takeValue+val) mapWithSkip
          mapUnion = Map.union mapWithSkip mapWithTake

但这太慢了，我相信是因为 Map.union takes too long, it's O(n+m) 而不是 O(min(n,m))。此外，这段代码对于像 memoizaton 这样简单的东西来说似乎相当混乱。对于这个特定的问题，您可以将 hacky 方法推广到二维，并进行一些额外的计算，但我想知道如何在更一般的意义上进行记忆。如何以这种更通用的形式实现记忆，同时保持与命令式语言中的代码相同的复杂性？

Answer 1

And if I want to memoize a function like f(n) = f(n/2) + f(n/3), I need to compute the value of f(i) for all i less than n, when I don't need most of those values.

不，惰性意味着永远不会计算未使用的值。你为它们分配一个 thunk 以防它们被使用，所以它是一个非零数量的 CPU 和 RAM 专用于这个未使用的值，但是例如计算 f 6 永远不会导致计算 f 5。所以假设计算一个item的开销比分配一个cons cell的开销高很多，并且你最终查看的是总可能值的很大一部分，这种方法使用的浪费工作很小。

But what if my parameters are vectors or sets?

使用相同的技术，但数据结构与列表不同。映射是最通用的方法，前提是您的键是 Ord，并且您可以枚举所有需要查找的键。

如果你不能枚举所有的键，或者你打算查找比可能的总数少很多的键，那么你可以使用State（或ST）来模拟共享可写记忆缓存的命令式过程在函数调用之间。

我很想向您展示这是如何工作的，但我发现您的问题陈述/link令人困惑。您 link 所做的练习似乎等同于您 link 进行的维基百科文章中的 UKP，但我在那篇文章中没有看到任何看起来像您的实现的内容。维基百科提供的“动态编程预先算法”明确设计为具有与您提供的 fib 记忆示例完全相同的属性。键是一个 Int，数组是从左到右构建的：以 len=0 作为基本情况，所有其他计算都基于已计算的值。出于某种我不明白的原因，它似乎还假设您将至少拥有每个合法大小对象的 1 个副本，而不是至少 0 个；但如果你有不同的约束，这很容易解决。

你实现的是完全不同的，从总 len 开始，然后为每个 (length, value) 步骤选择要切割多少个大小 length 的片段，然后用更小的 len 递归并从您的权重值列表中删除前面的项目。它更接近于传统的“给定这些面额的货币，您可以通过多少种方式找零”的问题。这也适用于与 fib 相同的从左到右的记忆方法，但在两个维度上（一个维度是要找零的货币数量，另一个维度是剩余要使用的面额数量） .

Answer 2

我在 Haskell 中进行记忆的常用方法通常是 MemoTrie。它非常简单、纯粹，而且通常可以满足我的需求。

不用多想，你可以得出：

import Data.MemoTrie (memo2)
maxValue :: [(Int,Int)] -> Int -> Int
maxValue = memo2 go
  where
    go [] len = 0
    go lst@((l, val):other) len =
      if l > len then skipValue else max skipValue takeValue
      where
        skipValue = maxValue other len
        takeValue = val + maxValue lst (len - l)

我没有你的输入，所以我不知道这会进行多快 — 记住 [(Int,Int)] 输入有点奇怪。我想您也认识到这一点，因为在您自己的尝试中，您 实际上 记忆了列表的长度，而不是列表本身。如果你想这样做，将你的列表转换为一个常量时间查找数组然后记忆是有意义的。这是我想出的：

import qualified GHC.Arr as Arr

maxValue :: [(Int,Int)] -> Int -> Int
maxValue lst = memo2 go 0
  where
    values = Arr.listArray (0, length lst - 1) lst
    go i _ | i >= length lst = 0
    go i len = if l > len then skipValue else max skipValue takeValue
      where
        (l, val) = values Arr.! i
        skipValue = go (i+1) len
        takeValue = val + go i (len - l)

Answer 3

一般来说，Haskell 中的运行-of-the-mill memoization 可以像在其他语言中一样实现，通过在可变映射上关闭函数的 memoized 版本缓存值。如果你想运行像纯函数一样方便地使用函数，你需要在 IO 中维护状态并使用 unsafePerformIO.

下面的memoizer对于大多数代码提交网站来说可能就足够了，因为它只依赖于System.IO.Unsafe、Data.IORef和Data.Map.Strict，这些通常应该是可用的。

import qualified Data.Map.Strict as Map
import System.IO.Unsafe
import Data.IORef

memo :: (Ord k) => (k -> v) -> (k -> v)
memo f = unsafePerformIO $ do
  m <- newIORef Map.empty
  return $ \k -> unsafePerformIO $ do
    mv <- Map.lookup k <$> readIORef m
    case mv of
      Just v -> return v
      Nothing -> do
        let v = f k
        v `seq` modifyIORef' m $ Map.insert k v
        return v

从你的问题和评论来看，你似乎是那种永远失望 (!) 的人，所以使用 unsafePerformIO 可能会让你失望，但如果 GHC 实际上提供了一个记忆 pragma，这个可能是它在幕后所做的事情。

直接使用的例子：

fib :: Int -> Int
fib = memo fib'
  where fib' 0 = 0
        fib' 1 = 1
        fib' n = fib (n-1) + fib (n-2)

main = do
  print $ fib 100000

或更重要的一点（剧透？！），你的 maxValue 的版本仅在长度上记忆：

maxValue :: [(Int,Int)] -> Int -> Int
maxValue values = go
  where go = memo (go' values)
        go' [] len = 0
        go' ((l, val): other) len =
          if l > len then
              skipValue
          else
              max skipValue takeValue
          where skipValue = go' other len
                takeValue = val + go (len - l)

这比必要的工作多了一点，因为 takeValue 案例重新评估了整套适销对路的作品，但它的速度足以通过链接网页上的所有测试用例。如果它不够快，那么你需要一个记忆器来记忆一个函数，其结果在具有不同参数的调用之间共享（长度相同，但可销售的部分不同，你知道答案无论如何都会相同由于问题的特殊方面以及您检查不同适销产品和长度的顺序）。这将是一个非标准的记忆，但修改 memo 函数来处理这种情况并不难，我不认为，只需将参数拆分为一个“关键”参数和一个“非键”参数，或通过在记忆时提供的任意函数从参数派生键。

在非整数键上有效地实现记忆化

Implementing Memoization efficiently on nonintegral keys

performance

haskell

dynamic-programming

memoization

knapsack-problem