struktura danych trwałych a niezmiennych

Question

Czy istnieje jakaś różnica w trwałej i niezmiennej strukturze danych? Wikipedia mówi o niezmiennej strukturze danych podczas omawiania wytrwałości, ale mam wrażenie, że może istnieć subtelna różnica między tymi dwoma.

Answer 1

Immutability to technika implementacji. Między innymi zapewnia trwałość, który jest interfejsem. Utrzymywanie API jest coś takiego:

• version update(operation o, version v) wykonuje operację o wersji v, powracając do nowej wersji. Jeśli struktura danych jest niezmienna, nowa wersja jest nową strukturą (która może dzielić niezmienne części starej struktury). Jeśli struktura danych nie jest niezmienna, zwrócona wersja może być po prostu numerem wersji. Wersja v pozostaje poprawną wersją i nie powinna się zmieniać w żaden sposób, aby była możliwa z powodu tej aktualizacji - aktualizacja jest widoczna tylko w zwróconej wersji, a nie w v.
• data observe(query q, version v) obserwuje strukturę danych w wersji v, nie zmieniając jej ani nie tworząc nowej wersji.

Więcej informacji na temat tych różnic, zobacz:

• The chapter "Persistent data structures" by Haim Kaplan in Handbook on Data Structures and Applications
• "Making Data Structures Persistent" by Driscoll et al.
• The first lecture of the Spring 2012 incarnation of MIT's 6.851: Advanced Data Structures

Answer 2

Tak, jest różnica. Niezmienna struktura danych nie może być w żaden sposób modyfikowana po jej utworzeniu. Jedynym sposobem na efektywną modyfikację byłoby utworzenie zmiennej lub czegoś podobnego (np. Nieznacznie modyfikującego parametry, które przekazujesz do konstruktora nowego). Z drugiej strony, stała struktura danych jest zmienna w tym sensie, że ujawniony interfejs API wydaje się zezwalać na zmiany w strukturze danych. W rzeczywistości jednak wszelkie zmiany zachowają wskaźnik do istniejącej struktury danych (a zatem każdej poprzedniej struktury); zdają się mutować tylko strukturę danych, ponieważ odsłonięty interfejs API zwraca nowy wskaźnik, który może zawierać wskaźniki do podzbioru poprzedniej struktury danych (w drzewach, np. wskażemy na węzeł, którego poddrzewo nie zmieniło się w wyniku operacja).