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?
functional-programming
Jbemmz
źródło
źródło
Odpowiedzi:
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ć).
źródło
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:
W tym przypadku dodatkowe zapotrzebowanie na pamięć jest stałe - podobnie jak koszty wykonania połączenia
prepend
. Dlaczego? Ponieważprepend
po prostu tworzy nową komórkę, która ma42
głowę ilist1
ogon.list2
Aby to osiągnąć, nie trzeba go kopiować ani iterować w inny sposób . To znaczy, z wyjątkiem pamięci wymaganej do przechowywania42
,list2
ponownie wykorzystuje tę samą pamięć, z której korzystalist1
. 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)
iarr1
nigdy nie zostanie ponownie użyty po tym wierszu, inteligentny optymalizator może faktycznie utworzyć kod, który mutujearr1
zamiast tworzyć nową tablicę (bez wpływu na zachowanie programu). W takim przypadku występ będzie oczywiście jak w języku imperatywnym.źródło
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::vector
w 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.
źródło
Wiem tylko trochę o Clojure i jego niezmiennych strukturach danych .
Graficznie możemy przedstawić coś takiego:
źródło
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
źródło