Wydajność czysto funkcjonalnego programowania


397

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?


6
To samo, co w przypadku programowania imperatywnego, cokolwiek to jest.
R. Martinho Fernandes,

3
@jldupont: Aby oczywiście zwrócić wynik obliczenia. Istnieje wiele programów wolnych od skutków ubocznych. Po prostu nie potrafią nic więcej niż obliczyć na podstawie danych wejściowych. Ale to wciąż przydatne.
czerwiec

24
Mogę zrobić to tak źle, jak chcesz, źle pisząc mój kod funkcjonalny! * uśmiech * Myślę, że pytasz „czy jest jakiś problem, dla którego najlepiej znany algorytm nieniszczący jest asymptotycznie gorszy od najlepiej znanego algorytmu niszczącego, a jeśli tak, to o ile?”… czy to prawda? ?
itowlson

2
czy możesz podać przykład interesującego cię spowolnienia. twoje pytanie jest nieco niejasne.
Peter Recore,

5
Użytkownik usunął swoją odpowiedź, ale twierdził, że funkcjonalna wersja problemu 8-królowych działała w ciągu minuty dla n = 13. Przyznał, że nie był on „napisany bardzo dobrze”, więc postanowiłem napisać własną wersję 8 królowych w F #: pastebin.com/ffa8d4c4 . Nie trzeba dodawać, że mój program o funkcjach czystych oblicza n = 20 w nieco ponad sekundę.
Juliet

Odpowiedzi:


531

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


50
Pippinger jest niekwestionowanym autorytetem w tej kwestii. Należy jednak podkreślić, że jego wyniki są teoretyczne , a nie praktyczne. Jeśli chodzi o uczynienie funkcjonalnych struktur danych praktycznymi i wydajnymi, nie można zrobić nic lepszego niż Okasaki.
Norman Ramsey

6
itowlson: Muszę przyznać, że nie przeczytałem wystarczająco dużo Pippenger, aby odpowiedzieć na twoje pytanie; został opublikowany w czasopiśmie recenzowanym, cytowanym przez Okasaki, i przeczytałem go wystarczająco dużo, aby stwierdzić, że jego twierdzenia są istotne dla tego pytania, ale niewystarczające do zrozumienia dowodu. Bezpośrednim wynos że mam do rzeczywistych konsekwencji jest to, że jest trywialny przekonwertować O ( n algorytm) zanieczyszczony się w czasie O ( n log n ) Czysty, po prostu symulacja pamięci zmieniony poprzez zrównoważoną drzewo binarne. Są problemy, których nie da się lepiej; Nie wiem, czy są one czysto teoretyczne.
Brian Campbell

3
Wynik Pippengera przyjmuje dwa ważne założenia, które ograniczają jego zakres: uwzględnia obliczenia „on-line” lub „reaktywne” (nie jest to zwykły model obliczeń odwzorowujących skończone dane wejściowe na pojedyncze dane wyjściowe) oraz obliczenia „symboliczne”, w których dane wejściowe są sekwencjami atomy, które można testować tylko pod kątem równości (tzn. interpretacja danych wejściowych jest niezwykle prymitywna).
Chris Conway,

2
Bardzo dobra odpowiedź; Chciałbym dodać, że dla czysto funkcjonalnych języków nie ma uniwersalnie uzgodnionego modelu złożoności obliczeniowej, podczas gdy w nieczystym świecie jednostkowa pamięć RAM jest stosunkowo standardowa (więc to utrudnia porównywanie rzeczy). Zauważ też, że górną granicę różnicy Lg (N) w czystym / nieczystym można bardzo intuicyjnie wytłumaczyć, patrząc na implementację tablic w czystym języku (kosztuje lg (n) na operację (i dostajesz historię)) .
user51568

4
Ważna uwaga: staranne przełożenie specyfikacji czysto funkcjonalnej na bardziej skomplikowaną, wydajną implementację czysto funkcjonalną ma niewielką korzyść, jeśli ostatecznie - automatycznie lub ręcznie - przełożysz ją na jeszcze bardziej wydajny nieczysty kod. Zanieczyszczenie nie jest tak wielkim problemem, jeśli można go trzymać w klatce, np. Zamykając go w funkcji zewnętrznej bez efektów ubocznych.
Robin Green,

44

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).


3
Jeśli zestaw danych mieści się w pamięci fizycznej, dostęp do niego to O (1), ponieważ można znaleźć absolutną górną granicę czasu na odczyt dowolnego elementu. Jeśli zestaw danych nie, mówisz o We / Wy i to będzie zdecydowanie dominujący czynnik, jednak program jest napisany.
Donal Fellows

Oczywiście mówię o operacjach O (log n) dostępu do pamięci zewnętrznej. Jednak w każdym razie mówiłem bs: pamięć zewnętrzna może być również adresowalna przez O (1) ...
jkff

2
Myślę, że jedną z największych rzeczy, które programowanie imperatywne zyskuje w porównaniu z programowaniem funkcjonalnym, jest możliwość przechowywania odniesień do wielu różnych aspektów jednego stanu i generowania nowego stanu, tak aby wszystkie te odniesienia wskazywały na odpowiednie aspekty nowego stanu. Korzystanie z programowania funkcjonalnego wymagałoby zastąpienia bezpośrednich operacji dereferencyjnych operacjami wyszukiwania w celu znalezienia odpowiedniego aspektu konkretnej wersji bieżącego stanu ogólnego.
supercat

Nawet model wskaźnika (dostęp do pamięci O (log n), luźno mówiąc) nie jest fizycznie realistyczny w bardzo dużych skalach. Prędkość światła ogranicza szybkość, z jaką różne urządzenia komputerowe mogą się ze sobą komunikować, podczas gdy obecnie uważa się, że maksymalna ilość informacji, jaką można przechowywać w danym regionie, jest ograniczona jego powierzchnią.
dfeuer

36

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ć? :)


4

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ść.


6
Stała górna granica wykorzystania pamięci nie polega na tym, jak ludzie analizują tego rodzaju rzeczy; zakładasz dowolnie dużą, ale skończoną pamięć. Wdrażając algorytm, jestem zainteresowany tym, jak skaluje się od najprostszych danych wejściowych do dowolnych dowolnych rozmiarów danych wejściowych. Jeśli nałożysz ustaloną górną granicę wykorzystania pamięci, dlaczego nie nałożysz również stałej górnej granicy czasu, na jaki pozwolisz na obliczenia, i powiesz, że wszystko jest O (1)?
Brian Campbell

@Brian Campbell: To prawda. Po prostu sugeruję, że gdybyś chciał, możesz zignorować różnicę współczynnika stałego w wielu przypadkach w praktyce. Nadal trzeba pamiętać o różnicy w kompromisie między pamięcią a czasem, aby upewnić się, że użycie m razy większej ilości pamięci skraca czas działania przynajmniej o współczynnik log (m).
Brian

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.