Czy w programowaniu funkcjonalnym większość niezmiennych struktur danych wymaga większego wykorzystania pamięci?

W programowaniu funkcjonalnym, ponieważ prawie cała struktura danych jest niezmienna, kiedy stan musi się zmienić, tworzona jest nowa struktura. Czy to oznacza dużo większe zużycie pamięci? Znam dobrze paradygmat programowania obiektowego, teraz próbuję dowiedzieć się o paradygmacie programowania funkcjonalnego. Pomysł, że wszystko jest niezmienne, myli mnie. Wydawałoby się, że program wykorzystujący niezmienne struktury wymagałby znacznie więcej pamięci niż program ze zmiennymi strukturami. Czy w ogóle patrzę na to we właściwy sposób?

Jedyną prawidłową odpowiedzią na to pytanie jest „czasami”. Istnieje wiele sztuczek, których można użyć w językach funkcjonalnych, aby uniknąć marnowania pamięci. Niezmienność ułatwia udostępnianie danych między funkcjami, a nawet strukturami danych, ponieważ kompilator może zagwarantować, że dane nie zostaną zmodyfikowane. Języki funkcjonalne zachęcają do korzystania ze struktur danych, które mogą być skutecznie wykorzystywane jako niezmienne struktury (na przykład drzewa zamiast tabel skrótów). Jeśli dodasz lenistwo do miksu, jak robi to wiele języków funkcjonalnych, doda to nowe sposoby oszczędzania pamięci (to także nowe sposoby marnowania pamięci, ale nie zamierzam tego robić).

W programowaniu funkcjonalnym, ponieważ prawie cała struktura danych jest niezmienna, kiedy stan musi się zmienić, tworzona jest nowa struktura. Czy to oznacza o wiele większe zużycie pamięci?

Zależy to od struktury danych, dokładnie dokonanych zmian, a w niektórych przypadkach od optymalizatora. Jako jeden przykład rozważmy przejście do listy:

list2 = prepend(42, list1) // list2 is now a list that contains 42 followed
                           // by the elements of list1. list1 is unchanged

W tym przypadku dodatkowe zapotrzebowanie na pamięć jest stałe - podobnie jak koszty wykonania połączenia prepend. Dlaczego? Ponieważ prependpo prostu tworzy nową komórkę, która ma 42głowę i list1ogon. list2Aby to osiągnąć, nie trzeba go kopiować ani iterować w inny sposób . To znaczy, z wyjątkiem pamięci wymaganej do przechowywania 42, list2ponownie wykorzystuje tę samą pamięć, z której korzysta list1. Ponieważ obie listy są niezmienne, udostępnianie jest całkowicie bezpieczne.

Podobnie podczas pracy ze zrównoważonymi strukturami drzewa większość operacji wymaga tylko logarytmicznej ilości dodatkowego miejsca, ponieważ wszystko, oprócz jednej ścieżki drzewa, może być wspólne.

W przypadku tablic sytuacja wygląda nieco inaczej. Dlatego w wielu językach FP tablice nie są tak często używane. Jeśli jednak zrobisz coś podobnego arr2 = map(f, arr1)i arr1nigdy nie zostanie ponownie użyty po tym wierszu, inteligentny optymalizator może faktycznie utworzyć kod, który mutuje arr1zamiast tworzyć nową tablicę (bez wpływu na zachowanie programu). W takim przypadku występ będzie oczywiście jak w języku imperatywnym.

Naiwne implementacje rzeczywiście ujawniłyby ten problem - kiedy tworzysz nową strukturę danych zamiast aktualizować istniejącą w miejscu, musisz mieć narzut.

Różne języki mają różne sposoby radzenia sobie z tym, a większość z nich używa kilku sztuczek.

Jedną ze strategii jest zbieranie śmieci . W momencie, gdy nowa struktura została utworzona, lub wkrótce potem, odniesienia do starej struktury wykraczają poza zakres, a śmieciarz odbierze ją natychmiast lub wystarczająco szybko, w zależności od algorytmu GC. Oznacza to, że chociaż narzut jest nadal narzutem, jest to tylko tymczasowe i nie będzie rosnąć liniowo wraz z ilością danych.

Kolejnym jest wybieranie różnych rodzajów struktur danych. Tam, gdzie tablice są podstawową strukturą danych listy w imperatywnych językach (zwykle zapakowane w pewnego rodzaju kontener dynamicznej realokacji, taki jak std::vectorw C ++), języki funkcjonalne często preferują listy połączone. W przypadku listy połączonej operacja poprzedzająca („wady”) może ponownie wykorzystać istniejącą listę jako ogon nowej listy, więc wszystko, co naprawdę zostanie przydzielone, to nowa głowa listy. Podobne strategie istnieją dla innych typów struktur danych - zestawów, drzew, nazywacie to.

A potem leniwa ocena à la Haskell. Chodzi o to, że tworzone struktury danych nie są w pełni tworzone natychmiast; zamiast tego są one przechowywane jako „thunks” (można je traktować jako przepisy na konstruowanie wartości, gdy jest to potrzebne). Tylko wtedy, gdy wartość jest potrzebna, thunk zostaje powiększony do wartości rzeczywistej. Oznacza to, że alokacja pamięci może zostać odroczona do czasu, gdy ocena będzie konieczna, i w tym momencie kilka łączników może być połączonych w jedną alokację pamięci.

Wiem tylko trochę o Clojure i jego niezmiennych strukturach danych .

Clojure zapewnia zestaw niezmiennych list, wektorów, zestawów i map. Ponieważ nie można ich zmienić, „dodanie” lub „usunięcie” czegoś z niezmiennej kolekcji oznacza utworzenie nowej kolekcji, takiej jak stara, ale z wymaganą zmianą. Trwałość jest terminem używanym do opisania właściwości, w której stara wersja kolekcji jest nadal dostępna po „zmianie” i że kolekcja zachowuje swoje gwarancje wydajności dla większości operacji. W szczególności oznacza to, że nowej wersji nie można utworzyć przy użyciu pełnej kopii, ponieważ wymagałoby to liniowego czasu. Nieuchronnie zaimplementowane są trwałe kolekcje przy użyciu połączonych struktur danych, dzięki czemu nowe wersje mogą współdzielić strukturę z poprzednią wersją.

Graficznie możemy przedstawić coś takiego:

(def my-list '(1 2 3))

    +---+      +---+      +---+
    | 1 | ---> | 2 | ---> | 3 |
    +---+      +---+      +---+

(def new-list (conj my-list 0))

              +-----------------------------+
    +---+     | +---+      +---+      +---+ |
    | 0 | --->| | 1 | ---> | 2 | ---> | 3 | |
    +---+     | +---+      +---+      +---+ |
              +-----------------------------+

Oprócz tego, co powiedziano w innych odpowiedziach, chciałbym wspomnieć o czystym języku programowania, który obsługuje tak zwane unikalne typy . Nie znam tego języka, ale przypuszczam, że unikalne typy obsługują pewnego rodzaju „destrukcyjną aktualizację”.

Innymi słowy, podczas gdy semantyką aktualizacji stanu jest to, że tworzysz nową wartość ze starej przez zastosowanie funkcji, ograniczenie unikatowości może pozwolić kompilatorowi na ponowne użycie obiektów danych wewnętrznie, ponieważ wie, że do starej wartości nie będzie się odwoływać więcej w programie po wygenerowaniu nowej wartości.

Aby uzyskać więcej informacji, zobacz np . Czystą stronę główną i ten artykuł w Wikipedii