Niewystarczająca pamięć za skończoną rekurencją

Question

Wykonuję zadania z obiektami objsets. I napotkałem problem z pamięcią

Brak pamięci dla środowiska Java Runtime Environment, aby kontynuować. Natywna alokacja pamięci (malloc) nie może przydzielić 253231104 bajtów w celu zatwierdzenia zarezerwowanej pamięci.

przy realizacji funkcji związkowej jak ten

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

Naprawiłem problem poprzez zmianę sposobu Unię do

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

Jaka jest różnica? dlaczego mam problem z pamięcią w pierwszym przypadku? Dziękuję Ci !

Answer 1

Też brałem kurs Coursera na FP ze Scala i miałem ten sam problem co ty. Wymyśliłem również to samo działające rozwiązanie. Kluczem do poznania, dlaczego jeden działa, a drugi nie, jest rekurencyjny rozkład funkcji. Najpierw przyjrzyjmy się twojemu pierwszemu rozwiązaniu, które się nie kończy.

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

użyjmy prosty przykład drzewa i jakieś arbitralne drzewo that:

val tree = NonEmpty(tweet1, NonEmpty(tweet2, Empty, Empty), NonEmpty(tweet3, Empty, Empty)) 
val that: TweetSet = ... 

tree.union(that) 

rozszerza się:

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

rozszerza dalej:

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

teraz możemy wywołaj t on przypadek bazowy na pustym TweetSets (tree.left.left i tree.left.right)

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

to na tyle daleko teraz spójrzmy na drugiego rozwiązania.

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


tree.union(that) 

Interpretowany:

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

Rozwiń ponownie:

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

Zastosuj przypadek bazowy dla tree.right.left i tree.right.right

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

Po tej samej liczbie kroków na każdym możesz zobaczyć t Mamy bardzo różne wyrażenia.

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

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

w roztworze 1, można zobaczyć, że wezwanie incl występuje po lewej stronie następnej union:

tree.right.incl(tree.left.elem).union(that).incl(tree.elem) 
      ^^^^ 

w roztworze 2 , incl występuje po prawej stronie następnego union.

tree.left.union(that.incl(tree.right.elem)).incl(tree.elem) 
        ^^^^ 

Widzimy więc, że rozwiązanie 1 buduje zupełnie nowe drzewo przed połączeniem z jednym elementem mniej niż w poprzedniej iteracji. Ten proces będzie się powtarzać dla każdego lewego odgałęzienia w drzewie, które będzie przetwarzane. Wydajność n^2. Błąd alokacji pamięci występuje podczas tworzenia n^2 nowych drzewek. Rozwiązanie 2 używa istniejącego drzewa jako lewej strony następnego związku i zwraca nowe drzewo z podstawowego przypadku (efektywność n). Aby uzyskać efektywne połączenie z danym przypadkiem podstawowym, musisz zbudować prawą stronę wyrażenia union, ponieważ budowanie lewej strony spowoduje wykładniczo więcej pracy.