Jakie klasy struktur danych można utrwalić?

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)?

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(\lg n)$

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ę (z$O(\lg n)$$O(\lg n)$$O(1)$$O(f(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 ) .$n$$O(\lg n)$$O(f(n) \lg n)$

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(\lg \lg n)$

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:$n$$O(1)$$O(1)$$\Omega(\lg \lg n)$

• Konsekwentnie trwałe próby skutecznej kontroli wersji . Erik D. Demaine, Stefan Langerman, Eric Price. Al Algorytmica, tom 57, nr 3, 2010, strony 462–483.

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(\lg n)$

$\ell$$d$$d$

$n$$O(\lg n)$$O(\lg n)$$O(\lg n)$

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

• Przeczytaj sekcje „Drzewa wyszukiwania binarnego” i „Struktury dostępu losowego” (w szczególności metoda drzewa) na stronie http://toves.org/books/persist/index.html .

• Lub przeczytaj http://netcode.ru/dotnet/?artID=6592#BinaryTrees i niektóre kolejne sekcje.

• Lub przeczytaj sekcje „Funkcjonalne struktury danych” i „Kopiowanie ścieżek” (zaczynające się na str. 4) cytowanego powyżej dokumentu Demaine: http://erikdemaine.org/papers/ConfluentTries_Algorithmica/paper.pdf

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.