Efisiensi pemrograman murni fungsional

397

Adakah yang tahu perlambatan asimptotik terburuk yang mungkin terjadi saat pemrograman murni secara fungsional sebagai lawan imperatif (yaitu memungkinkan efek samping)?

Klarifikasi dari komentar oleh itowlson : adakah masalah yang algoritma non-destruktif yang paling terkenal secara asimptot lebih buruk daripada algoritma destruktif yang paling dikenal, dan jika demikian seberapa banyak?

algorithm functional-programming performance Memilih
sumber
6
Sama seperti ketika pemrograman secara imperatif, apa pun itu.
R. Martinho Fernandes
3
@ jldupont: Untuk mengembalikan hasil perhitungan, tentu saja. Ada banyak program efek samping gratis. Mereka tidak bisa melakukan banyak hal selain menghitung input mereka. Tapi itu masih berguna.
jalf
24
Saya bisa membuatnya seburuk yang Anda mau, dengan menulis kode fungsional saya dengan buruk! * nyengir * Saya pikir yang Anda tanyakan adalah "apakah ada masalah yang algoritma non-destruktif yang paling terkenal secara asimptot lebih buruk daripada algoritma destruktif yang paling dikenal, dan jika demikian seberapa banyak?" ... benarkah itu? ?
itowlson
2
dapatkah Anda memberikan contoh jenis perlambatan yang menarik bagi Anda. Pertanyaan Anda agak kabur.
Peter Recore
5
Seorang pengguna menghapus jawabannya, tetapi ia mengklaim bahwa versi fungsional dari masalah 8-queens berjalan lebih dari satu menit selama n = 13. Dia mengakui itu bukan "ditulis dengan sangat baik", jadi saya memutuskan untuk menulis versi saya sendiri dari 8 ratu di F #: pastebin.com/ffa8d4c4 . Tak perlu dikatakan, program fungsi murni saya menghitung n = 20 hanya dalam satu detik.
Juliet

Jawaban:

531

Menurut Pippenger [1996] , ketika membandingkan sistem Lisp yang murni fungsional (dan memiliki semantik evaluasi yang ketat, tidak malas) dengan yang dapat bermutasi data, suatu algoritma yang ditulis untuk Lisp yang tidak murni yang berjalan di O ( n ) dapat diterjemahkan untuk sebuah algoritma dalam Lisp murni yang berjalan dalam waktu O ( n log n ) (berdasarkan kerja oleh Ben-Amram dan Galil [1992] tentang simulasi memori akses acak menggunakan hanya pointer). Pippenger juga menetapkan bahwa ada algoritma yang merupakan yang terbaik yang dapat Anda lakukan; ada masalah yang O ( n ) dalam sistem tidak murni yang Ω ( n log n ) dalam sistem murni.

Ada beberapa peringatan tentang makalah ini. Yang paling penting adalah tidak membahas bahasa fungsional yang malas, seperti Haskell. Bird, Jones dan De Moor [1997] menunjukkan bahwa masalah yang dibangun oleh Pippenger dapat diselesaikan dalam bahasa fungsional yang malas dalam waktu O ( n ), tetapi mereka tidak membangun (dan sejauh yang saya tahu, tidak ada yang memiliki) apakah atau bukan bahasa fungsional yang malas dapat menyelesaikan semua masalah dalam waktu berjalan asimptotik yang sama dengan bahasa dengan mutasi.

Masalah yang dibangun oleh Pippenger membutuhkan Ω ( n log n ) secara khusus dibangun untuk mencapai hasil ini, dan tidak selalu mewakili masalah praktis, masalah dunia nyata. Ada beberapa batasan pada masalah yang sedikit tidak terduga, tetapi diperlukan agar bukti tersebut bekerja; khususnya, masalahnya mensyaratkan bahwa hasil dihitung secara on-line, tanpa dapat mengakses input di masa depan, dan bahwa input terdiri dari urutan atom dari sekumpulan atom yang mungkin tidak terikat, dan bukannya kumpulan ukuran tetap. Dan kertas hanya menetapkan (batas bawah) hasil untuk algoritma waktu berjalan linier yang tidak murni; untuk masalah yang membutuhkan waktu berjalan lebih besar, ada kemungkinan bahwa O ekstra (log n) faktor yang terlihat pada masalah linier mungkin dapat "diserap" dalam proses operasi tambahan yang diperlukan untuk algoritma dengan waktu operasi yang lebih besar. Klarifikasi dan pertanyaan terbuka ini dieksplorasi secara singkat oleh Ben-Amram [1996] .

Dalam praktiknya, banyak algoritma dapat diimplementasikan dalam bahasa fungsional murni dengan efisiensi yang sama seperti dalam bahasa dengan struktur data yang bisa berubah. Untuk referensi yang baik tentang teknik yang digunakan untuk menerapkan struktur data murni fungsional secara efisien, lihat "Struktur Data Murni Fungsional" dari Chris Okasaki [Okasaki 1998] (yang merupakan versi perluasan dari tesisnya [Okasaki 1996] ).

Siapa pun yang perlu menerapkan algoritma pada struktur data yang berfungsi murni harus membaca Okasaki. Anda selalu bisa mendapatkan paling buruk pelambatan O (log n ) per operasi dengan mensimulasikan memori yang bisa berubah dengan pohon biner seimbang, tetapi dalam banyak kasus Anda bisa melakukan jauh lebih baik dari itu, dan Okasaki menjelaskan banyak teknik yang berguna, dari teknik diamortisasi ke real waktu yang melakukan pekerjaan diamortisasi secara bertahap. Struktur data yang murni fungsional bisa agak sulit untuk dikerjakan dan dianalisis, tetapi mereka memberikan banyak manfaat seperti transparansi referensial yang membantu dalam optimasi kompiler, dalam komputasi paralel dan terdistribusi, dan dalam implementasi fitur seperti versi, undo, dan rollback.

Perhatikan juga bahwa semua ini hanya membahas waktu berjalan asimptotik. Banyak teknik untuk menerapkan struktur data yang berfungsi murni memberi Anda sejumlah faktor perlambatan konstan, karena pembukuan tambahan yang diperlukan agar berfungsi, dan detail implementasi bahasa yang bersangkutan. Manfaat dari struktur data yang murni fungsional mungkin lebih penting daripada perlambatan faktor konstan ini, jadi Anda biasanya perlu melakukan trade-off berdasarkan masalah yang dipermasalahkan.

Referensi

Brian Campbell
sumber
50
Pippinger adalah otoritas yang tidak perlu dipersoalkan untuk pertanyaan ini. Tetapi kita harus menekankan bahwa hasilnya adalah teoretis , bukan praktis. Ketika membuat struktur data fungsional praktis dan efisien, Anda tidak dapat melakukan lebih baik daripada Okasaki.
Norman Ramsey
6
itowlson: Saya harus mengakui bahwa saya tidak cukup banyak membaca Pippenger untuk menjawab pertanyaan Anda; itu diterbitkan dalam jurnal peer-review, dikutip oleh Okasaki, dan saya cukup banyak membacanya untuk menentukan bahwa klaimnya relevan dengan pertanyaan ini, tetapi tidak cukup untuk memahami buktinya. Hasil langsung yang saya dapatkan untuk konsekuensi dunia nyata adalah sepele untuk mengubah O ( n ) algoritma tidak murni menjadi O ( n log n ) murni, dengan hanya mensimulasikan memori yang dapat dimodifikasi menggunakan pohon biner seimbang. Ada masalah yang tidak bisa lebih baik dari itu; Saya tidak tahu apakah itu murni teoretis.
Brian Campbell
3
Hasil Pippenger membuat dua asumsi penting yang membatasi ruang lingkupnya: ia menganggap komputasi "on-line" atau "reaktif" (bukan model yang biasa dari input perhitungan pemetaan input terbatas ke output tunggal) dan perhitungan "simbolik" di mana input merupakan urutan dari atom, yang dapat diuji hanya untuk kesetaraan (yaitu, interpretasi input sangat primitif).
Chris Conway
2
Jawaban yang sangat bagus; Saya ingin menambahkan bahwa untuk bahasa yang murni fungsional tidak ada model yang disepakati secara universal untuk kompleksitas komputasi, sementara di dunia yang tidak murni, mesin RAM unit-cost relatif standar (jadi ini membuat membandingkan berbagai hal lebih sulit). Perhatikan juga bahwa batas atas perbedaan Lg (N) dalam murni / tidak murni dapat dengan mudah dijelaskan secara intuitif dengan melihat implementasi array dalam bahasa murni (harganya lg (n) per operasi (dan Anda mendapatkan sejarah)) .
user51568
4
Poin penting: dengan susah payah menerjemahkan spesifikasi yang murni fungsional ke dalam implementasi yang lebih rumit dan efisien murni fungsional tidak banyak manfaatnya jika Anda pada akhirnya - baik secara otomatis atau dengan tangan - menerjemahkannya ke dalam kode yang tidak murni dan lebih efisien. Pengotor bukanlah masalah besar jika Anda bisa menyimpannya di dalam sangkar, misalnya dengan menguncinya dalam fungsi bebas efek samping.
Robin Green
44

Memang ada beberapa algoritma dan struktur data yang tidak ada solusi murni fungsional asimptotik efisien (ti satu diterapkan dalam kalkulus lambda murni) diketahui, bahkan dengan kemalasan.

  • Temuan serikat pekerja yang disebutkan di atas
  • Tabel hash
  • Array
  • Beberapa algoritma grafik
  • ...

Namun, kami berasumsi bahwa dalam bahasa "imperatif" akses ke memori adalah O (1) sedangkan dalam teori yang tidak dapat begitu asimptotik (yaitu untuk ukuran masalah yang tidak terbatas) dan akses ke memori dalam set data besar selalu O (log n) , yang dapat ditiru dalam bahasa fungsional.

Juga, kita harus ingat bahwa sebenarnya semua bahasa fungsional modern menyediakan data yang dapat berubah, dan Haskell bahkan menyediakannya tanpa mengorbankan kemurnian (monad ST).

Jkff
sumber
3
Jika dataset sesuai dengan memori fisik, aksesnya adalah O (1) karena dimungkinkan untuk menemukan batas atas absolut pada jumlah waktu untuk membaca item apa pun. Jika dataset tidak, Anda berbicara tentang I / O dan itu akan menjadi faktor dominan sejauh ini, namun program ini ditulis.
Donal Fellows
Yah, tentu saja saya berbicara tentang O (log n) operasi akses ke memori eksternal. Namun, dalam kasus apa pun saya berbicara bs: memori eksternal juga bisa O (1) -dapat disentuh ...
jkff
2
Saya pikir salah satu hal terbesar yang mendapatkan pemrograman penting dibandingkan dengan pemrograman fungsional adalah kemampuan untuk menyimpan referensi ke banyak aspek berbeda dari satu negara, dan menghasilkan negara baru sehingga semua referensi tersebut menunjuk ke aspek yang sesuai dari negara baru. Menggunakan pemrograman fungsional akan memerlukan operasi dereferencing langsung untuk digantikan oleh operasi pencarian untuk menemukan aspek yang sesuai dari versi tertentu dari keadaan keseluruhan saat ini.
supercat
Bahkan model pointer (O (log n) akses memori, secara longgar) tidak realistis secara fisik pada skala yang sangat besar. Kecepatan cahaya membatasi seberapa cepat berbagai peralatan komputasi dapat berkomunikasi satu sama lain, sementara saat ini diyakini bahwa jumlah maksimum informasi yang dapat disimpan di wilayah tertentu dibatasi oleh luas permukaannya.
dfeuer
36

Artikel ini mengklaim bahwa implementasi yang murni fungsional dari algoritma union-find semuanya memiliki kompleksitas asimptotik yang lebih buruk daripada yang mereka terbitkan, yang memiliki antarmuka murni fungsional tetapi menggunakan data yang dapat diubah secara internal.

Fakta bahwa jawaban lain mengklaim bahwa tidak akan pernah ada perbedaan dan bahwa misalnya, satu-satunya "kelemahan" dari kode fungsional murni adalah dapat diparalelkan memberi Anda gambaran tentang informasi / objektivitas dari komunitas pemrograman fungsional mengenai masalah ini. .

EDIT:

Komentar di bawah menunjukkan bahwa diskusi yang bias tentang pro dan kontra pemrograman fungsional murni mungkin tidak datang dari "komunitas pemrograman fungsional". Poin yang bagus. Mungkin para advokat yang saya lihat hanya, mengutip komentar, "buta huruf".

Sebagai contoh, saya berpikir bahwa posting blog ini ditulis oleh seseorang yang bisa dikatakan mewakili komunitas pemrograman fungsional, dan karena ini adalah daftar "poin untuk evaluasi malas", itu akan menjadi tempat yang baik untuk menyebutkan segala kekurangan yang mungkin pemrograman malas dan murni fungsional. Tempat yang baik akan menggantikan pemecatan berikut (benar secara teknis, tetapi bias sampai tidak lucu):

Jika fungsi yang ketat memiliki kompleksitas O (f (n)) dalam bahasa yang ketat, maka ia memiliki kompleksitas O (f (n)) dalam bahasa yang malas juga. Kenapa khawatir? :)

Pascal Cuoq
sumber
4

Dengan batas atas yang tetap pada penggunaan memori, seharusnya tidak ada perbedaan.

Sketsa bukti: Diberi batasan tetap pada penggunaan memori, seseorang harus dapat menulis mesin virtual yang mengeksekusi set instruksi imperatif dengan kompleksitas asimptotik yang sama seolah-olah Anda benar-benar mengeksekusi pada mesin itu. Ini karena Anda dapat mengelola memori yang dapat berubah sebagai struktur data yang persisten, membuat O (log (n)) membaca dan menulis, tetapi dengan batas atas yang tetap pada penggunaan memori, Anda dapat memiliki jumlah memori yang tetap, menyebabkan ini untuk pembusukan ke O (1). Dengan demikian implementasi fungsional dapat menjadi versi imperatif yang berjalan dalam implementasi fungsional VM, dan karenanya keduanya harus memiliki kompleksitas asimptotik yang sama.

Brian
sumber
6
Batas yang tetap pada penggunaan memori bukanlah cara orang menganalisis hal-hal semacam ini; Anda mengasumsikan memori sewenang-wenang besar, tetapi terbatas. Saat menerapkan suatu algoritma, saya tertarik bagaimana hal itu akan skala dari input yang paling sederhana hingga ukuran input yang sewenang-wenang. Jika Anda menetapkan batas atas tetap pada penggunaan memori, mengapa Anda tidak juga menetapkan batas atas tetap pada berapa lama Anda akan membiarkan perhitungan dilakukan, dan mengatakan bahwa semuanya adalah O (1)?
Brian Campbell
@ Campbell Campbell: Itu benar. Saya hanya menyarankan bahwa jika Anda mau, Anda bisa mengabaikan perbedaan dalam faktor konstan dalam banyak kasus dalam praktiknya. Orang masih perlu memperhatikan perbedaan ketika berkompromi antara memori dan waktu untuk memastikan bahwa menggunakan m kali lebih banyak memori mengurangi runtime Anda dengan setidaknya faktor log (m).
Brian