Lista drzew Conc
Conc -tree to struktura danych , która przechowuje sekwencje elementów i zapewnia amortyzowane operacje dołączania i poprzedzania w czasie O (1), operacje wstawiania i usuwania w czasie O (log n) oraz łączenie w czasie O (log n). Ta struktura danych jest szczególnie przydatna w funkcjonalnym programowaniu równoległym do zadań i równoległym do danych i jest stosunkowo łatwa do wdrożenia w porównaniu z innymi strukturami danych o podobnej złożoności asymptotycznej. Conc-drzewa zostały zaprojektowane w celu poprawy wydajności operacji równoległych danych, które nie wymagają sekwencyjnej kolejności iteracji od lewej do prawej, oraz poprawy stałych czynników w tych operacjach poprzez unikanie zbędnych kopii danych. algorytmach równoległych zadań w stylu funkcjonalnym , jako implementacja abstrakcji danych conc-list. Conc-list jest równoległym odpowiednikiem funkcjonalnych cons-lists i został pierwotnie wprowadzony przez język Fortress .
Operacje
Podstawową operacją conc-tree jest konkatenacja. Conc-drzewa działają na następujących podstawowych typach danych:
0
0
0
cecha Conc [ T ] { def left : Conc [ T ] def right : Conc [ T ] def level : Int def size : Int } case class Empty [ T ] extends Conc [ T ] { def level = def size = } case class Single [ T ]( elem : T ) extends Conc [ T ] { def level = def size = 1 } case class <> [ T ]( left : Conc [ T ], right : Conc [ T ]) extends Conc [ T ] { poziom wartości = 1 + matematyka . max ( lewy . poziom , prawy . poziom ) val rozmiar = lewy . rozmiar + prawy . rozmiar }
Typ <> reprezentuje wewnętrzne węzły i jest wymawiany conc , zainspirowany :: ( typem cons ) w listach funkcjonalnych, używanych do programowania sekwencyjnego.
Konkatenacja w czasie O(log n) działa wówczas, zapewniając, że różnica poziomów (tj. wysokości) między dowolnymi dwoma drzewami rodzeństwa wynosi jeden lub mniej, podobnie jak niezmienniki utrzymywane w drzewach AVL . Ten niezmiennik zapewnia, że wysokość drzewa (długość najdłuższej ścieżki od korzenia do jakiegoś liścia) jest zawsze logarytmiczna w liczbie elementów w drzewie. Konkatenacja jest realizowana w następujący sposób:
def concat ( xs : Conc [ T ], ys : Conc [ T ]) { val diff = ys . poziom - xs . poziom if ( math . abs ( różnica ) <= 1 ) nowy <> ( xs , ys ) else if ( różnica < - 1 ) { jeśli ( xs . lewy . poziom >= xs . prawy . poziom ) { val nr = concat ( xs . prawy , ys ) nowy <> ( xs . lewy , nr ) } else { val nrr = konkat ( xs . prawy . prawy , ys ) if ( nrr . poziom == xs . poziom - 3 ) { val nr = nowy <> ( xs . prawy . lewy , nrr ) nowy <> ( xs . lewy , nr ) } else { val nl = nowy <> ( xs . lewy , xs . prawy . lewy ) nowy <> ( nl , nrr ) } } } else { // przypadek symetryczny } }
Dołączanie (lub poprzedzanie) czasu amortyzowanego O(1) uzyskuje się poprzez wprowadzenie nowego typu węzła wewnętrznego o nazwie Append i użycie go do zakodowania logarytmicznej listy drzew conc, ściśle malejącej wysokości. Każda aplikacja węzła Append musi spełniać następujące niezmienniki:
1. Poziom ap.left.right jest zawsze ściśle większy niż poziom ap.right .
2. Drzewo ap.right nigdy nie zawiera węzłów Append (tzn. jest w znormalizowanej formie, złożonej tylko z <> , Single i Empty ).
W przypadku tych niezmienników dołączanie jest izomorficzne z dodawaniem liczb binarnych - dwa sąsiednie drzewa o tej samej wysokości można połączyć w stałym czasie, z co najwyżej logarytmiczną liczbą operacji przenoszenia. Jest to zilustrowane na poniższym rysunku, gdzie element jest dołączany do drzewa conc, które odpowiada liczbie binarnej 11:
Ta reprezentacja liczb binarnych jest podobna do czysto funkcjonalnych list o swobodnym dostępie autorstwa Okasaki, z tą różnicą, że listy o swobodnym dostępie wymagają, aby wszystkie drzewa były kompletnymi drzewami binarnymi , podczas gdy drzewa conc są bardziej swobodne i wymagają tylko zrównoważonych drzew. Te bardziej swobodne niezmienniki pozwalają drzewom conc zachować logarytmiczną konkatenację w czasie, podczas gdy listy o swobodnym dostępie pozwalają tylko na konkatenację O (n).
Poniżej przedstawiono implementację metody dołączania , która jest najgorszym przypadkiem O (log n) i zamortyzowanym czasem O (1):
klasa przypadku Append [ T ]( lewy : Conc [ T ], prawy : Conc [ T ]) extends Conc [ T ] { val level = 1 + math . max ( lewy . poziom , prawy . poziom ) val rozmiar = lewy . rozmiar + prawy . size } private def append [ T ]( xs : Append [ T ], ys : Conc [ T ]) = if ( xs . right . level > ys . level ) new Append ( xs , ys ) else { val zs = new < > ( xs . prawo , ys ) xs . lewe dopasowanie { case ws @ Append ( _ , _ ) => append ( ws , zs ) case ws => if ( ws . level <= xs . level ) concat ( ws , zs ) else new Append ( ws , zs ) } } }
Conc-tree skonstruowane w ten sposób nigdy nie ma więcej niż O(log n) węzłów dołączania i może zostać przekonwertowane z powrotem do postaci znormalizowanej (jednej używającej tylko <> , pojedynczych i pustych węzłów) w czasie O(log n).
Szczegółową demonstrację tych operacji można znaleźć w zasobach internetowych lub w oryginalnym dokumencie conc-tree. Wykazano, że te podstawowe operacje można rozszerzyć, aby obsługiwały operacje deque O(1) w najgorszym przypadku, przy jednoczesnym zachowaniu ograniczenia czasowego konkatenacji O(log n), kosztem zwiększenia stałych współczynników wszystkich operacji.