Czysto funkcjonalne struktury danych z kopiowaniem przy zapisie?

Question

Chcę mieć tę zaletę funkcjonalnych struktur danych (wiele wersji danych, które mogą dzielić struktury), ale mogli modyfikować go w bezwzględnej stylu.

Co myślę o (i ewentualne stosowanie): gra RPG, w której cała historia gry są przechowywane (na przykład, aby pozwolić na podróż w czasie). Korzystając z funkcji kopiowania przy zapisywaniu, mogłem po prostu sklonować strukturę utrzymującą stan gry i zmodyfikować ją, wprowadzając nową turę - ale mając dostęp do wcześniejszych zakrętów (niekoniecznie wszystkich, może po prostu wybranych migawek stanu gry), bez kara za kopiowanie wszystkiego za każdym razem.

---

Załóżmy, że foo to mapa.

bar = foo.clone() 

Nic struktury foo „s (na przykład drzewa) dostaje jeszcze skopiowane. Jednak odtąd bar traktowana jest jako kopia i żadne zmiany nie mogą propagować powrotem do `foo”.

baz = bar[someKey] 
baz.modifyInSomeWay() 

Teraz

• nowy obiekt zostanie utworzony, który jest zmodyfikowaną kopią baz.
• bar zostaje zastąpiony nową mapą, zawierającą nowe baz (prawdopodobnie zachowując część struktury foo).
• foo jest nienaruszona.

Ale jeśli mamy wtedy zrobić ...

baz.modifyAgain() 

... baz może być po prostu zmodyfikowany, ponieważ mamy najnowszą wersję. bar nie trzeba zmieniać.

Wszystko to wymaga posiadania informacji o wersji i barfoo, zwiększając ją foo.clone() i przekazaniem go do baz jakoś (przez co obiekt proxy?).

Każda część struktury, która została sklonowana, staje się "częścią historii" i nie można jej już zmienić, co można wymusić w czasie wykonywania.

---

Przypomina prototypów JavaScript w przeglądarce, to trochę, ale to nic więcej, gdyż pozwala na zmiany propagować górę. Myślę, że byłoby to coś w rodzaju systemu kontroli wersji.

• Czy zostało to zrobione, w jakim stopniu?
• Czy to dobry pomysł? Jeśli nie, czy istnieje sposób, aby go zapisać?
• Jak to możliwe? Zastanawiałem się nad budowaniem go na wysokim poziomie GC-ed, takim jak Python.

Answer 1

Functional ("persistent") data structures są zazwyczaj rekurencyjnie zbudowany z niezmiennymi węzłów (np pojedynczo połączonej listy gdzie wspólne przyrostki są wspólne, przeszukiwania drzewa lub sterty gdzie tylko części struktury drzewa, które są na ścieżce od korzenia do zaktualizowanego przedmiot wymaga skopiowania).

Wszystko, co musi zostać skopiowane z całego zestawu dla każdej modyfikacji, jest złe. W takich przypadkach można nakładać małe "różnice", które są sprawdzane (zajmowanie dodatkowego czasu) z rekursją do poprzednich wersji. Co jakiś czas, gdy różnice stają się zbyt duże, można wykonać głęboką kopię/przebudowę (więc zamortyzowany koszt nie jest tak zły).

Utrwalone struktury danych mogą mieć znaczny narzut, ale jeśli masz bardzo wydajną alokację małych obiektów (kwalifikuje się JVM GC), mogą być bardzo praktyczne - w najlepszym wypadku równie szybkie jak zmienne równoważne, nadające tylko trwałość kosztem używanej pamięci - która może być znacznie mniejsza niż pełna kopia każdej aktualizacji.

W zależności od języka najprawdopodobniej trudno będzie uzyskać wymaganą składnię bez przeciążania operatora. L-wartości (zmienne odniesienia) w C++ zdecydowanie wymagają nietrwałej semantyki.

Answer 2

To brzmi groźnie skręcone i podatne na błędy w porównaniu do posiadania całkowicie niezmiennej struktury danych, a następnie użycia opakowania, które zawiera odniesienie do niego i ujawnia imperatywny interfejs, który działa poprzez aktualizację owiniętej wersji.

np. w Scali

class ImmutableData{ 
    def doStuff(blah : Blah) : ImmutableData = implementation 
} 

class MutableData(var wrapped : ImmutableData){ 
    def doStuff(blah : Blah) : Unit = { wrapped = wrapped.doStuff(blah); } 
} 

Oczywiście oznacza to, że musisz utworzyć dwie wersje interfejsu, ale semantyka jest dużo bardziej bezpieczna.

Answer 3

1. Czy zostało to zrobione, w jakim zakresie?

Tak, patrz na przykład qt5 implicit sharing.

2. Czy to dobry pomysł? Jeśli nie, czy istnieje sposób, aby go zapisać?

Tak, to jest dobry pomysł. Jedną z proponowanych alternatyw jest użycie w pełni niezmiennej struktury danych (opakowanej w imperatywny interfejs), ale problem polega na tym, że nawet jeśli obiekt jest jedynym, który wskaże dane, operacja modyfikacji utworzy kopię danych (nie ma aktualizacji na miejscu), jest to nieefektywne. Używając metody kopiowania przy zapisie, kopia jest wykonywana tylko w pierwszej modyfikacji, kolejne modyfikacje zmieniają kopiowane dane w miejscu (jeśli inne odniesienie do tych samych danych nie zostało utworzone, poza kursem).

3. W jaki sposób można to zrealizować? Zastanawiałem się nad budowaniem go na wysokim poziomie GC-ed, takim jak Python.

Jednym ze sposobów jest użycie liczenia odwołań, tak jak w qt (patrz opis here). Aby go zaimplementować, wymagane jest przeciążenie operatora przypisania lub jawne wywołanie metody (np. bar = foo.clone(), ale może być delikatne, co się stanie, jeśli ktoś zapomni zadzwonić pod numer clone i po prostu zrobi bar = foo?), Aby można było zliczać.

Inna możliwość tworzenia obiektu proxy, tak jak powiedziałeś. Zobacz na przykład pycow (implementacja Pythona).