Czy można leniwie przemierzać rekursywną strukturę danych przy użyciu pamięci O (1), zoptymalizowanym ogonem?

Question

Załóżmy, że mamy rekursywną strukturę danych, taką jak drzewo binarne. Istnieje wiele sposobów na przemierzanie go i mają różne profile wykorzystania pamięci. Na przykład, gdybyśmy po prostu wydrukować wartości każdego węzła, używając pseudo-kod podobny do poniższego przechodzenie na zamówienie ...

visitNode(node) { 
    if (node == null) return; 
    visitNode(node.leftChild); 
    print(node.value); 
    visitNode(node.rightChild); 
} 

... nasz wykorzystanie pamięci byłaby stała, ale ze względu na wywołania rekurencyjne, zwiększyłybyśmy rozmiar stosu wywołań. Na bardzo dużych drzewach może to potencjalnie spowodować przepełnienie.

Załóżmy, że zdecydowaliśmy się zoptymalizować pod kątem rozmiaru stosu wywołań; przy założeniu, że język ten jest zdolny do prawidłowego tailcalls, możemy przepisać to jako następnego pre-order przechodzenie ...

visitNode(node, nodes = []) { 
    if (node != null) { 
     print(node.value); 
     visitNode(nodes.head, nodes.tail + [node.left, node.right]); 
    } else if (node == null && nodes.length != 0) { 
     visitNode(nodes.head, nodes.tail); 
    } else return; 
} 

Choć nigdy nie dmuchać stos, chcielibyśmy teraz zobaczyć sterty wzrost wykorzystania liniowo w stosunku do wielkość drzewa.

Powiedzmy, że wtedy próbowaliśmy leniwie przemierzać drzewo - tu moje rozumowanie staje się niewyraźne. Myślę, że nawet stosując podstawową leniwą strategię ewaluacyjną, zwiększylibyśmy pamięć w tym samym tempie, co wersja zoptymalizowana pod kątem tailcall. Oto konkretny przykład przy użyciu Scala klasę Stream, który zapewnia leniwe ocena:

sealed abstract class Node[A] { 
    def toStream: Stream[Node[A]] 
    def value: A 
} 

case class Fork[A](value: A, left: Node[A], right: Node[A]) extends Node[A] { 
    def toStream: Stream[Node[A]] = this #:: left.toStream.append(right.toStream) 
} 

case class Leaf[A](value: A) extends Node[A] { 
    def toStream: Stream[Node[A]] = this #:: Stream.empty 
} 

Chociaż tylko szef strumienia jest surowo oceniane każdym razem, gdy left.toStream.append(right.toStream) jest oceniany, myślę to faktycznie ocenić głowę zarówno lewy, jak i prawy strumień. Nawet jeśli nie (z powodu dodania sprytu), , myślę, że, rekursywnie budując ten thunk (pożyczyć termin od Haskella) zasadniczo zwiększyłby pamięć w tym samym tempie. Zamiast mówić: "umieść ten węzeł na liście węzłów do przemierzania", w zasadzie mówimy: "tutaj jest inna wartość do oceny, która powie ci, co masz przechodzić dalej", ale wynik jest taki sam; przyrost pamięci liniowej.

Jedyna strategia, o której można pomyśleć, pozwoli uniknąć tego, że ma zmienny stan w każdym węźle, deklarując, które ścieżki zostały przecięte. To pozwoliłoby nam na posiadanie referencyjnej przezroczystej funkcji, która mówi: "Biorąc pod uwagę węzeł, powiem ci, który pojedynczy węzeł powinieneś przejść dalej", i moglibyśmy użyć tego do zbudowania iteratora O (1).

Czy istnieje inny sposób osiągnięcia O (1), zoptymalizowanego przejścia poprzecznego drzewa binarnego, być może bez stanu zmiennego?

Answer 1

Czy istnieje inny sposób osiągnięcia O (1), zoptymalizowanego przejścia poprzecznego drzewa binarnego, być może bez stanu zmiennego?

Jak napisałem w swoim komentarzu, możesz to zrobić, jeśli drzewo nie musi przetrwać przejścia. Oto przykład Haskell:

data T = Leaf | Node T Int T 

inOrder :: T -> [Int] 
inOrder Leaf      = [] 
inOrder (Node Leaf x r)   = x : inOrder r 
inOrder (Node (Node l x m) y r) = inOrder $ Node l x (Node m y r) 

trwa to O (1) przestrzeń pomocniczy jeśli założymy, garbage collector będzie oczyścić dowolnym Node że właśnie przetwarzane, więc skutecznie zastąpić ją przez prawo obróconej wersji. Jeśli jednak przetwarzane przez nas węzły nie mogą zostać natychmiast pobrane ze śmiecia, to ostatnia klauzula może utworzyć liczbę węzłów przed uderzeniem w liść.

Jeśli masz wskaźniki nadrzędne, to jest to również wykonalne. Wskaźniki rodzicielskie wymagają jednak zmiany stanu i uniemożliwiają udostępnianie poddrzew, więc nie są one naprawdę funkcjonalne. Jeśli reprezentujesz iterator za pomocą pary (cur, prev) początkowo (root, nil), możesz wykonać iterację zgodnie z opisem here. Aby to działało, potrzebny jest język z porównaniami wskaźnika.

Bez wskaźników rodzicielskich i stanu zmiennego, trzeba zachować strukturę danych, która przynajmniej śledzi lokalizację katalogu głównego drzewa i jak się tam dostać, ponieważ taka struktura będzie potrzebna w pewnym momencie w kolejności lub przechodzenie po zamówieniu. Taka struktura koniecznie zajmuje przestrzeń Ω (d), gdzie d jest głębokością drzewa.

Answer 2

Biorąc pod uwagę, że masz odniesienia do rodziców węzłów, istnieje ładne rozwiązanie opublikowane here. Zastąp pętlę while rozmową tylno-rekurencyjną (przechodzącą w last i current, która powinna to zrobić:

Wbudowane referencje zwrotne pozwalają śledzić zamawianie tras, bez nich nie mogę myśleć o sposób zrobić go na (zrównoważone) drzewa z mniej niż O(log(n)) przestrzeni pomocniczej.

Answer 3

nie byłem w stanie znaleźć odpowiedź, ale mam kilka wskazówek. Idź spojrzeć na http://www.ics.uci.edu/~dan/pub.html, przewiń do

[33] DS Hirschberg i SSSeiden, algorytm przechodzenie drzewa ograniczoną przestrzeń, Information Processing Letters 47 (1993)

Pobierz plik PostScript może trzeba convert go do formatu PDF (ps moja przeglądarka nie był w stanie przedstawić go poprawnie). Wspomina na stronie 2 (Tabela 1) szereg algorytmów i dodatkowej literatury.

Answer 4

Wyszukana odpowiedź.

Możemy używać darmowych monad, aby efektywnie wykorzystać pamięć.

{-# LANGUAGE RankNTypes 
       , MultiParamTypeClasses 
       , FlexibleInstances 
       , UndecidableInstances #-} 

    class Algebra f x where 
     phi :: f x -> x 

Algebra funktora f jest funkcją phi z f x do x jakiegoś x.Na przykład, każdy monada ma algebraiczne dla każdego obiektu m x:

instance (Monad m) => Algebra m (m x) where 
     phi = join 

Wolna monada jakiegokolwiek funktora f można skonstruować (ewentualnie jakieś funktorów tylko, jak omega-cocomplete lub kilka takich, ale typy Haskell są funktory wielomianowe, które są omega-cocomplete, więc stwierdzenie jest prawdą dla wszystkich funktorów Haskell):

data Free f a = Free (forall x. Algebra f x => (a -> x) -> x) 
    runFree g (Free m) = m g 

    instance Functor (Free f) where 
     fmap f m = Free $ \g -> runFree (g . f) m 

    wrap :: (Functor f) => f (Free f a) -> Free f a 
    wrap f = Free $ \g -> phi $ fmap (runFree g) f 

    instance (Functor f) => Algebra f (Free f a) where 
     phi = wrap 

    instance (Functor f) => Monad (Free f) where 
     return a = Free ($ a) 
     m >>= f = fjoin $ fmap f m 

    fjoin :: (Functor f) => Free f (Free f a) -> Free f a 
    fjoin mma = Free $ \g -> runFree (runFree g) mma 

teraz możemy użyć Free skonstruować bezpłatny monady dla funktora T a:

data T a b = T a b b 
    instance Functor (T a) where 
     fmap f (T a l r) = T a (f l) (f r) 

Z tego funktora możemy zdefiniować algebrę dla obiektu [a]

instance Algebra (T a) [a] where 
     phi (T a l r) = l++(a:r) 

Drzewo to darmowa monada nad funktora T a:

type Tree a = Free (T a)() 

może być wykonana przy użyciu następujących funkcji (jeśli zdefiniowane jako ADT, będą to nazwy konstruktorów, więc nic nadzwyczajnego):

tree :: a -> Tree a -> Tree a -> Tree a 
    tree a l r = phi $ T a l r -- phi here is for Algebra f (Free f a) 
    -- and translates T a (Tree a) into Tree a 

    leaf :: Tree a 
    leaf = return() 

Aby zademonstrować, jak to działa:

bar = tree 'a' (tree 'b' leaf leaf) $ tree 'r' leaf leaf 
    buz = tree 'b' leaf $ tree 'u' leaf $ tree 'z' leaf leaf 
    foo = tree 'f' leaf $ tree 'o' (tree 'o' leaf leaf) leaf 

    toString = runFree (\_ -> [] :: String) 

    main = print $ map toString [bar, buz, foo] 

Jak runFree przemierza drzewa zastąpić leaf() z [], algebra dla T a [a] we wszystkich kontekstach jest algebra że buduje ciąg reprezentujący przechodzenie na zamówienie drzewa. Ponieważ funktor T a b konstruuje nowe drzewo, musi mieć tę samą charakterystykę zużycia pamięci co rozwiązanie cytowane przez larsmans - jeśli drzewo nie jest przechowywane w pamięci, węzły są odrzucane, gdy tylko zostaną zastąpione przez ciąg reprezentujący całe poddrzewo.