Analiza złożoności algorytmu dla implementacji funkcjonalnego języka programowania

Dowiedziałem się dzisiaj, że analiza algorytmów różni się w zależności od modelu obliczeniowego. To jest coś, o czym nigdy nie myślałem ani nie słyszałem.

Przykładem podanym mi przez użytkownika @chi , który dalej to ilustruje :

Np. Rozważ zadanie: dany zwraca . W pamięci RAM można to rozwiązać w ponieważ dostęp do tablicy jest stały. Korzystając z baz TM, musimy przeskanować całe wejście, więc jest to $(i,x_1 ,…,x_n )$ $x_i$ $O(1)$ $O(n)$

To sprawia, że zastanawiam się nad językami funkcjonalnymi; Z mojego zrozumienia „Języki funkcjonalne są ściśle związane z rachunkiem lambda” (z komentarza Yuval Filmus tutaj ). Tak więc, jeśli języki funkcjonalne oparte są na rachunku lambda, ale działają na maszynach opartych na pamięci RAM, jaki jest właściwy sposób przeprowadzania analizy złożoności algorytmów implementowanych przy użyciu czysto funkcjonalnych struktur danych i języków?

Nie miałem okazji czytać czysto funkcjonalnych struktur danych, ale zajrzałem do strony Wikipedii na ten temat i wydaje się, że niektóre struktury danych zastępują tradycyjne tablice:

„Tablice można zastąpić mapą lub listą dostępu swobodnego, która dopuszcza czysto funkcjonalną implementację, ale czas dostępu i aktualizacji jest logarytmiczny”.

W takim przypadku model obliczeniowy byłby inny, prawda?

— Abdul
źródło

O (\log n)

$O(\log n)$

O (\log n)

$O(\log n)$

n

$n$

O (1)

$O(1)$

Przykładem innego modelu obliczeniowego może być liczba redukcji beta wykonanych na rachunku rachunku lambda. W FP bardziej stosujemy model barana przebrany za rachunek lambda, jeśli ma to sens

— Kurt Mueller

O (2^{n})

$O(2^n)$

O (n)

$O(n)$

Pamiętaj, że musisz także wiedzieć, czy Twój język funkcjonalny jest chętny, leniwy / ścisły czy nie-ścisły. Niedawno spotkałem się z sytuacją, w której rzeczywisty algorytm był wielomianowy w Haskell (nie ścisły), ale naiwne tłumaczenie na OCaml (ścisłe) było wykładnicze.

— Eric Lippert,

To zależy od semantyki języka funkcjonalnego. Nie można analizować algorytmów w językach programowania w oderwaniu, ponieważ nie wiadomo, co naprawdę oznaczają te instrukcje. Specyfikacja twojego języka musi zapewniać wystarczająco szczegółową semantykę. Jeśli twój język określa wszystko w kategoriach rachunku lambda, potrzebujesz pewnej miary kosztów dla redukcji (czy są to O (1) czy zależą od wielkości zredukowanego terminu?).

Myślę, że większość języków funkcjonalnych nie robi tego w ten sposób i zamiast tego dostarcza bardziej użytecznych instrukcji, takich jak „wywołania funkcji to O (1), a dopisywanie do nagłówka listy to O (1)”, takie rzeczy.

— adrianN
źródło

Wydaje mi się, że rozumiem twoją odpowiedź (nieporozumienie najprawdopodobniej wynika z mojego niezrozumienia rachunku lambda): Mówisz, że zasadniczo musisz przeprowadzić analizę indywidualnie dla każdego przypadku (przypadek jest językiem), a nie ogólny sposób, ponieważ niektóre operacje mają różne znaczenia dla poszczególnych języków. Czy moje rozumowanie jest prawidłowe?

— Abdul

Tak. Twój projektant języka musi powiedzieć ci, co właściwie oznaczają rzeczy, które możesz napisać w tym języku, zanim będziesz mógł przeanalizować czas działania algorytmu.

— adrianN

„Nie można analizować algorytmów oddzielnie dla języków programowania” - czy odnosiło się to do języków FP czy ogólnie języków? Jeśli odnosi się to do wcześniejszego, to w jaki sposób analizujemy algorytmy w szkole w tak ogólny sposób, tj. Czy analizujemy problemy w Javie, C / C ++, Python? Czy to dlatego, że wszystkie są bardzo podobne? A może dlatego, że podstawowe struktury danych i narzędzia ADT są takie same i zaimplementowane w ten sam sposób? Czy wreszcie dlatego, że te kursy są po prostu ze względu na edukację i niekoniecznie muszą być ściśle dokładne?

— Abdul

Dotyczy to wszystkich języków programowania. Aby być ściśle poprawnym, najpierw musisz naprawić model maszyny, powiedzmy RAM i (niewielką garść) obsługiwanych instrukcji. Analizę programów można wykonywać tylko przy użyciu tych instrukcji. Następnie możesz pomyśleć o odwzorowaniu języka programowania na ten model maszyny. Następnie możesz analizować programy w języku programowania. Aby uzyskać bardzo rygorystyczne leczenie, sprawdź, jak robi to Knuth w sztuce programowania komputerowego. Wiele z tego można uprościć ze względu na stałe ukrywania big-O.

— adrianN