互联网上有一些用于各种不同语言的自动记忆库；但如果不知道它们的用途、使用地点以及它们的工作原理，就很难看到它们的价值。使用记忆化有哪些令人信服的论据，记忆化在哪些问题领域特别突出？不知情的信息将在这里特别感激。
问问题
6093 次
12 回答
22
在我看来，斐波那契和阶乘计算并不是最好的例子。当您拥有以下条件时，记忆就会真正发挥作用：
- 有问题的计算的潜在输入范围很大，但范围仍然受到明显限制和已知
- 您提前知道该程序的任何实际使用只会使用一小部分可能的输入来进行计算（斐波那契和阶乘失败）
- 您不知道在运行时将使用哪些特定输入，因此需要记住哪些特定结果（斐波那契和阶乘在某种程度上也失败了）
显然，如果您确实知道所有可能的输入，并且空间允许，您可以考虑用查找替换该函数（例如，对于具有已知生成器的嵌入式 CRC32 实现，我会这样做）。
...甚至比 #2 更好的是，如果对于程序的任何特定运行，您可以立即说“潜在输入的范围将被限制为满足这些条件的子集......”。
请注意，其中很多可能是概率性的（或直观的）——当然，有人可能会尝试所有 10^13 种可能的输入来进行魔术计算，但您知道实际上他们不会。如果他们这样做了，记忆的开销实际上对他们没有好处。但是您可能会认为这是可以接受的，或者在这种情况下允许绕过记忆。
这是一个例子，我希望它不会太复杂（或概括）而无法提供信息。
在我编写的某些固件中，程序的一部分从 ADC 读取，该 ADC 可以是任何数字0x000，0xFFF并计算程序其他部分的输出。此计算还采用一组用户可调的数字，但这些仅在程序启动时读取。这个计算在第一次运行时就很受欢迎。
提前创建查找表是荒谬的。输入域是 [ 0x000, ..., 0xFFF] 和（大范围的浮点值）和（另一个大范围...）和 ... 的笛卡尔积。不，谢谢。
但是，没有用户要求或期望设备在条件迅速变化时运行良好，他们更希望在情况稳定时运行得更好。因此，我在反映这些要求的计算行为上进行了权衡：我希望当事情稳定时这个计算又好又快，而我不在乎什么时候不稳定。
鉴于典型用户期望的“缓慢变化条件”的定义，ADC 值将稳定到特定值并保持在其稳定值的大约 0x010 范围内。哪个值取决于条件。
因此，可以为这 16 个潜在输入存储计算结果。如果环境条件的变化比预期的要快，则从最近读取的“最远”ADC 将被丢弃（例如，如果我已将 0x210 缓存到 0x21F，然后读取 0x222，则删除 0x210 结果）。
这里的缺点是，如果环境条件发生很大变化，那么已经很慢的计算运行速度会慢一些。我们已经确定这是一个不寻常的用例，但如果后来有人透露，他们确实想在异常不稳定的条件下操作它，我可以实现一种绕过记忆的方法。
于 2010-07-14T02:28:30.863 回答
21
这里流行的阶乘答案是一个玩具答案。是的，记忆化对于重复调用该函数很有用，但这种关系是微不足道的——在“print factorial(N) for 0..M”的情况下，你只是重用了最后一个值。
这里的许多其他示例只是“缓存”。这很有用，但它忽略了 memoization 这个词为我带来的令人敬畏的算法含义。
更有趣的是，递归函数的单次调用的不同分支遇到相同的子问题，但采用非平凡的模式，因此实际索引到某个缓存实际上是有用的。
例如，考虑绝对值总和为 k 的 n 维整数数组。例如，对于 n=3,k=5 [1,-4,0], [3,-1,1], [5,0,0], [0,5,0] 将是一些示例。令 V(n,k) 为给定 n,k 的可能唯一数组的数量。它的定义是：
V(n,0)=1; V(0,k)=0; V(n,k) = V(n-1,k) + V(n,k-1) + V(n-1,k-1);
对于 n=3,k=5，此函数给出 102。
如果没有记忆，即使是相当适度的数字，计算起来也会很快变得很慢。如果您将处理可视化为一棵树，则每个节点调用 V() 扩展为三个子节点，您将有 186,268,135,991,213,676,920,832 V(n,0)=1 在 V(32,32) 的计算中离开......天真地实现这个函数在可用硬件上很快变得无法计算。
但是树中的许多子分支是彼此完全相同的副本，尽管不是以某种像阶乘函数那样容易被消除的微不足道的方式。通过记忆化，我们可以合并所有这些重复的分支。事实上，使用记忆 V(32,32) 仅执行 V() 1024 (n*m) 次，这是 10^21 倍的加速（显然随着 n,k 的增长而变大）左右作为交换对于相当少量的内存。:) 我发现这种对算法复杂性的根本性改变比简单的缓存更令人兴奋。它可以使棘手的问题变得容易。
因为 python 数字自然是 bignums，所以你可以在 python 中使用字典和元组键在 9 行中使用 memoization 来实现这个公式。试一试，在没有记忆的情况下试一试。
于 2010-07-14T05:57:20.797 回答
13
记忆是存储子问题答案的技术，因此程序以后不需要重新解决相同的子问题。
它通常是使用动态规划解决问题的一项重要技术。
想象一下枚举从网格左上角到网格右下角的所有路径。许多路径相互重叠。您可以记住为网格上的每个点计算的解决方案，从右下角构建，回到左上角。这将计算时间从“荒谬”降低到“易处理”。
另一个用途是：列出数字 0 到 100 的阶乘。您不想计算 100！使用100 * 99 * ... * 1. 你已经计算过了99!，所以重复使用那个答案，然后简单地乘以100答案99!。您可以在每个步骤中记住答案（从 1 到 100），以节省大量计算。
对于数据点，对于我上面的网格解决问题（问题来自编程挑战）：
备忘：
real 0m3.128s
user 0m1.120s
sys 0m0.064s
非记忆（我杀了，因为我厌倦了等待......所以这是不完整的）
real 24m6.513s
user 23m52.478s
sys 0m6.040s
于 2010-07-14T00:51:42.983 回答
11
记忆化在可以重用子问题的解决方案的问题中大放异彩。简单地说，它是一种缓存形式。让我们以阶乘函数为例。
3！它本身就是一个问题，但它也是 n! 的一个子问题！其中 n > 3 例如4! = 4 * 3! 计算阶乘的函数可以在记忆化中表现得更好，因为它只会计算 3！一次并将结果内部存储在哈希表中。每当遇到3！它将再次在表中查找值而不是重新计算它。
任何可以重用子问题解决方案的问题（越频繁越好）都是使用记忆的候选者。
于 2010-07-14T00:47:53.053 回答
7
记忆以时间换空间。
当应用于本质上是多递归的问题时，记忆可以将指数时间（或更糟）变成线性时间（或更好）。成本通常是 O(n) 空间。
经典的例子是计算斐波那契数列。教科书的定义是递归关系：
F(n) = F(n-1) + F(n-2)
天真地实现，它看起来像这样：
int fib(int n) {
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
else {
return fib(n-1) + fib(n-2);
}
}
您可以看到运行时间随着 n 呈指数增长，因为每个部分和都被计算多次。
使用 memoization 实现，它看起来像这样（笨拙但实用）：
int fib(int n) {
static bool initialized = false;
static std::vector<int> memo;
if (!initialized) {
memo.push_back(0);
memo.push_back(1);
initialized = true;
}
if (memo.size() > n) {
return memo[n];
}
else {
const int val = fib(n-1) + fib(n-2);
memo.push_back(val);
return val;
}
}
在我的笔记本电脑上计时这两个实现，对于 n = 42，天真的版本需要 6.5 秒。记忆的版本需要 0.005 秒（所有系统时间——也就是说，它是 I/O 绑定的）。对于 n = 50，memoized 版本仍然需要 0.005 秒，而 naive 版本最终在 5 分 7 秒后完成（不要介意它们都溢出了一个 32 位整数）。
于 2010-07-14T01:23:45.943 回答
4
记忆可以从根本上加速算法。经典的例子是 Fibonocci 系列，其中递归算法非常慢，但 memoization 自动使其与迭代版本一样快。
于 2010-07-14T00:52:52.127 回答
4
一种记忆形式的用途之一是在博弈树分析中。在分析非平凡的博弈树（想想国际象棋、围棋、桥牌）中，计算位置的价值是一项非平凡的任务，并且可能需要大量时间。一个天真的实现会简单地使用这个结果然后丢弃它，但所有强大的玩家都会存储它并在情况再次出现时使用它。你可以想象在国际象棋中有无数种方法可以达到相同的位置。
在实践中实现这一点需要无休止的实验和调整，但可以肯定地说，如果没有这种技术，计算机国际象棋程序就不会是今天的样子。
在人工智能中，这种记忆的使用通常被称为“转置表”。
于 2010-07-14T03:02:16.727 回答
3
记忆化本质上是缓存给定输入的函数的返回值。如果您要使用相同的输入多次重复函数调用，这很有用，特别是如果函数需要一些时间来执行。当然，由于数据必须存储在某个地方，记忆化将使用更多的内存。这是使用 CPU 和使用 RAM 之间的权衡。
于 2010-07-14T00:49:45.543 回答
2
在将数据从一个系统迁移到另一个系统（ETL）时，我一直使用记忆。这个概念是，如果一个函数总是为同一组输入返回相同的输出，那么缓存结果可能是有意义的——特别是如果计算该结果需要一段时间。在进行 ETL 时，您通常会在大量数据上多次重复相同的操作，而性能通常很关键。当性能不是问题或可以忽略不计时，记住您的方法可能没有意义。像任何事情一样，为工作使用正确的工具。
于 2010-07-14T00:48:52.657 回答
1
我想大多数人都已经涵盖了记忆的基础知识，但我会给你一些实际的例子，这些例子可以用来做一些非常了不起的事情（恕我直言）：
- 在 C# 中，您可以反映一个函数并为其创建一个委托，然后您可以动态调用该委托……但这真的很慢！它比直接调用该方法慢大约 30 倍。如果您记住方法调用，那么您可以使调用几乎与直接调用方法一样快。
- 在遗传编程中，它可以减少对种群中成百上千的样本重复调用具有相似输入参数的相同函数的开销。
- 在表达式树的执行中：如果您已经记住了表达式树，则不必继续重新评估它...
当然还有更多可以使用记忆的实际示例，但这只是其中的一小部分。
于 2010-07-14T04:55:21.230 回答
1
作为如何使用 memoization 来提高算法性能的示例，对于这个特定的测试用例，以下运行速度大约快300倍。之前，大约需要 200秒；2/3记住了。
class Slice:
__slots__ = 'prefix', 'root', 'suffix'
def __init__(self, prefix, root, suffix):
self.prefix = prefix
self.root = root
self.suffix = suffix
################################################################################
class Match:
__slots__ = 'a', 'b', 'prefix', 'suffix', 'value'
def __init__(self, a, b, prefix, suffix, value):
self.a = a
self.b = b
self.prefix = prefix
self.suffix = suffix
self.value = value
################################################################################
class Tree:
__slots__ = 'nodes', 'index', 'value'
def __init__(self, nodes, index, value):
self.nodes = nodes
self.index = index
self.value = value
################################################################################
def old_search(a, b):
# Initialize startup variables.
nodes, index = [], []
a_size, b_size = len(a), len(b)
# Begin to slice the sequences.
for size in range(min(a_size, b_size), 0, -1):
for a_addr in range(a_size - size + 1):
# Slice "a" at address and end.
a_term = a_addr + size
a_root = a[a_addr:a_term]
for b_addr in range(b_size - size + 1):
# Slice "b" at address and end.
b_term = b_addr + size
b_root = b[b_addr:b_term]
# Find out if slices are equal.
if a_root == b_root:
# Create prefix tree to search.
a_pref, b_pref = a[:a_addr], b[:b_addr]
p_tree = old_search(a_pref, b_pref)
# Create suffix tree to search.
a_suff, b_suff = a[a_term:], b[b_term:]
s_tree = old_search(a_suff, b_suff)
# Make completed slice objects.
a_slic = Slice(a_pref, a_root, a_suff)
b_slic = Slice(b_pref, b_root, b_suff)
# Finish the match calculation.
value = size + p_tree.value + s_tree.value
match = Match(a_slic, b_slic, p_tree, s_tree, value)
# Append results to tree lists.
nodes.append(match)
index.append(value)
# Return largest matches found.
if nodes:
return Tree(nodes, index, max(index))
# Give caller null tree object.
return Tree(nodes, index, 0)
################################################################################
def search(memo, a, b):
# Initialize startup variables.
nodes, index = [], []
a_size, b_size = len(a), len(b)
# Begin to slice the sequences.
for size in range(min(a_size, b_size), 0, -1):
for a_addr in range(a_size - size + 1):
# Slice "a" at address and end.
a_term = a_addr + size
a_root = a[a_addr:a_term]
for b_addr in range(b_size - size + 1):
# Slice "b" at address and end.
b_term = b_addr + size
b_root = b[b_addr:b_term]
# Find out if slices are equal.
if a_root == b_root:
# Create prefix tree to search.
key = a_pref, b_pref = a[:a_addr], b[:b_addr]
if key not in memo:
memo[key] = search(memo, a_pref, b_pref)
p_tree = memo[key]
# Create suffix tree to search.
key = a_suff, b_suff = a[a_term:], b[b_term:]
if key not in memo:
memo[key] = search(memo, a_suff, b_suff)
s_tree = memo[key]
# Make completed slice objects.
a_slic = Slice(a_pref, a_root, a_suff)
b_slic = Slice(b_pref, b_root, b_suff)
# Finish the match calculation.
value = size + p_tree.value + s_tree.value
match = Match(a_slic, b_slic, p_tree, s_tree, value)
# Append results to tree lists.
nodes.append(match)
index.append(value)
# Return largest matches found.
if nodes:
return Tree(nodes, index, max(index))
# Give caller null tree object.
return Tree(nodes, index, 0)
################################################################################
import time
a = tuple(range(50))
b = (48, 11, 5, 22, 28, 31, 14, 18, 7, 29, 49, 44, 47, 36, 25, 27,
34, 10, 38, 15, 21, 16, 35, 20, 45, 2, 37, 33, 6, 30, 0, 8, 13,
43, 32, 1, 40, 26, 24, 42, 39, 9, 12, 17, 46, 4, 23, 3, 19, 41)
start = time.clock()
old_search(a, b)
stop = time.clock()
print('old_search() =', stop - start)
start = time.clock()
search({}, a, b)
stop = time.clock()
print('search() =', stop - start)
于 2010-07-18T18:46:11.567 回答
-7
记忆只是缓存的一个花哨的词。如果您的计算比从缓存中提取信息更昂贵，那么这是一件好事。问题是 CPU 速度快，内存速度慢。所以我发现使用记忆通常比重做计算要慢得多。
当然，还有其他可用的技术确实可以为您带来显着的改进。如果我知道循环的每次迭代都需要 f(10)，那么我会将其存储在一个变量中。由于没有缓存查找，这通常是一个胜利。
编辑
来吧，随心所欲地对我投反对票。这不会改变您需要进行真正的基准测试而不是盲目地开始将所有内容放入哈希表中的事实。
如果您在编译时知道您的值范围，就说因为您使用的是 n! 并且 n 是一个 32 位的 int，那么使用静态数组会更好。
如果您的值范围很大，比如任何双精度值，那么您的哈希表可能会变得如此之大，以至于成为一个严重的问题。
如果与给定对象一起反复使用相同的结果，则将该值与对象一起存储可能是有意义的。
就我而言，我发现任何给定迭代的输入在 90% 以上的时间都与上一次迭代相同。这意味着我只需要保留最后一个输入和最后一个结果，并且只有在输入更改时才重新计算。这比对该算法使用记忆化快一个数量级。
于 2010-07-14T00:52:24.727 回答