Adakah yang bisa menjelaskan konsep di balik memoisasi Haskell?

12

(perhatikan saya mengajukan pertanyaan di sini karena ini tentang mekanisme konseptualnya, daripada masalah pengkodean)

Saya sedang mengerjakan sebuah program kecil, yang menggunakan urutan angka-angka fibonacci dalam persamaannya, tetapi saya perhatikan bahwa jika saya mendapatkan lebih dari jumlah tertentu ia menjadi sangat lambat, mencari-cari sedikit, saya menemukan sebuah teknik di Haskell yang dikenal sebagai Memoization, mereka menunjukkan kode berfungsi seperti ini:

-- Traditional implementation of fibonacci, hangs after about 30
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)

-- Memorized variant is near instant even after 10000
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

Jadi pertanyaan saya kepada kalian adalah, bagaimana atau lebih tepatnya mengapa ini bekerja?

Apakah karena entah bagaimana berhasil melewati sebagian besar daftar sebelum perhitungannya tercapai? Tetapi jika haskell malas, sebenarnya tidak ada perhitungan yang perlu mengejar ... Jadi bagaimana cara kerjanya?

Kopi Listrik
sumber
1
bisakah Anda menjelaskan apa yang Anda maksud the calculation catches up? BTW, memoisasi tidak khusus untuk haskell: en.wikipedia.org/wiki/Memoization
Simon Bergot
lihat penjelasan saya di bawah jawaban killan
Electric Coffee
2
Cintai pertanyaan Anda; hanya sebuah catatan singkat: Teknik ini disebut memo saya lisasi, tidak memo ri lisasi.
Racheet

Jawaban:

11

Hanya untuk menjelaskan mekanisme di balik memoisasi yang sebenarnya,

memo_fib = (map fib [1..] !!)

menghasilkan daftar "thunks", perhitungan yang tidak dievaluasi. Pikirkan ini seperti hadiah yang belum dibuka, selama kita tidak menyentuh mereka, mereka tidak akan lari.

Sekarang setelah kami mengevaluasi seorang pencuri, kami tidak pernah mengevaluasinya lagi. Ini sebenarnya satu-satunya bentuk mutasi dalam haskell "normal", thunks bermutasi setelah dievaluasi menjadi nilai konkret.

Jadi kembali ke kode Anda, Anda punya daftar thunks, dan Anda masih melakukan rekursi pohon ini, tetapi Anda berulang menggunakan daftar, dan sekali elemen dalam daftar dievaluasi, itu tidak akan pernah dihitung lagi. Dengan demikian, kita menghindari rekursi pohon dalam fungsi fib naif.

Sebagai catatan yang menarik secara tangensial, ini terutama cepat pada serangkaian bilangan fibonnaci yang dihitung karena daftar itu hanya dievaluasi satu kali, yang berarti bahwa jika Anda menghitung memo_fib 10000dua kali, yang kedua harus instan. Ini karena Haskell hanya mengevaluasi argumen untuk fungsi sekali dan Anda menggunakan aplikasi parsial bukan lambda.

TLDR: Dengan menyimpan perhitungan dalam daftar, setiap elemen daftar dievaluasi satu kali, oleh karena itu, setiap nomor fibonnacci dihitung tepat sekali di seluruh program.

Visualisasi:

 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_5]
 -- Evaluating THUNK_5
 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_3 + THUNK_4]
 [THUNK_1, THUNK_2, THUNK_1 + THUNK_2, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 1 + 1, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 2, THUNK_4, 2 + THUNK4]
 [1, 1, 2, 1 + 2, 2 + THUNK_4]
 [1, 1, 2, 3, 2 + 3]
 [1, 1, 2, 3, 5]

Jadi, Anda dapat melihat bagaimana mengevaluasi THUNK_4jauh lebih cepat karena subekspresi sudah dievaluasi.

Daniel Gratzer
sumber
dapatkah Anda memberikan contoh bagaimana nilai-nilai dalam daftar berperilaku untuk urutan pendek? Saya pikir itu dapat menambah visualisasi bagaimana seharusnya bekerja ... Dan sementara itu benar bahwa jika saya memanggil memo_fibdengan nilai yang sama dua kali, kedua kalinya akan instan, tetapi jika saya menyebutnya dengan nilai 1 lebih tinggi, itu masih membutuhkan waktu lama untuk mengevaluasi (seperti mengatakan mulai dari 30 hingga 31)
Electric Coffee
@ElectricCoffee Added
Daniel Gratzer
@ElectricCoffee Tidak, itu tidak akan terjadi sejak itu memo_fib 29dan memo_fib 30sudah dievaluasi, itu akan memakan waktu persis seperti yang diperlukan untuk menambahkan dua angka itu :) Setelah sesuatu dieval-red, ia tetap bertahan.
Daniel Gratzer
1
@ElectricCoffee Rekursi Anda harus melalui daftar, jika tidak, Anda tidak mendapatkan kinerja apa pun
Daniel Gratzer
2
@ElectricCoffee Ya. tetapi elemen ke-31 dari daftar ini tidak menggunakan perhitungan sebelumnya, Anda memaafkan ya, tetapi dengan cara yang sangat tidak berguna .. Perhitungan yang diulang tidak dihitung dua kali, tetapi Anda masih memiliki rekursi pohon untuk setiap nilai baru yang sangat, sangat lambat
Daniel Gratzer
1

Titik memoisasi tidak pernah menghitung fungsi yang sama dua kali - ini sangat berguna untuk mempercepat perhitungan yang murni fungsional, yaitu tanpa efek samping, karena bagi mereka proses tersebut dapat sepenuhnya otomatis tanpa mempengaruhi kebenaran. Ini terutama diperlukan untuk fungsi seperti fibo, yang mengarah pada rekursi pohon , yaitu upaya eksponensial, ketika diterapkan secara naif. (Ini adalah salah satu alasan mengapa angka-angka Fibonacci sebenarnya adalah contoh yang sangat buruk untuk pengajaran rekursi - hampir semua implementasi demo yang Anda temukan dalam tutorial atau buku tidak dapat digunakan untuk nilai input besar.)

Jika Anda melacak aliran eksekusi, Anda akan melihat bahwa dalam kasus kedua, nilai untuk fib xakan selalu tersedia ketika fib x+1dieksekusi, dan sistem runtime akan dapat dengan mudah membacanya dari memori daripada melalui panggilan rekursif lain, sedangkan solusi pertama mencoba untuk menghitung solusi yang lebih besar sebelum hasil untuk nilai yang lebih kecil tersedia. Ini pada akhirnya karena iterator [0..n]dievaluasi dari kiri ke kanan dan karena itu akan mulai dengan 0, sedangkan rekursi dalam contoh pertama dimulai dengan ndan hanya kemudian bertanya tentang n-1. Inilah yang menyebabkan banyak, banyak panggilan fungsi duplikat yang tidak perlu.

Kilian Foth
sumber
oh saya mengerti intinya, saya hanya tidak mengerti cara kerjanya, seperti dari apa yang bisa saya lihat dalam kode, adalah bahwa ketika Anda menulis memorized_fib 20misalnya, Anda sebenarnya hanya menulis map fib [0..] !! 20, itu masih perlu menghitung seluruh rentang angka hingga 20, atau apakah saya melewatkan sesuatu di sini?
Kopi Listrik
1
Ya, tetapi hanya sekali untuk setiap nomor. Implementasi naif menghitung fib 2begitu sering itu akan membuat kepala Anda berputar - maju, tulis bulu pohon panggilan hanya nilai kecil seperti n==5. Anda tidak akan pernah melupakan memoisasi lagi setelah Anda melihat apa yang menyelamatkan Anda.
Kilian Foth
@ElectricCoffee: Ya, itu akan menghitung fib 1 hingga 20. Anda tidak mendapatkan apa pun dari panggilan itu. Sekarang coba hitung fib 21, dan Anda akan melihat bahwa alih-alih menghitung 1-21, Anda bisa menghitung 21 karena Anda sudah menghitung 1-20 dan tidak perlu melakukannya lagi.
Phoshi
Saya mencoba untuk menulis pohon panggilan untuk n = 5, dan saya saat ini telah mencapai titik di mana n == 3, sejauh ini sangat baik, tapi mungkin itu hanya pikiran imperatif saya yang memikirkan ini, tetapi bukankah itu hanya berarti bahwa untuk n == 3, Anda hanya mendapatkan map fib [0..]!!3? yang kemudian masuk ke fib ncabang program ... di mana tepatnya saya mendapatkan manfaat dari data yang telah dihitung sebelumnya?
Kopi Listrik
1
Tidak, memoized_fibtidak apa-apa. Itu slow_fibyang akan membuat Anda menangis jika Anda melacaknya.
Kilian Foth