Memoization

Latince memorandum kelimesinden türeyen memoization, birden çok defa hesaplanması gereken işlemlerin sonucunun hatırlanıp, aynı işlemi tekrar tekrar yapmamıza engel olan ve bu şekilde zamandan kazanmamızı sağlayan optimizasyon tekniğidir. Klasik örnek olacak belki ama fibonacci örneğini ele alalım.

Normalde yazdığımız fibonacci sayısı hesaplayan özyinelemeli fonksiyon

int fibonacci(int n) { if (n == 1 || n == 2) return 1; else return fibonacci(n – 1) + fibonacci(n – 2); }

Yukarıdaki fonksiyonun fibonacci(5) şeklinde çağırılmasından sonra sonucu bulması için gerçekleşecek özyinelemeli çağrılar sonucunda oluşacak ağaç şu şekildedir:

[![](http://www.onurbaysan.com/blog/wp-content/uploads/2011/11/tree.png “tree”)](http://www.onurbaysan.com/blog/wp-content/uploads/2011/11/tree.png)

 

 

Bu şekilde görüldüğü gibi 3 değeri 2 kez çalıştırılacak. Bu fonksiyonun 5 ile değil de daha büyük bir sayı ile çağırıldığı düşünülecek olursa tekrar hesaplanacak değerlerin sayısı artacaktır.

Ama eğer biz her hesaplanan fibonacci sayısının değerini bir veri yapısında tutacak olursak ve aynı işlemi tekrarlamamız gereken durumda direk sonucuna erişim yapabiliriz. Bunu da şu şekilde bir kod ile yapabiliriz.

 

//Memoization işleminde kullanılacak veri yapısı Dictionary fibs = new Dictionary(); int mFibonacci(int n) { if (n == 1 || n == 2) return 1; if (fibs.ContainsKey(n)) return fibs[n]; else { fibs[n] = mFibonacci(n – 1) + mFibonacci(n – 2); return fibs[n]; } }

 

Yukarıdaki verilen 2 farklı koda ait çalışma zamanları bilgileri aşağıda mevcuttur.

[![](http://www.onurbaysan.com/blog/wp-content/uploads/2011/11/output-1024×324.png “output”)](http://www.onurbaysan.com/blog/wp-content/uploads/2011/11/output.png)

Son söz olarak bu yöntem ile zamandan kazanmamıza rağmen sizin de farketmiş olacağınız üzere ek bellek kullandığımız için yerden kaybediyoruz.

305 Words