(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?
the calculation catches up
? BTW, memoisasi tidak khusus untuk haskell: en.wikipedia.org/wiki/MemoizationJawaban:
Hanya untuk menjelaskan mekanisme di balik memoisasi yang sebenarnya,
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 10000
dua 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:
Jadi, Anda dapat melihat bagaimana mengevaluasi
THUNK_4
jauh lebih cepat karena subekspresi sudah dievaluasi.sumber
memo_fib
dengan 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)memo_fib 29
danmemo_fib 30
sudah dievaluasi, itu akan memakan waktu persis seperti yang diperlukan untuk menambahkan dua angka itu :) Setelah sesuatu dieval-red, ia tetap bertahan.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 x
akan selalu tersedia ketikafib x+1
dieksekusi, 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 dengan0
, sedangkan rekursi dalam contoh pertama dimulai dengann
dan hanya kemudian bertanya tentangn-1
. Inilah yang menyebabkan banyak, banyak panggilan fungsi duplikat yang tidak perlu.sumber
memorized_fib 20
misalnya, Anda sebenarnya hanya menulismap fib [0..] !! 20
, itu masih perlu menghitung seluruh rentang angka hingga 20, atau apakah saya melewatkan sesuatu di sini?fib 2
begitu sering itu akan membuat kepala Anda berputar - maju, tulis bulu pohon panggilan hanya nilai kecil sepertin==5
. Anda tidak akan pernah melupakan memoisasi lagi setelah Anda melihat apa yang menyelamatkan Anda.n = 5
, dan saya saat ini telah mencapai titik di manan == 3
, sejauh ini sangat baik, tapi mungkin itu hanya pikiran imperatif saya yang memikirkan ini, tetapi bukankah itu hanya berarti bahwa untukn == 3
, Anda hanya mendapatkanmap fib [0..]!!3
? yang kemudian masuk kefib n
cabang program ... di mana tepatnya saya mendapatkan manfaat dari data yang telah dihitung sebelumnya?memoized_fib
tidak apa-apa. Ituslow_fib
yang akan membuat Anda menangis jika Anda melacaknya.