Memoization

Memoization

Terinspirasi dari salah seorang kolega di kantor yang berhasil meningkatkan performansi satu bagian di server. Saya ingin menulis tentang memoization. Dalam programming, saat satu fungsi yang kita gunakan membutuhkan proses yang mahal dan dipanggil berulang-ulang, kita bisa menyimpan data hasil perhitungan tersebut untuk kemudian digunakan saat fungsi tersebut dipanggil kembali. Dengan teknik ini, kita bisa menghemat “biaya” operasi fungsi (degnan kata lain performansi program kita meningkat) dengan “ganti rugi” space memory (untuk menyimpan hasil operasi fungsi tersebut). Teknik seperti ini disebut memoization.

Lebih jelasnya, mari kita lihat contoh berikut:

public class Lingkaran{
	private static final int PI = 3.14f;
	private float luas = -1;
	private int radius;

	public void setRadius(float r){
		luas = -1;
		radius = r;
	}
	public float Luas(){
		if (luas < 0){  // kita korbanin biaya buat branching, karena operasi di dalam sini bakal banyak makan resources
			luas = PI*radius*radius; // ini hanya contoh saja
		}
		return luas;
	}
}

tentu saja contoh di atas hanyalah contoh yang sangat sederhana sekali :)

Lookup Table
Salah satu teknik memoization adalah dengan menggunakan lookup table. Saat SMA tentu kita pernah melihat buku table logaritma, yang bisa kita gunakan untuk membantu menghitung nilai logaritma bilangan tertentu dengan cara melihat table logaritma tersebut yang sudah mencatat berbagai perhitungan logaritma bilangan tertentu. Dalam programming, kita juga dapat memanfaatkan table lookup, yang menyimpan data.

misalnya fungsi javascript sederhana ini:

function isPrime(value){
	if (!isPrime.answers) isPrime.answers = {};
	if (isPrime.answers[value] != null){
		return isPrime.answers[value];
	}

	var prime = value != 1;
	for (var i = 2; i < value; i++){
		if (value % i == 0){
			prime = false;
			break;
		}
	}

	return isPrime.answers[value] = prime;
}

tentu saja fungsi pengujian bilangan prima di atas sangat tidak efisien (cek cara lebih efisien di wiki, misalnya dengan metode Sieve of Eratosthenes), tapi bisa kita lihat di contoh kode di atas, setiap kali kita menguji satu bilangan, kita mencatat status bilangan tersebut apakah prima atau tidak dalam satu object. Dan ketika kita menguji kembali bilangan yang sama, kita tidak perlu melakukan pengujian ulang, tapi langsung mengembalikan status yang ada dalam “memo”.

lebih jauh tentang memoization bisa diawali dengan membaca wikipedia berikut: https://en.wikipedia.org/wiki/Memoization

happy coding :)

2 thoughts on “Memoization

  1. Mas, boleh nanya mengenai ini?
    Ada kalanya dalam konteks yang serupa, hasil operasinya adalah sebuah objek.
    Kemudian kalau kita menyimpan objek ini ke dalam memo, misalnya dalam bentuk Hashtable, apakah implementasi ini ideal?

    Contohnya jika kita me memo kan objek Listener atau Observer misalnya.

    Mohon tanggapannya mas.

    • menurutku itu bisa mas; tapi kalau object-nya membawa data banyak banget harus hati-hati dengan memory leaks;
      kalau observer sama listener saya kurang yakin perlu di memoize; karena biasanya dia task-nya handler observable object yang state-nya berubah.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s