Jakie klasy struktur danych można utrwalić?

19

Trwałe struktury danych to niezmienne struktury danych. Operacje na nich zwracają nową „kopię” struktury danych, ale zmienioną przez operację; stara struktura danych pozostaje jednak niezmieniona. Wydajność jest na ogół osiągana przez dzielenie się niektórymi danymi bazowymi i unikanie pełnego kopiowania struktury danych.

Pytania:

  • Czy istnieją wyniki dotyczące klas struktur danych, które można uczynić trwałymi (zachowując te same lub bardzo podobne złożoności)?

  • Czy wszystkie struktury danych mogą być trwałe (zachowując te same lub bardzo podobne złożoności)?

  • Czy wiadomo, że jakiekolwiek struktury danych nie mogą być trwałe (zachowując te same lub bardzo podobne złożoności)?

Realz Slaw
źródło
1
Nie można uczynić wektora trwałym z zachowaną złożonością O (1) w celu uzyskania dostępu do losowego elementu.
smossen
2
@smossen, możesz to udowodnić?
Realz Slaw
1
Twoje pierwsze pytanie jest bardzo szerokie. Istnieje wiele wyników na temat struktur danych, które można utrwalić. Można napisać całą książkę na ten temat, a niektórzy mają: na przykład książka Okasaki jest klasyką na ten temat. Czy przeprowadziłeś jakieś badania na ten temat? Czy możesz zawęzić pytanie? W tej chwili podejrzewam, że może być zbyt szeroki, aby dobrze pasował do tej witryny. Może podzielisz trzecie pytanie na osobne pytanie?
DW
@Realz Slaw: Nie mogę tego formalnie udowodnić, ale myślę, że to zdrowy rozsądek. O (1) dostęp do elementów w wektorach (w tym tablic skrótów) zależy od ustalonego czasu dekodowania adresu na danym sprzęcie. Trwałość dodaje jeden lub dwa wymiary oprócz indeksu wektorowego. Ale adresy sprzętowe są nadal jednowymiarowe.
smossen

Odpowiedzi:

22

Wynik pozytywny: wytrwałość nie kosztuje zbyt wiele. Można pokazać, że każda struktura danych może być w pełni trwała z co najwyżej spowolnieniem .O(lgn)

Dowód: możesz wziąć tablicę i sprawić, by była trwała przy użyciu standardowych struktur danych (np. Zrównoważone drzewo binarne; więcej szczegółów znajdziesz na końcu tej odpowiedzi). Powoduje to spowolnienie : każdy dostęp do tablicy zajmuje czas O ( lg n ) z trwałą strukturą danych, zamiast czasu O ( 1 ) dla nietrwałej tablicy. Teraz weźmy dowolny algorytm imperatywny, którego czas działania w modelu RAM to O ( f ( n ) ) , gdzie n oznacza ilość użytej pamięci. Reprezentuj całą pamięć jako jedną dużą tablicę (zO(lgn)O(lgn)O(1)O(fa(n))n elementów) i uczyń go trwałym za pomocą trwałej mapy. Każdy krok algorytmu imperatywnego powoduje co najwyżejspowolnienie O ( lg n ) , więc całkowity czas działania wynosi O ( f ( n ) lg n ) .nO(lgn)O(fa(n)lgn)

Najwyraźniej można zrobić trochę lepiej: najwyraźniej można zmniejszyć współczynnik spowolnienia do (oczekiwany, amortyzowany czas), stosując techniki z cytowanej poniżej pracy Demaine - ale nie znam szczegółów tej pracy, więc sam nie mogę za to ręczyć. Dzięki jbapple za tę obserwację.O(lglgn)


Wynik negatywny: nie można uniknąć spowolnienia w przypadku niektórych struktur danych. Aby odpowiedzieć na trzecie pytanie, istnieją struktury danych, o których wiadomo, że ich uporczywość powoduje pewne spowolnienie.

W szczególności rozważ tablicę elementów. Bez uporczywości dostęp do każdej tablicy zajmuje czas O ( 1 ) (w modelu RAM). Z uporem najwyraźniej wykazano, że nie ma sposobu na zbudowanie trwałej tablicy o złożoności O ( 1 ) najgorszego przypadku w celu uzyskania dostępu do losowego elementu. W szczególności widoczna jest dolna granica pokazująca, że ​​w pełni trwałe tablice muszą mieć czas dostępu Ω ( lg lg n ) . Ta dolna granica jest zapewniona na str. 3 następującego artykułu:nO(1)O(1)Ω(lglgn)

Dolną granicę przypisuje się Mihai Patrascu, ale nie ma żadnego wzmianki o źródle, które podaje szczegóły dowodu tej twierdzonej dolnej granicy.


Bogaty obszar badań. Jeśli weźmiemy dowolną strukturę danych lub algorytm, to jest trochę delikatne pytanie, czy możesz je utrwalić z co najwyżej spowolnieniem czy nie. Nie znam żadnego ogólnego twierdzenia o klasyfikacji. Istnieje jednak wiele badań nad tym, jak skutecznie utrwalić określone struktury danych.O(1)

Istnieje również silny związek z funkcjonalnymi językami programowania. W szczególności każda struktura danych, którą można wdrożyć w sposób czysto funkcjonalny (bez mutacji), jest już trwałą strukturą danych. (Niestety, niekoniecznie tak jest.) Jeśli chcesz zmrużyć oczy, możesz potraktować to jako słabe twierdzenie o częściowej klasyfikacji: jeśli można je zaimplementować w czysto funkcjonalnym języku programowania z takimi samymi granicami czasowymi, jak w imperatywnym językiem, wtedy istnieje trwała struktura danych o takich samych granicach czasowych jak nietrwały. Zdaję sobie sprawę, że to prawdopodobnie nie było to, czego szukałeś - jest to po prostu trywialne przeformułowanie sytuacji.


O(lgn)

rere

nO(lgn)O(lgn)O(lgn)

Możesz znaleźć więcej wyjaśnień, z ładnymi zdjęciami, w następujących zasobach:

To da ci główny pomysł. Należy zająć się dodatkowymi szczegółami, ale szczegóły nie mieszczą się w tym pytaniu. Na szczęście jest to wszystko standardowe i istnieje wiele informacji dostępnych w literaturze na temat tworzenia takich struktur danych. Jeśli powyższe zasoby nie są wystarczające, możesz zadać osobne pytanie, a chcesz uzyskać więcej informacji o szczegółach budowy trwałej struktury danych tablicowych.

DW
źródło
Naprawdę nie rozumiem akapitu pierwszego, w jaki sposób mógłbym uprościć tablicę przy użyciu czerwono-czarnego drzewa?
G. Bach,
@ G.Bach, całkiem dobre wyjaśnienie znajduje się w sekcjach „Drzewa wyszukiwania binarnego” i „Struktury o dostępie swobodnym” (w szczególności metoda drzewa) na stronie toves.org/books/persist/index.html . Aby uzyskać inny ładny opis, zobacz netcode.ru/dotnet/?artID=6592#BinaryTrees i kilka kolejnych sekcji. To da ci główny pomysł. Szczegóły są poza zakresem tego pytania, ale to wszystko standardowe rzeczy; Zachęcam do zadania osobnego pytania, jeśli chcesz uzyskać więcej informacji o tym, jak zbudować taką strukturę danych.
DW
4
O(lglgn)