Common Lisp ve Bir Optimizasyon Tekniği: "Memoization"

[Muallim-i Ali]

Giriş

"Memoization" tabiri bilgisayar bilimlerinde ilk kez Donald Michie'nin 1968 yılında Nature dergisinde yayımlanan Memo functions and machine learning (Memo fonksiyonları ve makina öğrenimi) makalesi ile gündeme gelmiştir.

Memoization tekniği bir fonksiyonu hesaplarken önceden hesaplanmış değerleri hesaplamadan kullanmak, dolayısı ile işlemi hızlandırmak olarak tarif edilebilir. Sözcük olarak "memorization"ı yani "ezberleme" eylemini çağrıştırmakla birlikte daha genel bir anlamı kapsamaktadır.

Programlama dilinden bağımsız olmakla birlikte, bu yazıda "memoization" tekniğinin Common Lisp'te nasıl kullanılacağına bakacağız. Bunun için Peter Norvig'in PAIP kitabı ana eksenimizi oluşturacak.

Common Lisp ile Basit "Memoization" Örneği

(defun fib (n)

"Fibonacci dizisindeki n. sayiyi hesaplar."

(if (<= n 2) 1

(+ (fib (- n 1)) (fib (- n 2)))))

Özyineli bu fonksiyonla ile ilgili temel sıkıntımız aynı hesaplamaları tekrar tekra yapıyor oluşu. Hemen bir örnek vermek gerekirse, yukarıdaki fonksiyonu Emacs+SLIME geliştirme ortamımızda yazdıktan sonra trace ile neyi nasıl yaptığını bir izleyelim:

CL-USER> (fib 5)

5

CL-USER> (trace fib)

(FIB)

CL-USER> (fib 5)

0: (FIB 5)

1: (FIB 4)

2: (FIB 3)

3: (FIB 2)

3: FIB returned 1

3: (FIB 1)

3: FIB returned 1

2: FIB returned 2

2: (FIB 2)

2: FIB returned 1

1: FIB returned 3

1: (FIB 3)

2: (FIB 2)

2: FIB returned 1

2: (FIB 1)

2: FIB returned 1

1: FIB returned 2

0: FIB returned 5

5

Yukarıdaki gibi bir durumla karşılaşmamızın sebebi (fib 5)'in hesaplanması için (fib 4) ve (fib 3)'ün hesaplanması ve (fib 4) için ise yine (fib 3) ve... sanırım problemin ne olduğu artık aşikardır.

Bu durumu iyileştirebilir miyiz? İlk akla gelen şey fonksiyona müdahale edip bunu biraz daha hızlandırmaktır ama bunun yerine fonksiyona hiç dokunmasak da onun yerine otomatik olarak herhangi bir fonksiyonu "memoized" hale getirebilecek bir yapı kursak nasıl olur? Common Lisp programcıları dinamik bir programlama dili ve yüksek dereceden fonksiyonlarla çalıştıkları için genellikle ikinci yolu tercih ederler, bu onlara daha "doğal" görünür.

Şöyle düşünelim, "memo" diye bir fonksiyonumuz olsa ve girdi olarak bir fonksiyon alsa ve çıktı olarak da aynı şeyi hesaplayan ama aynı şeyleri sürekli hesaplama derdinden kurtulmuş bir fonksiyon döndürse nasıl olur?

(defun memo (fn)

"fn fonksiyonunun memo-fonksiyonunu döndür."

(let ((table (make-hash-table)))

#'(lambda (x)

(multiple-value-bind (val found-p)

(gethash x table)

(if found-p

val

(setf (gethash x table) (funcall fn x)))))))

Yukarıdaki fonksiyonu özet olarak açıklamak gerekirse, önce bir "hash" tablosu oluşturuyor "table" isimli bir yerel değişken de bunu tutuyor, ardından da fonksiyonun asıl kısmı geliyor, lambda kullanılarak bir fonksiyon oluşturma kısmı. Öyle bir fonksiyon ki tek bir parametre alıyor, x parametresi ve sonra da yaptığı şey, (gethash x table) fonksiyonu ile söz konusu x'in yukarıda tanımlanmış olan "hash" tablosunda mevcut olup olmadığına bakmak.

Burada multiple-value-bind kullanılmasının sebebi gethash fonksiyonunu iki değer döndürmesi (evet, Lispçiler bir fonksiyon aynı anda birden fazla değer döndürünce şaşırmazlar ;-), yani x tabloda mevcut ve değeri nil olabilir, yahut x tabloda bulunmuyor olabilir, bu yüzden yine nil dönmüş olabilir. Bu ikisini birbirinden ayırt edebilmek için gethash bir de bunu belirten bir değer döndürmektedir ve biz de bunu found-p ile yakalamaktayız.

Bu açıklamadan sonra devam edelim: basit bir if yapısı ile, eğer x tabloda bulunmuş ise bulunan değeri, bulunmadı ise de hesaplanmış değeri döndüren bir fonksiyon döndürüyor ve lambda ifademizi tamamlamış oluyoruz. Hesaplanmış değeri döndürüyoruz derken, bu kısma dikkat çünkü aynı anda bunu (setf ...) ile table isimli "hash" tablosunun x ile ilişkilendirilmiş kısmına yazıyoruz, böylece bir sonraki hesapta bu aşamada hesaplamak zorunda kaldığımız x ile ilgili değeri doğrudan tablodan çekebilir hale gelmiş oluyoruz.

Bir soru (9 puan): En başta, table isimli hash tablosu değişkeninin (let ...) ile tanımlanan yerel bir değişken olduğunu belirtmiştik, o halde nasıl oluyorda bu yerel değişken (yani global olmayan), bu yerel "hash" tablosu tekrar tekrar çağrıldığında önceki değerleri koruyabiliyor? (ipucu: bkz. "closure".)

Artık elimizde kendisine bir fonksiyon geçirebileceğimiz ve karşılığında da "memo edilmiş" (memolanmış?) bir fonksiyon alabileceğimiz memo fonksiyonumuz hazır. Hemen küçük bir deneme yapalım:

CL-USER> (setf memo-fib (memo #'fib))

#<CLOSURE (LAMBDA (X)) {9DA0125}>

(Bazı uyarı mesajları ile karşılaşabilirsiniz ama bunlar şimdilik önemli değil, görmezden gelebilirsiniz. Ayrıca #' notasyonunun açıklamasını da hatırlamakta fayda var!)

Şimdi de (memo #'fib) ile üretip sonra da setf ile memo-fib'e yerleştirdiğimiz bu fonksiyonu bir çağırıp ne yaptığını izleyelim:

CL-USER> (funcall memo-fib 3)

0: (FIB 3)

1: (FIB 2)

1: FIB returned 1

1: (FIB 1)

1: FIB returned 1

0: FIB returned 2

2

CL-USER> (funcall memo-fib 3)

2

CL-USER> (funcall memo-fib 3)

2

Görüldüğü gibi memo-fib fonksiyonu bir kez 3 parametresi ile çağrıldıktan sonra, 2., 3., ... n. çağrılışında artık hesap yapmak yerine doğrudan "öğrenmiş" olduğu yani "memoized" değeri döndürerek optimizasyon sağlamış oluyor.İşimiz bitti mi? Hayır. Maalesef henüz ideal duruma varmış değiliz; dikkat edilecek olursa yukarıdaki "trace"te, (fib 3) için (fib 2) iki kere hesaplanıyor? Bunun sebebi nedir? Sebep şu: Özyineli olarak çağrılan fib fonksiyonunun kendisine herhangi bir müdahalede bulunmadık, dolayısı ile onun içindeki özyineleme, kendi kendini çağırması durumu "memoization"dan faydalanmıyor. Başka bir deyişle "memoized" olan fonksiyon fib değil memo-fib isimli yeni yaratılmış fonksiyon. Öyle bir fonksiyonumuz olsa ki, aldığı fonksiyonu değiştirip doğrudan onu memo fonksiyon hale getirse nasıl olur?

(defun memoize (fn-name)

"fn-name'in global tanimini 'memoized' versiyonla degistir."

(setf (symbol-function fn-name) (memo (symbol-function fn-name))))

Common Lisp'in yüksek dereceden fonksiyon kullanımı konusunda bir adım daha ileri gittik, yukarıdaki memoize fonksiyonu aldığı herhangi bir fonksiyonunun kendisini değiştiriyor, işin püf noktası ise tahmin edebileceğiniz gibi symbol-function.

Şimdi bu fib'in iki halini kıyaslamak için küçük bir deneme yapalım:

CL-USER> (fib 5)

0: (FIB 5)

1: (FIB 4)

2: (FIB 3)

3: (FIB 2)

3: FIB returned 1

3: (FIB 1)

3: FIB returned 1

2: FIB returned 2

2: (FIB 2)

2: FIB returned 1

1: FIB returned 3

1: (FIB 3)

2: (FIB 2)

2: FIB returned 1

2: (FIB 1)

2: FIB returned 1

1: FIB returned 2

0: FIB returned 5

5

Hemen ardından fib fonksiyonunu "memoized" hale getirelim:

CL-USER> (memoize 'fib)

#<CLOSURE (LAMBDA (X)) {9059C5D}>

CL-USER> (fib 5)

0: (FIB 5)

1: (FIB 4)

2: (FIB 3)

3: (FIB 2)

3: FIB returned 1

3: (FIB 1)

3: FIB returned 1

2: FIB returned 2

1: FIB returned 3

0: FIB returned 5

5

CL-USER> (fib 5)

5

CL-USER> (fib 6)

0: (FIB 6)

0: FIB returned 8

8

CL-USER> (fib 9)

0: (FIB 9)

1: (FIB

2: (FIB 7)

2: FIB returned 13

1: FIB returned 21

0: FIB returned 34

34

CL-USER> (fib 7)

13

Görüldüğü gibi, artık gereksiz herhangi bir hesaplama yapılması söz konusu değil!

Artık elimizde epey işlevsel bir memoize fonksiyonu var ancak eğer, söz gelimi fib fonksiyonunun kendisinde bir değişiklik yaparsak bunu tekrar "memoized" hale getirmemiz için etkileşimli Lisp ortamında yine (memoize 'fib) yazmamız gerekiyor. Bunun yerine daha fonksiyonu en baştan yazarken memoize içine yazabileceğimiz ve böylece her derlenişinde otomatik olarak "memoized" hale getirilmesini sağlayabileceğimiz gibi:

(memoize

(defun f (x) ...)

)

bunu yapmak yerine Common Lisp'in en güçlü özelliklerinden biri olan makrolardan da faydalanabiliriz (lütfen diğer dillerdeki primitif makro kavramları ile karıştırmayalım! ;-):

(defmacro defun-memo (fn args &body body)

"'memoized' fonksiyon tanimlama makrosu."

`(memoize (defun ,fn ,args . ,body)))

Böylece artık fonksiyonumuzu doğrudan

(defun-memo fn (x) ...)

olarak yazabiliriz. Emacs+SLIME ortamında dinamik makro açılımından faydalanarak .lisp dosyamızın içine

(defun-memo fib (n)

(if (<= n 2) 1

(+ (fib (- n 1)) (fib (- n 2)))))

yazalım ama derlemeksizin SLIME'ın makro açma özelliğinden (macro expand) faydalanmak için başına gidip C-c RET (yani önce Ctrl-C ardından da ENTER) basalım, SLIME bize ayrı bir ekranda aşağıdaki açılımı gösterecektir:

(MEMOIZE (DEFUN FIB (N) (IF (<= N 2) 1 (+ (FIB (- N 1)) (FIB (- N 2))))))

q tuşuna basıp geri dönebiliriz. Aynı bilgiyi edinmenin bir başka yolu ise doğrudan Common Lisp'in macroexpand-1'inden faydalanabiliriz:

CL-USER> (macroexpand-1 '(defun-memo fib (n)

(if (<= n 2) 1

(+ (fib (- n 1)) (fib (- n 2))))))

(MEMOIZE (DEFUN FIB (N) (IF (<= N 1) 1 (+ (FIB (- N 1)) (FIB (- N 2))))))

T

CL-USER>

Bütün bu makro muhabbetinin nelere kadir olduğunu görmek için Peter Seibel'in Practical Common Lisp kitabının Macros: Defining Your Own ve David B. Lamkins'in Successful Lisp kitabının Essential Macro Definition bölümlerine bakabilirsiniz.

"Memoization" tekniğini şimdi de hız açısından biraz inceleyelim. Bunun için önce fib fonksiyonunun özgün halini tekrar derleyelim, ardından da untrace ile izlemeyi kapatıp time ile analiz edelim:

CL-USER> (untrace fib)

WARNING: Function is not TRACEd: FIB

T

CL-USER> (time (fib 30))

Evaluation took:

0.121 seconds of real time

0.110983 seconds of user run time

0.0 seconds of system run time

0 page faults and

0 bytes consed.

832040

CL-USER> (time (fib 35))

Evaluation took:

1.321 seconds of real time

1.236812 seconds of user run time

0.002 seconds of system run time

0 page faults and

0 bytes consed.

9227465

CL-USER> (time (fib 36))

Evaluation took:

2.237 seconds of real time

1.962701 seconds of user run time

9.99e-4 seconds of system run time

0 page faults and

0 bytes consed.

14930352

CL-USER> (time (fib 37))

Evaluation took:

3.402 seconds of real time

3.195515 seconds of user run time

0.003 seconds of system run time

0 page faults and

0 bytes consed.

24157817

Şimdi bir "memoized" sürümü zaman açısından inceleyelim:

CL-USER> (memoize 'fib)

#<CLOSURE (LAMBDA (X)) {91F2545}>

CL-USER> (time (fib 34))

Evaluation took:

0.0 seconds of real time

0.0 seconds of user run time

0.0 seconds of system run time

0 page faults and

8,096 bytes consed.

5702887

CL-USER> (time (fib 35))

Evaluation took:

0.0 seconds of real time

0.0 seconds of user run time

0.0 seconds of system run time

0 page faults and

0 bytes consed.

9227465

CL-USER> (time (fib 36))

Evaluation took:

0.0 seconds of real time

0.0 seconds of user run time

0.0 seconds of system run time

0 page faults and

0 bytes consed.

14930352

CL-USER> (time (fib 37))

Evaluation took:

0.0 seconds of real time

0.0 seconds of user run time

0.0 seconds of system run time

0 page faults and

0 bytes consed.

24157817

CL-USER> (time (fib 400))

Evaluation took:

0.0 seconds of real time

0.0 seconds of user run time

0.0 seconds of system run time

0 page faults and

0 bytes consed.

176023680645013966468226945392411250770384383304492191886725992896575345044216019675

Kendiniz de pratik olarak birkaç deneme yaparsanız özgün fib 50 gibi bir girdi için bile epey beklediğini, "memoized" fib'in ise 1000. Fibonacci sayısını dahi rahatlıkla kısa sürede hesaplayabildiğini (!) göreceksiniz. Burada detaylı bir algoritma karmaşıklık analizine girmiyoruz ancak meraklısı kaynakçada belirtilen PAIP kitabında bunları bulabilir.

Biraz Daha Gelişmiş Bir "Memoization"

Yukarıdaki memoize fonksiyonunun bazı eksiklikleri olduğunu fark etmiş olabilirsiniz, söz gelimi sadece tek parametreli fonksiyonlar için çalışıyor, "hash" tablosundan girdileri silmek için bir fonksiyon tanımlanmış durumda değil ve hash tablosunda değer ararken eşitlik kontrolü için sadece eql kullanıyor, oysa bazı durumlarda equal ya da eq kullanmak isteyebiliriz.

Aşağıda bu problemleri bertaraf eden memoize tanımlamalarını inceleyebilirsiniz:

(defun memo (fn name key test)

"fn fonksiyonunun memo-fonksiyonunu döndür."

(let ((table (make-hash-table :test test)))

(setf (get name 'memo) table)

#'(lambda (&rest args)

(let ((k (funcall key args)))

(multiple-value-bind (val found-p)

(gethash k table)

(if found-p

val

(setf (gethash k table) (apply fn args))))))))

(defun memoize (fn-name &key (key #'first) (test #'eql))

"fn-name'in global tanimini 'memoized' versiyonla degistir."

(setf (symbol-function fn-name)

(memo (symbol-function fn-name) fn-name key test)))

(defun clear-memoize (fn-name)

"Fonksiyonla iliskilendirilmis hash tablosunu temizle."

(let ((table (get fn-name 'memo)))

(when table (clrhash table))))