Memoisasi
Pelajaran 4 dari 15 dalam kursus Dasar-Dasar Pemrograman Dinamis di Coddy.
Memoization adalah teknik optimasi yang digunakan dalam pemrograman dinamis untuk mempercepat program dengan menyimpan hasil pemanggilan fungsi yang membutuhkan banyak sumber daya, lalu mengembalikan hasil yang tersimpan ketika input yang sama muncul lagi.
Untuk menerapkan memoization, kamu bisa membuat dictionary untuk menyimpan hasil yang sudah dihitung, dengan kunci berupa argumen input dan nilai berupa hasil output yang sesuai. Sebelum menghitung hasil fungsi, kamu bisa terlebih dahulu memeriksa apakah input tersebut sudah dihitung dan disimpan dalam dictionary. Jika ya, kamu bisa mengembalikan hasil yang tersimpan alih-alih menghitungnya lagi. Jika tidak, kamu menghitung hasilnya dan menyimpannya dalam dictionary.
listjuga bisa digunakan untuk menerapkan memoization.
Memoization dapat mempercepat algoritma pemrograman dinamis secara signifikan, terutama ketika ada banyak submasalah yang saling tumpang tindih.
Tantangan
MudahTulis fungsi Python bernama fib yang menghitung bilangan Fibonacci ke-n menggunakan memoization.
- Gunakan dictionary
memountuk menyimpan bilangan Fibonacci yang sudah dihitung. - Sebelum menghitung bilangan Fibonacci ke-n, periksa apakah bilangan tersebut sudah dihitung dan disimpan di
memo. - Jika sudah, kembalikan hasil yang tersimpan dalam cache. Jika belum, hitung bilangan Fibonacci ke-n menggunakan relasi rekurensi
fib(n) = fib(n-1) + fib(n-2), lalu simpan hasilnya di dictionary untuk digunakan nanti.
Petunjuk: periksa solusi di akhir untuk memastikan kamu menggunakan memoization dengan benar!
Coba sendiri
memo = {0: 0, 1: 1}
def fib(n):
Semua pelajaran di Dasar-Dasar Pemrograman Dinamis
3Algoritma pemrograman dinamis
Subsekuens bersama terpanjangMasalah knapsackMasalah penukaran koinJarak editLatihan sendiri: Compiler Python online