Trwała tablica

W informatyce , a dokładniej w odniesieniu do struktur danych , trwała tablica to trwała struktura danych o właściwościach podobnych do (nietrwałej) tablicy . Oznacza to, że po aktualizacji wartości w trwałej tablicy istnieją dwie trwałe tablice. Jedna trwała tablica, w której brana jest pod uwagę aktualizacja, oraz jedna, która jest równa tablicy przed aktualizacją.

Różnica między tablicami trwałymi a tablicami

Tablica $mi ,$ liczbą n elementów $e_ {0}, \ kropki$ } Oczekuje się, że biorąc pod uwagę tablicę ar i indeks ${\ Displaystyle 0 \ równoważnik i <n}$ , wartość $odzyskać$ . Ta operacja nazywa się przeglądem . $v$ , biorąc pod uwagę tablicę ar , indeks nową wartość , nową ar2 z ${\ Displaystyle [e_ {0}, \ kropki, e_ {i-1}, v, e_ {i + 1}, \ kropki, e_ {n-1}]} można szybko utworzyć$ . Ta operacja jest nazywana aktualizacją . Główna różnica między tablicami trwałymi i nietrwałymi polega na tym, że w tablicach nietrwałych tablica ar jest niszczona podczas tworzenia ar2 .

Rozważmy na przykład następujący pseudokod.

 tablica  = [0, 0, 0]  zaktualizowana_tablica  =  tablica  .aktualizacja(0, 8)  inna_tablica  =  tablica  .aktualizacja(1, 3)  ostatnia_tablica  =  zaktualizowana_tablica  .aktualizacja(2, 5) 

Pod koniec wykonywania, wartość array nadal wynosi [0, 0, 0], wartość update_array to [8, 0, 0], wartość other_array to [0, 3, 0], a wartość last_array to [ 0, 8, 5].

Istnieją dwa rodzaje trwałych tablic. Trwała tablica może być częściowo lub całkowicie trwała. W pełni trwała tablica może być aktualizowana dowolną liczbę razy, podczas gdy częściowo trwała tablica może być aktualizowana co najwyżej raz. W naszym poprzednim przykładzie, gdyby tablica była tylko częściowo trwała, tworzenie innej_tablicy byłoby zabronione, jednak tworzenie ostatniej_tablicy byłoby nadal poprawne. Rzeczywiście, updated_array jest tablicą różną od array i nigdy nie była aktualizowana przed utworzeniem last_array .

Implementacje

Istnieje wiele implementacji tablic trwałych. W tej sekcji dodatnia liczba naturalna n zawsze będzie miała rozmiar tablicy trwałej.

Poniżej omówiono trzy implementacje. Te pierwsze są najłatwiejsze do wdrożenia, natomiast ostatnie są bardziej wydajne.

Używanie czysto funkcjonalnych struktur danych

0 Najprostsza implementacja w pełni trwałej tablicy o rozmiarze n polega na użyciu dowolnej trwałej mapy, której wpisami są liczby od do n − 1. Taką strukturą danych może być np. zrównoważone drzewo . Jednak wyszukanie elementu w takiej strukturze danych zajęłoby czas logarytmiczny . Jedną z głównych zalet tablicy jest to, że operacje są wykonywane w stałym czasie. O ile nie jest możliwe stworzenie struktury danych, w której każda operacja zajmuje stały czas, o tyle poniższe operacje pozwolą na bardziej wydajne wyszukiwanie, przynajmniej na ostatniej wersji struktur.

Korzystanie z tablicy i drzewa modyfikacji

W pełni trwałą tablicę można zaimplementować za pomocą tablicy i tzw. sztuczki Bakera. Ta implementacja jest używana w OCaml parray.ml autorstwa Jean-Christophe Filliâtre.

Aby zdefiniować tę implementację, należy podać kilka innych definicji. Tablica początkowa to tablica, która nie jest generowana przez aktualizację innej tablicy. Dziecko tablicy ar jest tablicą w postaci ar.update(i,v) , a ar jest rodzicem ar.update (i,v ) . Potomkiem tablicy ar jest ar lub potomek elementu podrzędnego ar . Początkowa tablica tablicy ar jest albo ar , jeśli ar jest początkowe, albo jest początkową tablicą rodzica ar . Oznacza to, że początkowa tablica ar jest unikalną tablicą init taką, że ${\ Displaystyle \ operatorname {ar} = init.update (i_ {0}, v_ {0}). \ dots .update (i_ {m}, v_ {m})} z początkowym ar i ja , … , ja m {\ Displaystyle i_ {0}, \ kropki, i_ {m}} dowolna sekwencja indeksów i v , … , v$ m { \ $,$ v_ $wartości$ . rodzina _ tablicy jest więc zbiorem tablic zawierających tablicę początkową i wszystkich jej elementów potomnych. Wreszcie, drzewo rodziny tablic jest drzewem, którego węzłami są tablice, z krawędzią e od ar do każdego z jego elementów podrzędnych ar.update(i,v) .

Trwała tablica wykorzystująca sztuczkę Bakera składa się z pary z rzeczywistą tablicą zwaną tablicą i drzewem tablic. To drzewo dopuszcza dowolny korzeń - niekoniecznie początkową tablicę. Korzeń może zostać przeniesiony do dowolnego węzła drzewa. Zmiana korzenia z korzenia na dowolny węzeł ar zajmuje czas proporcjonalny do głębokości ar . To znaczy w odległości między root a ar . Podobnie wyszukiwanie wartości zajmuje czas proporcjonalny do odległości między tablicą a korzeniem jej rodziny. Tak więc, jeśli ta sama tablica ar może być wyszukiwany wiele razy, bardziej wydajne jest przeniesienie katalogu głównego do ar przed wykonaniem wyszukiwania. Wreszcie aktualizacja tablicy zajmuje tylko stały czas .

Technicznie biorąc, biorąc pod uwagę dwie sąsiednie tablice ar1 i ar2 , z ar1 bliżej korzenia niż ar2 , krawędź od ar1 do ar2 jest oznaczona przez (i,ar2[i]) , gdzie i jest jedyną pozycją, której wartość różni się między ar1 i ar2 .

Dostęp do elementu i tablicy ar odbywa się w następujący sposób. Jeśli ar jest pierwiastkiem, to ar[i] równa się root[i] . W przeciwnym razie niech e krawędź wychodząca z ar będzie skierowana w stronę korzenia. Jeśli etykietą e jest (i,v), to ar[i] równa się v . W przeciwnym razie niech ar2 będzie drugim węzłem krawędzi e . Wtedy ar[i] równa się ar2[i] . Obliczanie ar2[i] odbywa się rekurencyjnie przy użyciu tej samej definicji.

Utworzenie ar.update(i,v) polega na dodaniu nowego węzła ar2 do drzewa i krawędzi e od ar do ar2 oznaczonej przez (i,v) .

Na koniec przeniesienie korzenia do węzła ar odbywa się w następujący sposób. Jeśli ar jest już korzeniem, nie ma nic do zrobienia. W przeciwnym razie niech e krawędź wychodząca z ar będzie skierowana w kierunku bieżącego korzenia, (i, v) jego etykiety i ar2 drugiego końca e . Przeniesienie korzenia do ar odbywa się najpierw przez przeniesienie korzenia do ar2 , zmiana etykiety e na (i, ar2[i]) i zmiana array[i] na v .

Log-log-czas

W 1989 roku Dietz zaimplementował w pełni trwałe tablice, tak że wyszukiwanie i aktualizacje można wykonywać w ${\ Displaystyle O (\ log \ log (\ min (n, m))}$ -czas i przestrzeń ${\ Displaystyle O (m + n)}$ , gdzie m liczba tablic i n numer elementu w tablicy. Ta implementacja jest optymalna do wyszukiwania, zgodnie z tak zwanym modelem sondy komórkowej.

Należy jednak pamiętać, że ta implementacja jest znacznie bardziej złożona niż dwie wymienione powyżej, dlatego nie zostanie opisana w tym artykule.

.