Jak modeluje się złożoność algorytmu dla języków funkcjonalnych?

Złożoność algorytmu została zaprojektowana w taki sposób, aby była niezależna od szczegółów niższego poziomu, ale opiera się na modelu imperatywnym, np. Dostęp do tablicy i modyfikowanie węzła w drzewie zajmuje O (1). Nie dotyczy to wyłącznie języków funkcjonalnych. Dostęp do listy Haskell zajmuje liniowy czas. Modyfikowanie węzła w drzewie wymaga wykonania nowej kopii drzewa.

Czy zatem powinno istnieć alternatywne modelowanie złożoności algorytmu dla języków funkcjonalnych?

— wsaleem
źródło

To może być to, czego szukasz.

— Aristu

Odpowiedź na twoje pytanie może być tutaj: cs.stackexchange.com/q/18262/755 . W szczególności złożoność czasowa w języku czysto funkcjonalnym różni się od złożoności czasowej w języku imperatywnym maksymalnie o stosunek , dla niektórych odpowiednich założeń dotyczących możliwości obu języków.

O (\log n)

$O(\log n)$

— DW

GHC Haskell obsługuje zmienne tablice i drzewa i tym podobne, umożliwiając dostęp do tablicy i modyfikowanie węzłów drzew w czasie O (1), przy użyciu „wątków stanu” ( STmonad).

— Tanner Swett,

@BJJvisvis Zależy. Czy lista jest dla Ciebie abstrakcyjnym typem danych, czy konkretnie rozważasz listy połączone?

— Raphael

W jakim celu szukasz modelowania złożoności algorytmicznej? Szukasz czegoś, co jest matematycznie czyste, czy czegoś praktycznego? Dla praktycznej wartości należy zwrócić uwagę na takie rzeczy, jak to, czy masz dostępne zapamiętywanie, ale z matematycznego purystycznego punktu widzenia możliwości wdrożenia nie powinny mieć znaczenia.

— Cort Ammon

Odpowiedzi:

Jeśli założymy, że rachunek jest dobrym modelem funkcjonalnych języków programowania, można pomyśleć: rachunek ma pozornie proste pojęcie złożoności czasowej: wystarczy policzyć liczbę kroków redukcji . $\lambda$ $\lambda$ $\beta$ $(\lambda x.M)N \rightarrow M[N/x]$

Ale czy to dobra miara złożoności?

Aby odpowiedzieć na to pytanie, powinniśmy przede wszystkim wyjaśnić, co rozumiemy przez miarę złożoności. Dobrą odpowiedź daje teza Slot i van Emde Boasa : każda dobra miara złożoności powinna mieć wielomianowy związek z kanonicznym pojęciem złożoności czasowej zdefiniowanej za pomocą maszyn Turinga. Innymi słowy, powinno istnieć „rozsądne” kodowanie Od terminów rachunek do maszyn Turinga, takich jak dla niektórych wielomianów , jest tak, że dla każdego terminu o rozmiarze : zmniejsza się do wartości w $tr(.)$ $\lambda$ $p$ $M$ $|M|$ $M$ krokiredukcjidokładnie wtedy, gdy zmniejsza się do wartości w kroków maszyny Turinga. $p(|M|)$ $\beta$ $tr(M)$ $p(|tr(M)|)$

Przez długi czas nie było jasne, czy można to osiągnąć za pomocą rachunku λ. Główne problemy są następujące.

Istnieją terminy, które tworzą normalne formy (wielomianowe kroki), które mają wielkość wykładniczą. Nawet zapisywanie normalnych formularzy zajmuje dużo czasu.
Wybrana strategia redukcji odgrywa ważną rolę. Na przykład istnieje rodzina terminów, która zmniejsza wielomianową liczbę równoległych kroków β (w sensie optymalnej redukcji λ ), ale których złożoność nie jest elementarna (co oznacza gorsze niż wykładnicze).

$\beta$

Nie jestem pewien, jaka jest sytuacja w przypadku innych strategii oceny. Nie wiem, czy podobny program został przeprowadzony dla złożoności przestrzeni.

— Martin Berger
źródło

Złożoność algorytmu została zaprojektowana w taki sposób, aby była niezależna od szczegółów niższego poziomu.

Nie, nie bardzo. Zawsze liczymy operacje elementarne w niektórych modelach maszyn:

Kroki dla maszyn Turinga.
Podstawowe operacje na pamięciach RAM.

$\Omega$ $\Theta$ $O$ $\Theta$

Dlatego twoje pytanie ma prostą odpowiedź: napraw model maszyny i które „operacje” policzyć. To daje do środka. Jeśli chcesz, aby wyniki były porównywalne z niefunkcjonalnymi algorytmami, najlepiej byłoby skompilować swoje programy do pamięci RAM (do analizy algorytmów) lub TM (do teorii złożoności) i przeanalizować wynik. Twierdzenia o przeniesieniu mogą istnieć, aby ułatwić ten proces.

— Raphael
źródło

Zgoda. Dygresja: Ludzie mają często sprawiają wiele błędów o jakie operacje są „stałe”. Na przykład założenie, że a + b jest O(1)wtedy, gdy jest naprawdęO(log ab)

— Paul Draper,

@PaulDraper To inne założenie, niekoniecznie błąd. Możemy modelować to, co chcemy - pytanie brzmi, czy odpowiada na interesujące pytania. Zobacz także tutaj .

— Raphael

brzmi to okropnie jak „pozbyć się modelu maszyny”

— Paul Draper,

@PaulDraper Zależy od tego, jakie sentymenty przywiązujesz do słowa „maszyna”. Zobacz także tę dyskusję . FWIW, jednostkowy model pamięci RAM - prawdopodobnie standardowy model w analizie algorytmów! - jest przydatny, inaczej nie byłby używany od dziesięcioleci. Wszystkie znane granice sortowania, wyszukiwania itp. Są oparte na tym modelu. Ma to sens, ponieważ modeluje prawdziwe komputery tak długo, jak długo mieszczą się w rejestrach.

— Raphael

Zamiast formułować miarę złożoności w odniesieniu do jakiejś podstawowej maszyny abstrakcyjnej, możesz upiec koszt w samych definicjach języka - nazywa się to Dynamiką Kosztów . Do każdej reguły oceny w języku przypisuje się koszty w sposób kompozycyjny - to znaczy, że koszt operacji jest funkcją kosztu jej podwyrażeń. Takie podejście jest najbardziej naturalne w przypadku języków funkcjonalnych, ale można je zastosować w każdym dobrze zdefiniowanym języku programowania (oczywiście większość języków programowania niestety nie jest dobrze zdefiniowana).

— ogrodnik
źródło

<Dyskusja na temat usuniętego modelu maszyny.> Kontynuujmy tę dyskusję na czacie .

— Raphael