有限遞歸背後的內存不足

Question

我正在做objsets 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) 

的區別是什麼問題？爲什麼iam在第一種情況下出現內存問題？謝謝 ！

Answer 1

我也在Scala上學習了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) 

現在我們可以調用t在空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中，可以看出，在左側的下一個union的發生incl呼叫：

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) 
        ^^^^ 

因此，我們可以看到該解決方案以與一個比以前少迭代元素工會之前建立一個全新的樹。對於將要處理的樹中的每個左分支，這個過程都會重複。 n^2效率。內存分配錯誤發生在創建n^2個新樹上。解決方案2使用現有樹作爲下一個聯合的左側，並從基本情況返回新的樹（效率爲n）。要與給定的基本情況保持有效的結合，您必須建立union表達式的右側，因爲構建左側將導致指數級更多的工作。