Bagaimana kompleksitas algoritma dimodelkan untuk bahasa fungsional?

Kompleksitas algoritma dirancang untuk tidak tergantung pada detail level yang lebih rendah tetapi didasarkan pada model imperatif, mis. Akses array dan memodifikasi sebuah node dalam sebuah pohon membutuhkan waktu O (1). Ini tidak terjadi dalam bahasa fungsional murni. Daftar Haskell membutuhkan waktu linier untuk akses. Memodifikasi sebuah simpul dalam pohon melibatkan pembuatan salinan baru dari pohon tersebut.

Haruskah ada pemodelan alternatif kompleksitas algoritma untuk bahasa fungsional?

algorithm-analysis runtime-analysis computation-models functional-programming wsaleem
sumber

Ini mungkin yang Anda cari.

Aristu

Pertanyaan Anda mungkin dijawab di sini: cs.stackexchange.com/q/18262/755 . Khususnya, kompleksitas waktu dalam bahasa fungsi murni berbeda dari kompleksitas waktu dalam bahasa imperatif paling banyak rasio , untuk beberapa asumsi yang sesuai pada kemampuan kedua bahasa.

O (\log n)

$O(\log n)$

GHC Haskell mendukung array dan pohon yang bisa berubah dan yang lainnya, memungkinkan Anda untuk melakukan akses array dan memodifikasi simpul pohon dalam waktu O (1), menggunakan "status thread" ( STmonad).

Tanner Swett

@BobJarvis Tergantung. Apakah daftar merupakan tipe data abstrak untuk Anda, atau apakah Anda secara khusus mempertimbangkan daftar yang ditautkan?

Raphael

Apa tujuan yang Anda cari untuk memodelkan kompleksitas algoritmik? Apakah Anda mencari sesuatu yang murni secara matematis, atau sesuatu yang praktis? Untuk nilai praktis, harus memperhatikan hal-hal seperti apakah Anda memiliki hafalan tersedia atau tidak untuk Anda, tetapi dari sudut pandang matematis murni, kemampuan implementasi seharusnya tidak menjadi masalah.

Cort Ammon

Jawaban:

Jika Anda berasumsi bahwa -calculus adalah model bahasa pemrograman fungsional yang baik, maka orang mungkin berpikir: the -calculus memiliki gagasan kompleksitas waktu yang tampaknya sederhana: cukup hitung jumlah langkah pengurangan . $\lambda$ $\lambda$ $\beta$ $(\lambda x.M)N \rightarrow M[N/x]$

Tetapi apakah ini ukuran kompleksitas yang baik?

Untuk menjawab pertanyaan ini, pertama-tama kita harus menjelaskan apa yang kita maksud dengan ukuran kompleksitas. Satu jawaban yang baik diberikan oleh tesis Slot dan van Emde Boas : segala ukuran kompleksitas yang baik harus memiliki hubungan polinomial dengan gagasan kanonik kompleksitas waktu yang didefinisikan menggunakan mesin Turing. Dengan kata lain, harus ada penyandian yang 'masuk akal' Dari istilah -calculus ke mesin Turing, seperti untuk beberapa polinomial , dalam kasus ini untuk setiap istilah ukuran: direduksi menjadi nilai dalam -pengurangan langkah tepat saat berkurang menjadi nilai $tr(.)$ $\lambda$ $p$ $M$ $|M|$ $M$ $p(|M|)$ $\beta$ $tr(M)$ $p(|tr(M)|)$ langkah-langkah mesin Turing.

Untuk waktu yang lama, tidak jelas apakah ini dapat dicapai dalam kalkulus λ. Masalah utama adalah sebagai berikut.

Ada istilah yang menghasilkan bentuk normal (dalam jumlah polinomial langkah) yang berukuran eksponensial. Bahkan menuliskan bentuk normal membutuhkan waktu yang eksponensial.
Strategi reduksi yang dipilih memainkan peran penting. Sebagai contoh, ada sekumpulan istilah yang berkurang dalam jumlah polinomial dari langkah-langkah β paralel (dalam arti optimal λ-reduksi ), tetapi yang kerumitannya non-elementer (artinya lebih buruk daripada eksponensial).

Makalah " Pengurangan Beta adalah Invariant, Memang " oleh B. Accattoli dan U. Dal Lago mengklarifikasi masalah ini dengan menunjukkan pengkodean 'masuk akal' yang menjaga kompleksitas kelas P fungsi waktu polinomial, dengan asumsi pengurangan panggilan-nama dengan nama paling kiri dari luar . Wawasan utama adalah ledakan eksponensial hanya dapat terjadi karena alasan 'tidak menarik' yang dapat dikalahkan dengan pembagian yang tepat. Dengan kata lain, kelas P sama apakah Anda mendefinisikannya dengan menghitung langkah mesin Turing atau (paling kiri) -pengurangan. $\beta$

Saya tidak yakin apa situasinya untuk strategi evaluasi lainnya. Saya tidak menyadari bahwa program serupa telah dilakukan untuk kompleksitas ruang.

Martin Berger
sumber

Kompleksitas algoritma dirancang untuk tidak tergantung pada detail level yang lebih rendah.

Tidak terlalu. Kami selalu menghitung operasi dasar dalam beberapa model mesin:

Langkah-langkah untuk mesin Turing.
Operasi dasar pada RAM.

Anda mungkin berpikir dari keseluruhan / / -Bisnis. Meskipun benar bahwa Anda dapat mengabstraksi beberapa detail implementasi dengan asimtotik Landau, Anda tidak menyingkirkan dampak dari model mesin. Algoritma memiliki waktu operasi yang sangat berbeda, katakanlah TM dan RAM - bahkan jika Anda hanya mempertimbangkan -classes! $\Omega$ $\Theta$ $O$ $\Theta$

Karenanya, pertanyaan Anda memiliki jawaban sederhana: perbaiki model mesin dan "operasi" mana yang harus dihitung. Ini akan memberi Anda sebuah ukuran. Jika Anda ingin hasil yang dapat dibandingkan dengan algoritma non-fungsional, sebaiknya Anda mengkompilasi program Anda ke RAM (untuk analisis algoritma) atau TM (untuk teori kompleksitas), dan menganalisis hasilnya. Teorema transfer mungkin ada untuk memudahkan proses ini.

Raphael
sumber

Sepakat. Catatan: Orang yang sering membuat banyak kesalahan tentang apa operasi yang "konstan". Misalkan mengasumsikan a + b adalah O(1)ketika itu benarO(log ab)

Paul Draper

@ PaulDraper Itu asumsi yang berbeda, belum tentu kesalahan. Kita dapat memodelkan apa yang kita inginkan - pertanyaannya adalah apakah itu menjawab pertanyaan yang menarik. Lihat juga di sini .

Raphael

yang terdengar sangat mengerikan seperti "singkirkan model mesin"

Paul Draper

@PaulDraper Tergantung pada jenis sentimen yang Anda lampirkan pada kata "mesin". Lihat juga diskusi ini . FWIW, model RAM unit-cost - bisa dibilang model standar dalam analisis algoritma! - adalah berguna, jika tidak maka tidak akan digunakan selama beberapa dekade sekarang. Semua batasan yang umum untuk penyortiran, pencarian, dll. Didasarkan pada model itu. Masuk akal karena memodelkan komputer nyata selama nomornya sesuai dengan register.

Raphael

Alih-alih merumuskan ukuran kompleksitas Anda dalam hal beberapa mesin abstrak yang mendasari, Anda dapat memanggang biaya ke dalam definisi bahasa itu sendiri - ini disebut Dynamics Biaya . Satu melampirkan biaya untuk setiap aturan evaluasi dalam bahasa, dengan cara komposisi - yaitu, biaya operasi adalah fungsi dari biaya sub-ekspresi. Pendekatan ini paling alami untuk bahasa fungsional, tetapi dapat digunakan untuk bahasa pemrograman yang terdefinisi dengan baik (tentu saja, kebanyakan bahasa pemrograman sayangnya tidak terdefinisi dengan baik).

kepala kebun
sumber

<Diskusi tentang apa itu model mesin yang dihapus.> Mari kita lanjutkan diskusi ini dalam obrolan .

Raphael