Wydajność czysto funkcjonalnego programowania

Czy ktoś wie, jakie jest najgorsze możliwe asymptotyczne spowolnienie, które może się zdarzyć, gdy programowanie ma charakter wyłącznie funkcjonalny, a nie imperatywny (tzn. Pozwala na efekty uboczne)?

Wyjaśnienie z komentarza itowlson : czy jest jakiś problem, dla którego najlepiej znany algorytm nieniszczący jest asymptotycznie gorszy niż najlepiej znany algorytm niszczący, a jeśli tak, to o ile?

Według Pippengera [1996] , porównując system Lisp, który jest czysto funkcjonalny (i ma ścisłą semantykę oceny, a nie leniwość) z takim, który może mutować dane, można przetłumaczyć algorytm napisany dla nieczystego Lisp działającego w O ( n ) na algorytm w czystym Lisp, który działa w czasie O ( n log n ) (na podstawie pracy Ben-Amrama i Galila [1992] na temat symulacji pamięci o dostępie swobodnym przy użyciu tylko wskaźników). Pippenger ustala również, że istnieją algorytmy, dla których jest to najlepsze, co możesz zrobić; występują problemy, które są O ( n ) w nieczystym systemie, które są Ω ( n log n ) w czystym systemie.

Jest kilka ostrzeżeń dotyczących tego artykułu. Najważniejsze jest to, że nie zajmuje się leniwymi językami funkcjonalnymi, takimi jak Haskell. Bird, Jones i De Moor [1997] pokazują, że problem skonstruowany przez Pippengera można rozwiązać w leniwym języku funkcjonalnym za O ( n ) czasu, ale nie ustalają (i o ile wiem, nikt nie ma), czy lub nie leniwy język funkcjonalny może rozwiązać wszystkie problemy w tym samym asymptotycznym czasie działania, co język z mutacją.

Problem skonstruowany przez Pippenger wymaga, aby Ω ( n log n ) był specjalnie skonstruowany, aby osiągnąć ten wynik i niekoniecznie jest reprezentatywny dla praktycznych problemów w świecie rzeczywistym. Istnieje kilka ograniczeń dotyczących problemu, które są nieco nieoczekiwane, ale konieczne do działania dowodu; w szczególności problem wymaga, aby wyniki były obliczane on-line, bez możliwości uzyskania dostępu do przyszłych danych wejściowych, i że dane wejściowe składają się z sekwencji atomów z nieograniczonego zestawu możliwych atomów, a nie z zestawu o ustalonym rozmiarze. A artykuł określa jedynie (dolną granicę) wyniki dla nieczystego algorytmu liniowego czasu pracy; w przypadku problemów wymagających dłuższego czasu działania możliwe jest, że dodatkowe O (log n) współczynnik widziany w problemie liniowym może być „absorbowany” w procesie dodatkowych operacji niezbędnych dla algorytmów o dłuższym czasie działania. Te wyjaśnienia i pytania otwarte zostały krótko zbadane przez Ben-Amrama [1996] .

W praktyce wiele algorytmów można zaimplementować w czystym języku funkcjonalnym z taką samą wydajnością jak w języku ze zmiennymi strukturami danych. Dobre odniesienie do technik efektywnego wdrażania czysto funkcjonalnych struktur danych można znaleźć w „Czysto funkcjonalnych strukturach danych” Chrisa Okasakiego [Okasaki 1998] (będącym rozszerzoną wersją jego pracy [Okasaki 1996] ).

Każdy, kto musi zaimplementować algorytmy w czysto funkcjonalnych strukturach danych, powinien przeczytać Okasaki. Zawsze możesz uzyskać w najgorszym przypadku spowolnienie O (log n ) na operację, symulując zmienną pamięć za pomocą zrównoważonego drzewa binarnego, ale w wielu przypadkach możesz to zrobić znacznie lepiej, a Okasaki opisuje wiele przydatnych technik, od technik zamortyzowanych do rzeczywistych czas, który wykonuje zamortyzowaną pracę, stopniowo. Czysto funkcjonalne struktury danych mogą być nieco trudne w pracy i analizie, ale zapewniają wiele korzyści, takich jak przejrzystość referencyjna, które są pomocne w optymalizacji kompilatora, w obliczeniach równoległych i rozproszonych oraz w implementacji funkcji takich jak wersjonowanie, cofanie i wycofywanie.

Zauważ też, że wszystko to omawia tylko asymptotyczne czasy działania. Wiele technik wdrażania czysto funkcjonalnych struktur danych zapewnia ciągłe spowolnienie czynników z powodu dodatkowej księgowości niezbędnej do ich działania oraz szczegółów implementacyjnych danego języka. Korzyści z czysto funkcjonalnych struktur danych mogą przeważać nad ciągłymi spowolnieniami czynników, więc na ogół będziesz musiał dokonać kompromisów w oparciu o dany problem.

Bibliografia

• Ben-Amram, Amir i Galil, Zvi 1992. „On Pointers vs. Addresses” Journal of the ACM, 39 (3), s. 617-648, lipiec 1992
• Ben-Amram, Amir 1996. „Uwagi na temat porównania czystego i nieczystego Lisp Pippengera ” Niepublikowany rękopis, DIKU, University of Copenhagen, Dania
• Bird, Richard, Jones, Geraint i De Moor, Oege 1997. „Więcej pośpiechu, mniej prędkości: leniwa kontra chętna ocena” Journal of Functional Programming 7, 5 s. 541–547, wrzesień 1997
• Okasaki, Chris 1996. Praca doktorska „Czysto funkcjonalne struktury danych” , Carnegie Mellon University
• Okasaki, Chris 1998. „Czysto funkcjonalne struktury danych” Cambridge University Press, Cambridge, Wielka Brytania
• Pippenger, Nicholas 1996. Sympozjum ACM „Pure versus Impure Lisp” na temat zasad języków programowania, strony 104–109, styczeń 1996

Rzeczywiście istnieje kilka algorytmów i struktur danych, dla których nie jest znane żadne asymptotycznie wydajne, czysto funkcjonalne rozwiązanie (które można wdrożyć w rachunku czysto lambda), nawet z lenistwem.

• Wyżej wspomniany związek-znalezisko
• Tabele skrótów
• Tablice
• Niektóre algorytmy graficzne
• ...

Zakładamy jednak, że w „imperatywnych” językach dostęp do pamięci to O (1), podczas gdy teoretycznie nie może być tak asymptotycznie (tj. W przypadku nieograniczonych rozmiarów problemów), a dostęp do pamięci w ogromnym zbiorze danych jest zawsze O (log n) , które można emulować w języku funkcjonalnym.

Musimy również pamiętać, że właściwie wszystkie współczesne języki funkcjonalne zapewniają zmienne dane, a Haskell nawet je zapewnia bez utraty czystości (monada ST).

W tym artykule stwierdzono, że wszystkie znane czysto funkcjonalne implementacje algorytmu znajdowania związku mają gorszą asymptotyczną złożoność niż ta, którą publikują, która ma czysto funkcjonalny interfejs, ale wykorzystuje zmienne dane wewnętrznie.

Fakt, że inne odpowiedzi twierdzą, że nigdy nie może być żadnej różnicy i że na przykład jedyną „wadą” czysto funkcjonalnego kodu jest to, że można go zrównoleglać, daje wyobrażenie o świadomości / obiektywności społeczności programistów funkcjonalnych w tych sprawach .

EDYTOWAĆ:

Komentarze poniżej wskazują, że stronnicza dyskusja na temat zalet i wad czystego programowania funkcjonalnego może nie pochodzić od „społeczności programowania funkcjonalnego”. Słuszna uwaga. Być może zwolennicy, których widzę, przytaczają komentarz „niepiśmienny”.

Na przykład uważam, że ten post na blogu został napisany przez kogoś, kogo można uznać za przedstawiciela społeczności programistów funkcjonalnych, a ponieważ jest to lista „punktów do leniwej oceny”, dobrze byłoby wspomnieć o wszelkich wadach leniwe i czysto funkcjonalne programowanie. Dobrym miejscem byłoby miejsce (technicznie prawdziwe, ale tendencyjne do tego stopnia, że ​​nie jest śmieszne) zwolnienie:

Jeśli funkcja ścisła ma złożoność O (f (n)) w języku ścisłym, ma również złożoność O (f (n)) w języku leniwym. Po co się martwić? :)

Przy ustalonej górnej granicy wykorzystania pamięci nie powinno być różnicy.

Szkic próbny: Biorąc pod uwagę ustaloną górną granicę wykorzystania pamięci, powinno być możliwe napisanie maszyny wirtualnej, która wykonuje zestaw instrukcji rozkazów z taką samą asymptotyczną złożonością, jak gdybyś faktycznie wykonywał na tej maszynie. Dzieje się tak, ponieważ można zarządzać pamięcią zmienną jako trwałą strukturą danych, umożliwiającą O (log (n)) odczyt i zapis, ale ze stałą górną granicą wykorzystania pamięci, możesz mieć stałą ilość pamięci, co powoduje, że rozpad na O (1). W ten sposób funkcjonalna implementacja może być wersją imperatywną działającą w implementacji funkcjonalnej maszyny wirtualnej, dlatego oba powinny mieć tę samą asymptotyczną złożoność.

Sugerowałbym przeczytanie na temat wydajności Haskell , a następnie przyjrzenie się wydajności testów gier dla języków funkcjonalnych w porównaniu z językami proceduralnymi / OO.