scala - 有限递归背后的内存不足

Question

我正在做 objsets coursera 作业。我遇到了内存问题

There is insufficient memory for the Java Runtime Environment to continue. Native memory allocation (malloc) failed to allocate 253231104 bytes for committing reserved memory.

在实现这样的联合功能时

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 类(class)，并且遇到了与您相同的问题。我也想出了同样的工作解决方案。了解为什么一个有效而另一个无效的关键在于函数的递归分解。首先，让我们看看您的第一个不终止的解决方案。

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调用发生在下一个 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 的右侧。表达式，因为建立左侧将导致成倍增加的工作。