有限再帰の後ろに不十分なメモリがあります

Question

私はobjsets courseraの割り当てをしています。そして私は記憶の問題に直面した。

Java Runtime Environmentが続行するためのメモリが不足している。 ネイティブメモリ割り当て（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.left.union(tree.left.right).union(tree.right).incl(tree.left.elem).union(that).incl(tree.elem) 

：

tree.left.union(tree.right)).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) 

ための基本ケースを適用しますそれぞれの同じ数のステップを実行すると、t私たちは非常に異なった表現をしています。

ソリューション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の右側に表示されます。

したがって、解決策1は、前の繰り返しよりも1つ少ない要素で、結合前に新しいツリーを構築することがわかります。このプロセスは、処理されるツリー内のすべての左ブランチについて繰り返されます。 n^2効率。メモリ割り当てエラーは、n^2個の新しいツリーを作成することによって発生します。解法2は、既存の木を次の共用体の左辺として使用し、新しい木を基本ケースから戻します（nの効率）。与えられた基底ケースとの効率的な結合を行うには、union式の右辺を構築する必要があります。なぜなら、左辺を構築することは指数関数的に多くなるからです。