有限递归背后的内存不足

Question

我正在做objsets课程作业.我遇到了记忆问题

Java Runtime Environment没有足够的内存来继续.本机内存分配(malloc)无法为提交保留内存分配253231104个字节.

在实现这样的union函数时

def union(that: TweetSet): TweetSet = (left union(right)) union(that) incl(elem)

我通过将union方法更改为来修复问题

def union(that: TweetSet): TweetSet = right union(left union(that)) incl(elem)

有什么不同 ？为什么我在第一种情况下遇到内存问题？谢谢 !

Answer 1

我也参加过 Coursera 的 FP with Scala 课程，并且遇到了和你一样的问题。我也想出了相同的工作解决方案。了解为什么一个有效而另一个无效的关键在于函数的递归分解。首先，让我们看看您的第一个不会终止的解决方案。

def union(that: TweetSet): TweetSet = (left union(right)) union(that) incl(elem)

让我们使用一个简单的示例树和一些任意树that：

val tree = NonEmpty(tweet1, NonEmpty(tweet2, Empty, Empty), NonEmpty(tweet3, Empty, Empty))
val that: TweetSet = ...

tree.union(that)

扩展到：

tree.left.union(tree.right)).union(that).incl(tree.elem)

进一步扩展为：

tree.left.left.union(tree.left.right).union(tree.right).incl(tree.left.elem).union(that).incl(tree.elem)

现在我们可以在 Empty TweetSets 上调用基本情况（tree.left.left 和 tree.left.right）

tree.right.incl(tree.left.elem).union(that).incl(tree.elem)

现在已经足够了，让我们看看第二个解决方案。

def union(that: TweetSet): TweetSet = left union(right union(that)) incl(elem)


tree.union(that)

扩展到：

tree.left.union(tree.right.union(that)).incl(tree.elem)

再次展开：

tree.left.union(tree.right.left.union(tree.right.right.union(that)).incl(tree.right.elem)).incl(tree.elem)

应用tree.right.left 和tree.right.right 的基本情况

tree.left.union(that.incl(tree.right.elem)).incl(tree.elem)

在每个步骤相同数量之后，您可以看到我们有非常不同的表达。

解1 =tree.right.incl(tree.left.elem).union(that).incl(tree.elem)

解2 =tree.left.union(that.incl(tree.right.elem)).incl(tree.elem)

在解决方案 1 中，您可以看到调用incl发生在 next 的左侧union：

tree.right.incl(tree.left.elem).union(that).incl(tree.elem)
           ^^^^

而在解决方案 2 中，incl发生在下一个 的右侧union。

tree.left.union(that.incl(tree.right.elem)).incl(tree.elem)
                     ^^^^

所以我们可以看到，解决方案 1 在并集之前构建了一棵全新的树，比上一次迭代少了一个元素。对于将要处理的树中的每个左分支，都会重复此过程。n^2 效率。创建 n^2 个新树时会发生内存分配错误。解决方案 2 使用现有树作为下一个并集的左侧，并从基本情况返回新树（n 的效率）。为了与给定的基本情况建立有效的并集，您必须构建表达式的右侧，union因为构建左侧将导致指数级更多的工作。