Pemrograman dinamis (dynamic programming, sering disingkat DP) adalah teknik menyimpan jawaban submasalah agar tidak pernah dihitung dua kali. Teknik ini lahir dari satu pengamatan sederhana, yaitu rekursi yang tampak elegan bisa menghitung hal yang sama berjuta kali. Topik ini mengukur ledakan itu dengan penghitung pemanggilan, lalu menutupnya dengan dua cara, yaitu memoisasi top-down dan tabel bottom-up, semuanya pada deret Fibonacci yang mudah diperiksa ulang.
Submasalah tumpang-tindih#
Deret Fibonacci didefinisikan dengan dua nilai awal dan hubungan berulangnya:
Rumus itu diterjemahkan ke kode rekursif tanpa pikir panjang, dan justru di situlah masalahnya. fib(4) memanggil fib(3) dan fib(2), sedangkan fib(3) sendiri memanggil fib(2) lagi. Submasalah yang sama, seperti fib(2), muncul di beberapa cabang pohon panggilan. Keadaan ini disebut submasalah tumpang-tindih (overlapping subproblems), dan jumlahnya tumbuh cepat.
Pohon panggilan fib(4) hanya berisi sembilan panggilan, tetapi polanya sudah terlihat, yaitu f(2) dihitung dua kali, f(1) tiga kali, dan f(0) dua kali. Setiap kenaikan n melipatgandakan pengulangan itu, dan pengukuran pada bagian berikutnya menunjukkan fib(20) menumpuk 21891 panggilan untuk pekerjaan yang sebenarnya hanya 21 submasalah berbeda. Syarat pertama DP, yaitu submasalah tumpang-tindih, jelas terpenuhi di sini. Syarat keduanya ikut terpenuhi, yaitu jawaban soal utuh tersusun dari jawaban submasalah yang lebih kecil tanpa saling memengaruhi.
Mengukur ledakan dengan penghitung#
Keluaran program lebih meyakinkan daripada perkiraan, karena itu tiga versi Fibonacci berikut dibandingkan lewat penghitung yang setara, yaitu jumlah pemanggilan fungsi untuk versi rekursif dan jumlah langkah perulangan untuk versi tabel.
"""Fibonacci tiga cara: rekursi naif, memoisasi top-down, dan tabel bottom-up."""
panggil_naif = 0
def fib_naif(n):
# submasalah yang sama dihitung berulang sehingga panggilan meledak
global panggil_naif
panggil_naif += 1
if n <= 1:
return n
return fib_naif(n - 1) + fib_naif(n - 2)
memo = {}
panggil_memo = 0
def fib_memo(n):
global panggil_memo
panggil_memo += 1
if n <= 1:
return n
if n in memo:
return memo[n] # jawaban lama langsung dipakai lagi
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
def fib_bawah(n):
langkah = 0
a, b = 0, 1
for _ in range(n):
a, b = b, a + b # geser jendela dua nilai, tabel hanya itu
langkah += 1
return a, langkah
print("fib_naif(20) =", fib_naif(20), "| panggilan:", panggil_naif)
print("fib_memo(20) =", fib_memo(20), "| panggilan:", panggil_memo)
hasil, langkah = fib_bawah(20)
print("fib_bawah(20) =", hasil, "| langkah :", langkah)fib_naif(20) = 6765 | panggilan: 21891
fib_memo(20) = 6765 | panggilan: 39
fib_bawah(20) = 6765 | langkah : 20Angkanya jelas, yaitu 21891 panggilan untuk versi naif melawan 39 untuk versi memo dan 20 langkah untuk versi tabel. Penghitungnya ditambah satu pada baris pertama setiap fungsi, sedangkan penghitung versi tabel ditambah satu di dalam perulangan sehingga satu langkah berarti satu pengisian jendela. Struktur ketiganya sengaja ditaruh berdampingan dalam satu berkas, sehingga angkanya pasti sama setiap program dijalankan ulang dan perbandingan antar versi menjadi adil. Rasio pertumbuhan versi naif juga konsisten, karena setiap kenaikan n sebesar satu memperbanyak panggilan sekitar 1,6 kali, sama dengan rasio dua suku Fibonacci berurutan. Versi memo berakhir di sekitar 2n panggilan karena setiap submasalah dihitung sekali, lalu paling banyak dibaca ulang satu kali dari memo.
Memoisasi top-down#
Memoisasi top-down mempertahankan bentuk rekursifnya, lalu menyimpan jawaban setiap submasalah pada memo sebelum fungsi kembali. Pemeriksaan memo dilakukan paling awal, sehingga panggilan berulang langsung selesai tanpa turun ke pohon lagi. Memo untuk Fibonacci cukup berupa kamus dengan kunci n dan nilai hasilnya, dan kuncinya pasti unik karena hanya ada satu argumen. Python menyediakan alat siap pakai untuk pola ini, yaitu dekorator functools.lru_cache yang membungkus fungsi apa pun dengan memo berupa kamus tanpa mengubah satu baris pun dari badan fungsinya. Jumlah panggilannya sedikit lebih banyak daripada jumlah submasalah karena setiap hit tetap masuk fungsi sebelum menemukan jawabannya.
"""Memoisasi siap pakai dengan functools.lru_cache pada Fibonacci."""
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print([fib(n) for n in range(10)])
print("fib(50) =", fib(50))
print("info cache:", fib.cache_info())[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fib(50) = 12586269025
info cache: CacheInfo(hits=58, misses=51, maxsize=None, currsize=51)Baris cache_info() mencatat semuanya secara tepat, yaitu 51 misses untuk nilai 0 sampai 50 yang masing-masing dihitung sekali, dan 58 hits untuk panggilan berulang yang dijawab langsung dari memo. Nilai maxsize=None berarti cache tidak dibatasi jumlahnya, sesuai untuk soal dengan jumlah submasalah yang jelas seperti Fibonacci.
Tabel bottom-up#
Pendekatan bottom-up membalik arahnya, yaitu mulai dari basis lalu mengisi tabel sampai ukuran soal yang diminta, tanpa rekursi sama sekali. Urutan pengisian dari kecil ke besar menjamin setiap sel yang dirujuk transisi sudah terisi lebih dulu. Untuk Fibonacci, tabelnya bahkan menyusut menjadi dua variabel yang digeser setiap langkah, karena transisi hanya menatap dua nilai terakhir. Biayanya 20 langkah untuk fib(20), sebagaimana tercatat pada penghitung sebelumnya.
Pilihan antara keduanya bergantung pada situasi. Top-down ditulis hampir persis seperti definisi rekursifnya sehingga jarang salah, tetapi tetap memakai call stack dan bisa menabrak batas kedalaman rekursi pada masukan besar. Bottom-up menghindari stack sepenuhnya dan memungkinkan pemangkasan memori seperti jendela dua nilai tadi, tetapi urutan pengisiannya harus dirancang lebih dahulu.
Varian Java#
Java tidak punya dekorator bawaan seperti lru_cache, tetapi pola memoisasinya sama dengan satu array. Versi berikut mengulang ketiga cara beserta penghitungnya:
public class FibTigaCara {
// Fibonacci tiga cara: naif, memoisasi, dan bottom-up dengan penghitung
static long panggilNaif = 0;
static long panggilMemo = 0;
static long[] memo = new long[21];
static long fibNaif(int n) {
panggilNaif++;
if (n <= 1) {
return n;
}
return fibNaif(n - 1) + fibNaif(n - 2);
}
static long fibMemo(int n) {
panggilMemo++;
if (n <= 1) {
return n;
}
if (memo[n] != 0) {
return memo[n]; // jawaban lama langsung dipakai lagi
}
memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
return memo[n];
}
static long fibBawah(int n, long[] langkah) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) {
long t = a + b;
a = b;
b = t;
langkah[0]++;
}
return a;
}
public static void main(String[] args) {
System.out.println("fibNaif(20) = " + fibNaif(20) + " | panggilan: " + panggilNaif);
System.out.println("fibMemo(20) = " + fibMemo(20) + " | panggilan: " + panggilMemo);
long[] langkah = {0};
System.out.println("fibBawah(20) = " + fibBawah(20, langkah) + " | langkah : " + langkah[0]);
}
}fibNaif(20) = 6765 | panggilan: 21891
fibMemo(20) = 6765 | panggilan: 39
fibBawah(20) = 6765 | langkah : 20Keluarannya sama persis dengan versi Python, termasuk angka 21891 dan 39. Penghitungnya berupa variabel static sehingga seluruh pemanggilan melihat angka yang sama, dan tipe long dipilih agar penghitung tidak meluap pada masukan yang lebih besar. Parameter langkah dikemas dalam array satu sel karena Java mengoper array dengan rujukan, sehingga penambahan di dalam fungsi tetap terbaca di main. Pemeriksaan memo[n] != 0 memanfaatkan nilai awal array Java yang nol, dan trik ini sah karena sel n minimal 2 selalu berisi Fibonacci positif, sedangkan kasus 0 dan 1 sudah ditangani basis sebelum pemeriksaan memo tercapai. Bila n dinaikkan jauh, tipe long mulai meluap pada suku ke-93, dan saat itu tabelnya diganti menjadi java.math.BigInteger tanpa mengubah struktur perulangannya.
Kesalahan umum#
- Menyimpan memo tetapi memeriksanya setelah rekursi. Pohon panggilan tetap tumbuh penuh karena pemeriksaan terlambat, dan penghitung pemanggilan membuktikannya langsung. Pemeriksaan memo harus jadi hal pertama yang dilakukan setelah basis.
- Memakai rekursi naif untuk masukan besar. Waktu tumbuh eksponensial dan Python mengakhiri program dengan
RecursionErrorsebelum jawabannya keluar. Perbaikannya memoisasi atau bottom-up, bukan menaikkan batas rekursi. - Memakai 0 sebagai penanda sel yang belum dihitung pada soal yang jawabannya memang bisa 0. Sel berjawaban 0 tidak bisa dibedakan dari sel yang belum dihitung, sehingga pemeriksaan memo membacanya keliru dan perhitungan jadi salah. Gunakan nilai sentinel seperti -1 atau tabel boolean terpisah.
- Mengira memoisasi mengubah jawaban. Hasilnya identik dengan versi naif, yang berubah hanya biaya waktunya.
- Mengukur kinerja dengan stopwatch. Angka detik berubah-ubah mengikuti beban mesin, sedangkan penghitung panggilan dan langkah pasti sama setiap dijalankan. Bandingkan versi algoritma dengan penghitung, dan gunakan waktu eksekusi hanya untuk mengonfirmasi kelas pertumbuhannya pada masukan yang besar.
Ringkasan#
- Submasalah tumpang-tindih membuat rekursi naif meledak, terukur 21891 panggilan untuk
fib(20)melawan hanya 21 submasalah berbeda. - Memoisasi top-down menyimpan jawaban sebelum fungsi kembali dan memeriksanya paling awal, menurunkan hitungan menjadi 39 panggilan.
functools.lru_cachememberi memo siap pakai, dengancache_info()sebagai penghitung hits dan misses yang pasti.- Bottom-up mengisi tabel dari basis tanpa rekursi, 20 langkah untuk
fib(20), dan memangkas memori hingga dua variabel bila transisinya pendek.
Referensi#
- functools — Higher-order functions and operations on callable objects — Python Software Foundation
— dokumentasi
lru_cachebesertacache_info()yang dipakai pada contoh. - Dynamic programming — Wikipedia — definisi DP, sifat submasalah tumpang-tindih, dan hubungan memoisasi dengan tabulasi.