Analisis Kompleksitas Algoritma pada implementasi bahasa pemrograman fungsional

Saya telah belajar hari ini bahwa analisis algoritma berbeda berdasarkan pada model komputasi. Itu adalah sesuatu yang tidak pernah saya pikirkan atau dengar.

Contoh yang diberikan kepada saya, yang menggambarkannya lebih lanjut, oleh Pengguna @chi adalah:

Misalnya, pertimbangkan tugas: diberikan kembalikan . Dalam RAM ini dapat diselesaikan dalam karena akses array adalah waktu konstan. Dengan menggunakan TM, kita perlu memindai seluruh input, jadi $(i,x_1 ,…,x_n )$ $x_i$ $O(1)$ $O(n)$

Ini membuat saya bertanya-tanya tentang bahasa fungsional; Dari pemahaman saya, "Bahasa fungsional terkait erat dengan kalkulus lambda" (dari komentar oleh Yuval Filmus di sini ). Jadi, jika bahasa fungsional didasarkan pada kalkulus lambda, tetapi mereka berjalan pada mesin berbasis RAM, apa cara yang tepat untuk melakukan analisis kompleksitas pada algoritma yang diimplementasikan menggunakan struktur data dan bahasa murni fungsional?

Saya belum memiliki kesempatan untuk membaca Struktur Data Murni Fungsional tetapi saya telah melihat halaman Wikipedia untuk subjek, dan tampaknya beberapa struktur data mengganti array tradisional dengan:

"Array dapat diganti dengan peta atau daftar akses acak, yang mengakui implementasi murni fungsional, tetapi waktu akses dan pembaruan adalah logaritmik."

Dalam hal itu, model komputasi akan berbeda, benar?

complexity-theory algorithm-analysis computability computation-models lambda-calculus Abdul
sumber

Saya jelas bukan ahli dalam topik ini, tapi saya yakin saya mendengar bahwa 1) mesin mirip-lisp (dengan model biaya sendiri) dapat mensimulasikan program RAM dengan faktor tambahan (ini terlihat mudah dibuktikan ), dan 2) apakah faktor ini benar-benar dibutuhkan masih merupakan masalah terbuka. Lebih lanjut, dapat dikatakan bahwa menetapkan biaya O (1) untuk mengatur array dalam model RAM terlalu murah hati. Dalam perangkat keras, akses memori harus melintasi gerbang mana adalah ukuran memori fisik.

O (\log n)

$O(\log n)$

O (\log n)

$O(\log n)$

n

$n$

chi

Juga perlu diingat bahwa hampir semua bahasa FP dunia nyata memiliki array dalam beberapa bentuk, dengan jaminan waktu akses (seperti dalam bahasa imperatif). Ini biasanya diselesaikan dengan menambahkannya sebagai bahasa primitif.

O (1)

$O(1)$

chi

Contoh dari model komputasi yang berbeda adalah jumlah reduksi beta yang dilakukan pada istilah kalkulus lambda. Di FP kita lebih menggunakan model ram yang didandani sebagai kalkulus lambda, jika itu masuk akal

Kurt Mueller

@KurtMueller Perhatikan bahwa kita bisa mendapatkan istilah lambda ukuran setelah hanya pengurangan . Ini membuat model biaya penghitungan jumlah beta tidak realistis. Yang bisa dibilang lebih baik adalah menimbang setiap langkah berdasarkan ukuran syarat yang ada. Namun, ini bukan satu-satunya model yang mungkin: evaluasi optimal istilah lambda tidak berlaku beta dengan cara naif, lebih memilih beberapa mesin pengurangan grafik yang lebih canggih. Dalam kasus seperti itu, menghitung beta mungkin tidak tepat.

O (2^{n})

$O(2^n)$

O (n)

$O(n)$

chi

Perhatikan bahwa Anda juga perlu tahu apakah bahasa fungsional Anda bersemangat atau malas / ketat atau tidak ketat. Saya baru-baru ini menghadapi situasi di mana algoritma dunia nyata polinomial di Haskell (tidak ketat) tetapi terjemahan naif ke OCaml (ketat) eksponensial.

Eric Lippert

Jawaban:

Itu tergantung pada semantik bahasa fungsional Anda. Anda tidak dapat melakukan analisis algoritma pada bahasa pemrograman secara terpisah, karena Anda tidak tahu apa arti pernyataan itu sebenarnya. Spesifikasi untuk bahasa Anda perlu memberikan semantik yang cukup rinci. Jika bahasa Anda menentukan semuanya dalam hal kalkulus lambda, Anda memerlukan ukuran biaya untuk pengurangan (apakah mereka O (1) atau apakah mereka bergantung pada ukuran istilah yang Anda kurangi?).

Saya pikir sebagian besar bahasa fungsional tidak melakukannya dan sebaliknya memberikan pernyataan yang lebih berguna seperti "panggilan fungsi adalah O (1), menambahkan ke kepala daftar adalah O (1)", hal-hal seperti itu.

adrianN
sumber

Saya yakin saya agak mengerti jawaban Anda (kesalahpahaman ini kemungkinan besar disebabkan oleh kurangnya pemahaman saya dalam lambda calculus): Anda mengatakan bahwa Anda pada dasarnya harus melakukan analisis berdasarkan kasus per kasus (berdasarkan bahasa), bukan berdasarkan cara umum, karena operasi tertentu memiliki arti berbeda per bahasa. Apakah pemahaman saya benar?

Abdul

Iya. Perancang bahasa Anda perlu memberi tahu Anda apa yang sebenarnya dapat Anda tulis dalam bahasa sebelum Anda dapat menganalisis runtime suatu algoritma.

adrianN

"Anda tidak dapat melakukan analisis algoritma pada bahasa pemrograman secara terpisah" - apakah ini merujuk pada bahasa FP atau bahasa pada umumnya? Jika itu merujuk pada yang sebelumnya, lalu bagaimana kita analisis algoritma di sekolah dengan cara yang umum yaitu melakukan analisis di seluruh Jawa, C / C ++, masalah Python? Apakah karena semuanya sangat mirip? Atau apakah karena struktur data yang mendasari & ADT semuanya sama dan diimplementasikan dengan cara yang sama juga? Atau terakhir, apakah itu karena kursus-kursus ini hanya demi pendidikan, dan tidak perlu benar - benar akurat?

Abdul

Itu berlaku untuk semua bahasa pemrograman. Agar benar-benar benar, Anda harus terlebih dahulu memperbaiki model mesin, ucapkan RAM dan (segelintir kecil) instruksi yang didukungnya. Anda hanya dapat melakukan analisis pada program hanya menggunakan instruksi tersebut. Kemudian Anda bisa memikirkan pemetaan bahasa pemrograman Anda ke model mesin itu. Kemudian Anda dapat menganalisis program dalam bahasa pemrograman. Untuk perawatan yang sangat ketat, periksa bagaimana Knuth melakukannya di The Art of Computer Programming. Banyak dari ini dapat disederhanakan karena konstanta bersembunyi-O besar.

adrianN