问题标签 [memoization]

我正在编写一个函数来查找三角形数，而编写它的自然方法是递归：

但是尝试计算前 100,000 个三角形数会在一段时间后因堆栈溢出而失败。这是memoize的理想函数，但我想要一个能够记住我传递给它的任何函数的解决方案。

我看过另一篇关于这个的帖子，但是在 Haskell 中有没有一种干净的方法呢？

作为第二部分，它也可以在不使函数单子化的情况下完成吗？

上面的代码示例使用 memoization 根据一些输入计算递归公式n。我知道这使用了记忆化，因为我编写了一个使用相同公式的纯递归函数，但是对于更大的n. 我以前从未使用过向量，但我做了一些研究，我理解了它们的概念。我知道记忆应该存储每个计算的值，这样它就可以简单地检索已经计算过的值，而不是再次执行相同的计算。

我的问题是：这个记忆如何，它是如何工作的？我似乎无法在代码中看到它检查 n 的值是否已经存在。另外，我不明白if(as[n]<=0). 这个公式可以产生正值和负值，所以我不确定这个检查在寻找什么。

谢谢，我想我已经接近理解它是如何工作的了，它实际上比我想象的要简单一些。

我不认为序列中的值永远是 0，所以这应该对我有用，因为我认为 n 必须从 1 开始。

但是，如果零在我的序列中是一个可行的数字，那么我可以解决它的另一种方法是什么？例如，如果五个永远不会出现怎么办？我只需要用五个填充我的向量吗？

编辑：哇，我在检查代码和输入这个代码时收到了很多其他的回复。谢谢大家的帮助，我想我现在明白了。

我有一个接受 Predicate<Foo> 并返回匹配项列表的 C# 方法...

过滤器通常是常见的一组...

...但可能是匿名代表。

我现在想让这个方法在 ASP.NET 缓存中缓存它的结果，所以重复调用同一个委托只会返回缓存的结果。为此，我需要从委托创建一个缓存键。Delegate.GetHashCode() 会为此目的产生合理的结果吗？还有其他我应该看的代表成员吗？你会完全以另一种方式来做这件事吗？

我是一个 Lisp 初学者。我试图记住一个递归函数来计算Collat​​z 序列中的项数（对于Project Euler中的问题 14 ）。到目前为止，我的代码是：

memoize 函数与On Lisp书中给出的函数相同。

与非记忆版本相比，此代码实际上并没有提供任何加速。我相信这是由于递归调用调用了函数的非记忆版本，这有点违背了目的。在那种情况下，在这里进行记忆的正确方法是什么？有没有办法让对原始函数的所有调用都调用记忆化版本本身，从而消除对特殊 m-collat​​z-steps 符号的需要？

编辑：更正了代码

这就是我的代码中的内容。在编辑之前，我错误地输入了：

看到这个错误给了我另一个想法，我尝试使用最后一个 defvar 本身并将递归调用更改为

这似乎确实执行了记忆（从大约 60 秒加速到 1.5 秒），但需要更改原始功能。是否有不涉及更改原始功能的更清洁的解决方案？

我有一个关于在 Haskell 中使用数组实现缓存（记忆）的问题。以下模式有效：

但这不是（程序的速度表明每次调用或其他东西都会重新创建数组）：

在 where 子句之外（在“全局范围”中）定义 fA 也适用于任一模式。

我希望有人能指出我对上述两种模式之间区别的技术解释。

请注意，我使用的是最新的 GHC，我不确定这只是编译器的特性还是语言本身的一部分。

编辑： ！用于数组访问，所以 fA ！5 表示 C++ 语法中的 fA[5]。我对 Haskell 的理解是 (fA !) n 将与 (fA ! n) 相同......而且对我来说写“fn = fA ! n”（不带括号）会更传统。无论如何，无论我如何括号，我都会得到相同的行为。

如果我可以选择使用递归或记忆来解决我应该使用的问题？换句话说，如果它们都是可行的解决方案，因为它们提供了正确的输出并且可以在我正在使用的代码中合理地表达，那么我什么时候会使用一个而不是另一个呢？

我正在尝试构建一个 .PLY 解析器，以将存储为 .ply 文件的 3d 模型加载到半边数据结构网格中。

抱歉这个大问题，我很冗长，我想确保我列出了所有细节。正因为如此，我将立即重申我的最终目标，以便用户可以在阅读大量文本之前了解我想要什么。

1) 什么是从 .PLY 文件的顶点和面列表中记忆半边的好散列

或者

2) 有没有更好的方法从 .PLY 文件中的数据填充我的半边结构？

.PLY 文件列出了顶点，然后是网格的面。显而易见的解决方案是先填写顶点表，然后使用面列表生成边表。问题是每条边都有一个伙伴边，所以对于四边形网格，我加载的第一个四边形将需要 8 个半边。这最初不是问题，只需为面部创建四个半边并反转每个边以使其伙伴成为半边。这里的问题是，这会创建 4 个悬垂的半边，这些边与 4 个不同的面相关联。

所以有两种攻击方法：首先为人脸生成所有边，然后尝试配对伙伴边。我真的不喜欢这种方法，它似乎在编程上效率较低，因为它将涉及大量搜索和排序。

第二：按照第一个说明进行：从指定的第一个面开始并生成创建多边形所需的边，并在创建边时创建它们的双胞胎。但是，我们将记住边列表，因此所有边都将散列到一个表中。然后，当我们为其他面生成边时，如果已经生成了一条边（因为它是先前加载的面的伙伴边），我们将简单地将指针从表格中取出。

这就是我卡住的地方。我需要一个智能散列函数来记忆我的边缘列表。需要尽量减少碰撞以提高效率。我现在想到的方案是根据创建它们的两个顶点命名*边，IE 边 01 和 10 是双胞胎。最坏的情况会创建一个哈希表，其中所有顶点都可能被连接，最终大小为 2^n，其中 n = 顶点数，这是完全不可接受的。我的目标是使哈希值接近实际边数（= 每个面的边数之和），同时仍尽量减少碰撞。

*注意：因为半边执行“仅逆时针”绘制方案，所以不可能发生名称冲突。通过基于绘制它们的两个顶点命名边，我们确保所有名称对于单个半边都是唯一的。

在 C# 中，我如何记住一个带有两个参数的函数？

在记忆之前我必须咖喱吗？

Wes Dyer 编写了我通常使用的 Memoization 代码，但现在我需要两个参数

我试图模仿 JavaScript 函数上的静态变量，目的如下：

如何保存“折叠”对象，以便不必在每次调用时都“找到”它？我知道使用命名函数我可以做一些类似“someFunction.myvar = collapse”的事情，但是像这样的匿名函数呢？

谢谢！