有限递归背后的内存不足

Question

我正在做 objset coursera 作业。我遇到了记忆问题

没有足够的内存供 Java 运行时环境继续运行。 本机内存分配 （malloc） 无法分配 253231104 个字节来提交保留内存。

当像这样实现联合函数时

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

我通过将联合方法更改为

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

有什么

区别？ 为什么在第一种情况下我会遇到内存问题 ？ 谢谢 ！

Answer 1

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

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)

现在我们可以调用空推文集（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.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调用发生在下一个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表达式的右侧，因为构建左侧将导致成倍增加的工作。