Czy cała mapa została skopiowana po włożeniu nowego powiązania?

Question

Chciałbym lepiej poznać praktykantów z m.in. Data.Map. Kiedy wstawiam nowe wiązanie w Mapie, to z powodu niezmienności danych otrzymuję nową strukturę danych, która jest identyczna ze starą strukturą danych plus nowe powiązanie.

Chciałbym zrozumieć, w jaki sposób zostało to osiągnięte. Czy kompilator ostatecznie implementuje to przez kopiowanie całej struktury danych za pomocą np. miliony wiązań? Czy można ogólnie powiedzieć, że zmienne struktury/tablice danych (np. Data.Judy) lub imperatywne języki programowania działają lepiej w takich przypadkach? Czy dane niezmienne mają jakąkolwiek przewagę, jeśli chodzi o słowniki/magazyny klucz-wartość?

Answer 1

Map jest zbudowany na strukturze danych drzewa. Zasadniczo, nowa Map wartość jest skonstruowana jako, ale zostanie wypełniona prawie w całości za pomocą wskaźników do struktury starej. Ponieważ wartości nigdy się nie zmieniają w Haskell, jest to bezpieczna i bardzo ważna optymalizacja, znana jako udostępnianie.

Oznacza to, że można zawiesić wiele podobnych wersji tej samej struktury danych, ale tylko gałęzie drzewa, które różnią się od siebie; reszta będzie po prostu wskazówkami do oryginalnej kopii oddziału. I oczywiście, jeśli wyrzucisz stare Map, zmiana gałęzi zostanie zmieniona przez śmieciarek.

Udostępnianie jest kluczem do wydajności niezmiennych struktur danych. Pomocne może być znalezienie this Wikipedia article; ma kilka pouczających wykresów pokazujących, jak zmodyfikowane dane są reprezentowane przez udostępnianie.

Answer 2

nr The documentation for Data.Map.insert stwierdza, że ​​wprowadzanie odbywa O (log n) czasu. Niemożliwe byłoby spełnienie tej granicy, gdyby musiała skopiować całą strukturę.

Answer 3

Data.Map nie kopiuje starej mapy; to (leniwie) przydziela O (log N) nowe węzły, które wskazują (i tym samym dzielą) większość starej mapy.

Ponieważ "aktualizacja" mapy nie zakłóca starych wersji, ten rodzaj danych daje większą swobodę w budowaniu równoległych algorytmów.