Недостаточно памяти за конечной рекурсией

Question

Я выполняю задания coursera objsets. И я столкнулся с проблемой памяти

Недостаточно памяти для 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) 

В чем разница? почему iam получает проблему с памятью в первом случае? Спасибо !

Answer 1

Я тоже прошел курс Курсера по FP с 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) 

Теперь мы можем вызывать 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 Мы имеем очень разные выражения.

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

Solution2 = 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, потому что создание левой стороны приведет к экспоненциальному увеличению работы.