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

Question

我是 Haskell 的新手，一直在通过一些简单的编程挑战来练习。最近 2 天，我一直在尝试实现 the unbounded knapsack problem here.我正在使用的算法描述为 on the wikipedia page ，尽管对于这个问题，“重量”一词被替换为“长度”一词。无论如何，我是在没有内存的情况下开始编写代码的:

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) 这样的函数，我需要计算 f( i) 对于所有小于 n 的 i，当我不需要这些值中的大部分时。(其他人指出这种说法是错误的)

我尝试通过传递我们作为额外参数慢慢填充的备忘录表来实现我想要的:

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。因此，假设计算一个项目的开销远高于分配一个 cons cell 的开销，并且您最终查看的可能值占总可能值的很大一部分，则此方法使用的浪费工作很小。

But what if my parameters are vectors or sets?

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

如果您不能枚举所有键，或者您计划查找比可能的总数少得多的键，那么您可以使用 State(或 ST)来模拟在调用之间共享可写内存缓存的命令式过程你的功能。

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

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