Czy można skutecznie reprezentować mutację grafu obiektowego w niezmiennych stanach?

Ćwiczę używanie niezmiennego obiektu w C ++. Moim osobistym celem jest przedstawienie ogólnego wykresu obiektowego (w stercie) z sekwencją niezmiennych wykresów.

Samo tworzenie wykresu z wieloma wersjami nie jest takie trudne. Problemem jest wydajność. Wersje brute-force wymagają pełnej kopii wykresu, co było nie do przyjęcia.

Próbowałem udostępnić niezmienione węzły. Ale w tym przypadku mam nowy problem; Bibliografia. Odniesienie do innego obiektu musi zostać zaktualizowane na całym wykresie. To wymaga odwiedzania wszystkich węzłów za każdym razem, gdy uzyskuję nową wersję wykresu. I to mutuje węzły za pomocą referencji, dlatego też należy je wyprowadzić (kopiując). Wydajność nie będzie lepsza niż kopiowanie z użyciem siły.

O ile mogę sobie wyobrazić, nie ma naprawdę skutecznego sposobu reprezentowania mutacji wykresu obiektowego w niezmiennych stanach. Proszę o jakiś pomysł na ten temat.

Czy można skutecznie reprezentować mutację wykresu obiektowego w stanie niezmiennym?

To, czego szukasz, nazywa się Trwałą strukturą danych. Kanonicznym zasobem trwałych struktur danych jest książka Chrisa Okasakiego „ Czysto funkcjonalne struktury danych” . Trwałe struktury danych wzbudziły w ostatnich czasach zainteresowanie ze względu na ich popularyzację w Clojure i Scali.

Jednak z jakiegoś dziwnego powodu trwałe wykresy wydają się być w większości ignorowane. Mamy listy, dziesiątki różnych rodzajów drzew, tablice, kolejki priorytetowe, mapy, ale żadnych wykresów.

Znalazłem tylko jeden artykuł: w pełni trwałe wykresy - który wybrać?

Jeśli nie uważasz połączeń między obiektami za część zasobu z wersją (a możesz - w takim przypadku poniższe prawdopodobnie nie są zbyt pomocne), możesz rozważyć podzielenie swoich obiektów na część reprezentującą część połączenia obiektu i części reprezentującej niezmienny stan.

Wówczas każdy z podobiektów łączności może zawierać wektor stanów wersji. W ten sposób możesz pracować z numerem wersji wykresu, aby uzyskać dostęp do odpowiedniego niezmiennego stanu.

Aby uniknąć konieczności przechodzenia przez cały wykres za każdym razem, gdy pojawia się aktualizacja określonego węzła, można go ustawić tak, aby w przypadku dostępu do węzła o numerze wersji większym niż aktualny numer wersji użyto bieżącej wersji . Jeśli węzeł zostanie następnie zaktualizowany, wypełniasz wszystkie wersje pośrednie poprzednią wersją - umożliwiając w ten sposób dokonywanie leniwych aktualizacji wykresu obiektowego.

Jeśli łączność między obiektami jest częścią stanu wersjonowanego, powyższe nie działa. Ale może możesz to przedłużyć w następujący sposób:

Dla każdego obiektu na wykresie utwórz „obiekt uchwytu”. Obiekt uchwytu zawiera listę niezmiennych stanów wersjonowanych. Zamiast przechowywać odwołania do obiektów w dowolnym obiekcie na wykresie, należy przechowywać odniesienie do obiektu uchwytu. Następnie każde odwołanie do obiektu zostanie odsyłane do uchwytu za pomocą uchwytu i numeru wersji wykresu obiektu, który jest aktualnie przetwarzany. Zwróci to poprawny niezmienny stan obiektu. Niezmienne stany używają uchwytów do odwoływania się do innych obiektów na wykresie, więc zawsze otrzymujesz spójną datę dla wersji wykresu, którą chcesz przetworzyć.

Ta sama logika opisana powyżej dotyczy aktualizacji wersji w uchwytach - co pozwala na leniwe, zlokalizowane aktualizacje.

Istnieje opublikowane rozwiązanie tego problemu z bardzo dobrą zamortyzowaną złożonością czasu, ale trudno je znaleźć, gdy nie wiesz dokładnie, czego szukać. Ładne podsumowanie można znaleźć w tych notatkach z wykładów (zob. Sekcja 2.2.3) lub przeczytać oryginalny artykuł Tworzenie trwałych struktur danych . Jeśli twój wykres obiektowy ma ograniczoną łączność (np. Struktury drzewiaste), możesz nawet osiągnąć zamortyzowaną złożoność O (1) zarówno dla odczytu, jak i aktualizacji niezmiennego wykresu, co jest imponujące.

Chodzi o to, że każdy obiekt oprócz przechowywania swojego obecnego niezmiennego stanu, rezerwuje miejsce na rejestrowanie zmian. Jeśli chcesz utworzyć nowy niezmienny wykres z istniejącego poprzez zastosowanie zmian, musisz wziąć pod uwagę dwa przypadki:

• Obiekt, który chcesz zmienić, ma jeszcze miejsce na zmiany. Możesz przechowywać zmiany bezpośrednio w obiekcie.

• W obiekcie nie ma już miejsca na zmiany. Tworzysz nowe wystąpienie na podstawie bieżących wartości i pustych rekordów zmian. Teraz musisz rekurencyjnie aktualizować wszystkie obiekty odwołujące się do starego obiektu, aby odwoływały się do nowego obiektu.

  Jeśli w samym obiekcie odniesienia jest jeszcze miejsce na zmiany, można zapisać zmianę w odwołaniu bezpośrednio, w przeciwnym razie nastąpi ona kaskadowo.

Chociaż ten schemat obsługuje wydajne tworzenie nowych generacji niezmiennych wykresów obiektów, komplikuje czytanie z niego, ponieważ teraz musisz określić, do której „wersji” chcesz uzyskać dostęp podczas odczytywania danych z niezmiennego obiektu. Wynika to z faktu, że niezmienny obiekt może zawierać informacje dla wielu wersji z powodu zapisanych zapisów zmian, dlatego musisz określić, którą wersję chcesz obejrzeć.

Podczas implementacji staram się ukryć tę złożoność w interfejsie API. Odnosząc się do czegoś na niezmiennym wykresie z zewnątrz, używam wygenerowanych kodów pośredniczących zamiast bezpośrednich odniesień, więc osoby dzwoniące nie muszą ręcznie przekazywać żądanej wersji. To sprawia, że ​​referencje są nieco droższe niż bezpośredni wskaźnik, ale uważam, że jest to warte wygody.