Efektywność programowania czysto funkcjonalnego
Czy ktoś wie, jakie jest najgorsze możliwe spowolnienie asymptotyczne, które może się zdarzyć przy programowaniu czysto funkcjonalnym, a nie imperatywnym (czyli dopuszczaniu efektów ubocznych)?
Wyjaśnienie z komentarza itowlsona: czy jest jakiś problem, dla którego najbardziej znany algorytm nieniszczący jest asymptotycznie gorszy od najbardziej znanego algorytmu destrukcyjnego, a jeśli tak, to o ile?
6 answers
Zgodnie z Pippenger [1996] , porównując system Lispu, który jest czysto funkcjonalny (i ma ścisłą semantykę oceny, a nie leniwy) do takiego, który może mutować dane, algorytm napisany dla nieczystego Lispu, który działa w O (n log n ) time (oparty na na temat pracy BEN-Amram i Galil[1992] o symulowaniu pamięci dostępu losowego za pomocą tylko wskaźników). Pippenger stwierdza również, że istnieją algorytmy, dla których jest to najlepsze, co możesz zrobić; istnieją problemy, które są O ( n ) w systemie nieczystym, które są Ω ( N log n ) w systemie czystym.
Jest kilka zastrzeżeń do tego papieru. Najbardziej znaczące jest to, że nie dotyczy leniwych języków funkcyjnych, takich jak Haskell. Bird, Jones i De Moor[1997] pokazują, że problem skonstruowany przez Pippengera można rozwiązać w leniwym języku funkcyjnym w O (N) Czas, ale nie ustalają (i z tego co wiem, nikt nie ma), czy leniwy język funkcjonalny może rozwiązać wszystkie problemy w tym samym czasie bezobjawowym, co język z mutacją.
Problem skonstruowany przez Pippengera wymaga Ω ( N log n ) jest skonstruowany specjalnie w celu osiągnięcia tego rezultatu i niekoniecznie jest reprezentatywny dla praktycznych, rzeczywistych problemów. 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 dostępu do przyszłych danych wejściowych, i że dane wejściowe składają się z sekwencji atomów z nieograniczonego zbioru możliwych atomów, a nie ze stałego zestawu rozmiarów. W artykule przedstawiono jedynie wyniki nieczystego algorytmu liniowego czasu pracy; w przypadku problemów, które wymagają większego czasu pracy, możliwe jest, że dodatkowy O (log n) współczynnik widziany w liniowym problem może być "wchłonięty" w procesie dodatkowych operacji niezbędnych dla algorytmów o dłuższych czasach działania. Te wyjaśnienia i otwarte pytania zostały omówione krótko przez Ben-Amram [1996].
W praktyce wiele algorytmów może być zaimplementowanych w czystym języku funkcjonalnym z taką samą efektywnością, jak w języku z zmiennymi strukturami danych. Aby uzyskać dobre informacje na temat technik stosowanych do efektywnego wdrażania czysto funkcjonalnych struktur danych, zobacz "czysto funkcjonalne struktury danych" Chrisa Okasaki [Okasaki 1998] (która jest rozszerzoną wersją jego tezy [Okasaki 1996] ).
Każdy, kto potrzebuje zaimplementować algorytmy na czysto funkcjonalnych strukturach danych, powinien przeczytać Okasaki. W najgorszym przypadku można uzyskać spowolnienie O(log n) na operację, symulując zmienną pamięć ze zrównoważonym drzewem binarnym, ale w wielu przypadkach można to zrobić znacznie lepiej, a Okasaki opisuje wiele przydatnych technik, od amortyzowanych technik do tych w czasie rzeczywistym, które wykonują amortyzowaną pracę stopniowo. Czysto funkcjonalne struktury danych mogą być nieco trudne do pracy i analizy, ale zapewniają wiele korzyści, takich jak przejrzystość referencyjna, które są pomocne w optymalizacji kompilatora, w obliczeniach równoległych i rozproszonych oraz we wdrażaniu funkcji, takich jak wersjonowanie, cofanie i wycofywanie.
Zauważ również, że wszystko to omawia tylko asymptotyczne czasy działania. Wiele technik wdrażania czysto funkcjonalne struktury danych dają pewną ilość stałego spowolnienia czynnika, ze względu na dodatkową księgowość niezbędną do ich działania i szczegóły implementacji danego języka. Korzyści płynące z czysto funkcjonalnych struktur danych mogą przeważać nad tymi stałymi spowolnieniami czynników, więc na ogół będziesz musiał dokonać kompromisów w oparciu o omawiany problem.
Referencje
- Ben-Amram, Amir I Galil, Zvi 1992. "o wskaźnikach a adresach" Dziennik 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, Uniwersytet Kopenhaski, Dania
Bird, Richard, Jones, Geraint, And De Moor, Oege 1997. "więcej pośpiechu, mniej prędkości: leniwy vs gorliwa ocena" Journal of Functional Programming 7, 5 s. 541-547, wrzesień 1997
Okasaki, Chris 1996. "Czysto Funkcjonalne Struktury Danych" Praca Doktorska, Carnegie Mellon University
Okasaki, Chris 1998. W 2011 roku, po raz pierwszy w Polsce, w Polsce i za granicą, w 2012 roku, w Polsce i za granicą.]}
Pippenger, Nicholas 1996. [1]}"Pure Versus Impure Lisp" ACM Symposium on Principles of Programming Languages, pages 104-109, January 1996
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-23 14:52:40
Istnieje rzeczywiście kilka algorytmów i struktur danych, dla których nie jest znane żadne asymptotycznie efektywne rozwiązanie czysto funkcjonalne (T.i. jedno możliwe do implementacji w rachunku lambda), nawet z lenistwem.
- wspomniany związek-znajdź
- tabele Hash
- Tablice
- niektóre algorytmy grafowe
- ...
Zakładamy jednak, że w językach "imperatywnych" dostęp do pamięci jest O(1), podczas gdy w teorii nie może być tak asymptotycznie (tzn. dla unbounded problem sizes) i dostęp do pamięci w obrębie ogromnego zbioru danych jest zawsze O (log n), które można emulować w języku funkcjonalnym.
Musimy również pamiętać, że w rzeczywistości wszystkie współczesne języki funkcyjne dostarczają zmiennych danych, a Haskell dostarcza je nawet bez poświęcania czystości (ST monad).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-04-12 07:12:14
Ten artykuł twierdzi, że znane czysto funkcjonalne implementacje algorytmu union-find mają gorszą asymptotyczną złożoność niż ten, który publikują, który 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że być równoległy, daje wyobrażenie o informatyzacji / obiektywizmie społeczność programowania funkcyjnego w tych sprawach.
EDIT:
Komentarze poniżej wskazują, że tendencyjne omówienie zalet i wad czystego programowania funkcyjnego może nie pochodzić z"Społeczności programowania funkcyjnego". Słuszna Uwaga. Być może zwolennicy, których widzę, są po prostu, cytując komentarz, "analfabetami".
Na przykład, myślę, że ten wpis na blogu jest napisany przez kogoś, kto można by powiedzieć, że jest przedstawicielem społeczności programowania funkcyjnego i ponieważ jest to lista "punktów do leniwej oceny", byłoby dobrym miejscem, aby wspomnieć o wszelkich wadach, które może mieć leniwe i czysto funkcjonalne programowanie. Dobre miejsce byłoby w miejsce następujących (technicznie prawdziwe, ale stronnicze do tego stopnia, że nie jest śmieszne):
Jeśli ścisła funkcja ma złożoność O(f(n)) w języku ścisłym, to ma złożoność o(f(n)) również w języku leniwym. Po co się martwić? :)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-01-21 16:47:26
Ze stałą górną granicą użycia pamięci, nie powinno być żadnej różnicy.
Szkic dowodu: Biorąc pod uwagę stałą górną granicę użycia pamięci, należy być w stanie napisać maszynę Wirtualną, która wykonuje imperatywny zestaw instrukcji o takiej samej asymptotycznej złożoności, jak gdybyś faktycznie wykonywała na tej maszynie. Dzieje się tak, ponieważ możesz zarządzać zmienną pamięcią jako trwałą strukturą danych, dając O(log (n)) odczyt i zapis, ale ze stałą górną granicą użycia pamięci, możesz może mieć określoną ilość pamięci, powodując ich rozpad do O(1). Tak więc implementacja funkcjonalna może być wersją imperatywną działającą w implementacji funkcjonalnej maszyny wirtualnej, a więc obie powinny mieć taką samą złożoność asymptotyczną.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-01-02 04:13:20
Proponuję przeczytać na Wydajność Haskell, a następnie spojrzeć na benchmarki gry wydajność dla języków funkcyjnych vs proceduralnych/oo te.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-06-05 20:19:04
"funkcjonalne" to kilka różnych funkcji, z których każda jest niezależnie użyteczna, a jej bardziej przydatne jest spojrzenie na każdą z osobna.
Niezmienność
Teraz, kiedy już się z tym zapoznałem, za każdym razem, gdy mogę ujść na sucho z zwróceniem niezmiennego wyniku, zawsze staram się to robić, nawet w programie zorientowanym obiektowo. Łatwiej jest rozumować o programie, jeśli masz dane typu wartości.
Funkcje jako typy klasy pierwszej
Whatever you want to nazwij to, przekazywanie delegatów, działań lub funkcji, jest naprawdę poręcznym sposobem rozwiązania całej klasy rzeczywistych problemów świata, takich jak "dziura w środku wzór".
Możliwość komponowania funkcji (na przykład Zamiana akcji w akcję jest również bardzo przydatna w niektórych scenariuszach.
Powinniśmy również zwrócić uwagę na składnię Lambda, ponieważ składnię Lambda otrzymujemy tylko wtedy, gdy promujemy funkcje do typów klas pierwszych. Składnia Lambda może być bardzo wyrazista i zwięzłe.
Monady
To subtelna, ale bardzo potężna konstrukcja. Jest tak samo potężny jak słowo kluczowe yield używane do tworzenia klas IEnumerable w C#. Zasadniczo to budowanie maszyny stanowej dla ciebie pod przykrywką, ale twoja logika wygląda liniowo.
Lazy Evaluation & Recursion
Poskładałem je do kupy, bo chociaż są zawsze wrzucane jako cechy programowania funkcyjnego, to tak szybko trafiły w coś innego-imperatyw języki, które trudno już nazwać funkcjonalnymi.
S-Wyrażenia
Chyba Nie wiem, gdzie to umieścić, ale zdolność do traktowania kodu skompilowanego jako obiektu (i sprawdzania/modyfikowania go), takiego jak Lisp S-Expressions, czy LINQ Expressions, jest pod pewnymi względami najpotężniejszym narzędziem programowania funkcyjnego. Większość nowych interfejsów. NET "fluent" i DSL używa kombinacji składni lambda i wyrażeń LINQ do tworzenia bardzo zwięzłych interfejsów API. Nie wspominając Linq2Sql / Linq2Nhibernate gdzie twój kod C# jest" magicznie " wykonywany jako SQL zamiast jako kod C#.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-08-15 06:54:45