Merhaba,
Uzun zamandır Parrot (http://www.parrotcode.org/) ile uğraşmak
istiyordum. Dün öğleden sonra kalan vaktimde biraz Parrot Assmebly'si
öğrenip amcalarımın yazdığı VM'yi test edeyim dedim. Ve tek kelime ile
hız açısından dibim düştü diyebilirim. Projenin ana fikrini zaten çok
seviyordum ama beta aşamasında olmasına rağmen bu kadar performans
göstereceği aklımın ucundan bile geçmezdi. Ne PHP, ne Perl, ne de
Python. Şu ana kadar gördüğüm en hızlı VM idi.
Hemen buna sistemi zorlayacak bir algoritma ile girişeyim ve diğer
VM'ler ile ufak bir başarım karşılaştırması yapayım dedim. Ne yapayım
diye düşünürken aklıma kombinasyon alan bir algoritma yazmak geldi.
Gecenin bir yarısı O() mertebesi en düşük derecede nasıl kombinasyon
alabilirim diye kafa yorarken, aklımda bir yandan da hep rekürsif bir
şekilde bir önceki adımda hesaplanan değerlerin tasarruf için ileri
adımlarda nasıl kullanılabileceği sorusu vardı.
Velhasıl kelam, aşağıdaki gibi bir yöntem ile çıkageldim:
+--------------------------------+
| +------------------------+|
| | +----------------+||
| | | +--------+|||
|1 |2 |3 |4 5||||
| | | | 45||||
| | | +--------+|||
| | | 34 35 |||
| | | 345 |||
| | +----------------+||
| | 23 24 25 ||
| | 245 ||
| | 234 235 ||
| | 2345 ||
| +------------------------+|
| 12 13 14 15 |
| 145 |
| 134 135 |
| 1345 |
| 123 124 125 |
| 1245 |
| 1234 1235 |
| 12345 |
+--------------------------------+
Her seferinde, en iç kutuda hesaplanan değelerler üzerine, sıradaki sayı
uygulanıyor. Ve bu şekilde rekürsif olarak ilerliyorsunuz. Üşenmedim
akşam akşam bir de buna basit bir Python kodu döktüreyim dedim:
def combinations(lst):
if len(lst) < 2:
return [(lst[0], )]
curr = (lst[0], )
combs = combinations(lst[1:])
lst = [curr] + combs
for comb in combs:
lst.append(curr + comb)
return lst
Fakat farklı VM'leri ve dilleri test edeceğim ya, bunu Scheme ile
yazmazsam bir yerlerim şişerdi:
(define combinations
; Benim tarafımdan yazılan (belli değil mi?) metod.
(lambda (lst)
(cond
((< (length lst) 2) lst)
(else
(letrec ((curr (car lst))
(combs (combinations (cdr lst)))
(iterate
(lambda (comb-lst)
(cond
((null? comb-lst) '())
(else
(append (list (append (list curr)
(car comb-lst)))
(iterate (cdr comb-lst))))))))
(append combs (list curr) (iterate combs)))))))
(define (combinations lst)
; #scheme kanalından forcer'ın kodu.
(if (null? (cdr lst))
(list lst)
(let ((curr (car lst))
(combs (combinations (cdr lst))))
(append (list (list curr))
combs
(map (lambda (comb)
(cons curr comb))
combs)))))
Ama işin komik yanı, bunu yazmak için epey bir kişi seferber olduk ve
bir çok başarısız denemeden sonra çalışır bir şeyler elde edilebildi.
(#lisp sakinlerinden de öneriler geldi. Ama onlarınki de gene böyle
uzayıp giden parantezler silsilesiydi. En temiz kodu sanırım forcer
yazdı.)
Şimdi sorum şu: Bu kadar ufak bir Python kodunun gerçekten tam olarak
Lisp dialektlerindeki karşılığı bu kadar karmaşık mı? Sizin algoritmanın
Lisp/Scheme ile yazımına ya da kendisine getireceğiniz öneriler
nelerdir?
Yemekten sonra tatlı olarak da şöyle bir Haskell kodumuz mevcut:
combinations [] = [[]]
combinations (x:xs) = combinations xs ++ [ x:xs' | xs' <- combinations xs ]
İyi çalışmalar.
P.S. GEB tartışmasına çok cevap yazmak istedim ama zaman bulamadım. Onu
af buyurursanız şimdi gidermek istiyorum: Gödel'in tamsızlık
teoreminin insanlar tarafından anlaşılabilir bir açıklamasını
Nagel & Newman'ın Türkçeye çevrilmiş Gödel Kanıtlaması kitabından
bulabilirsiniz. Bence GEB olayın hikaye kısmını biraz fazla
sulandırmış. Bana Hürriyet'in hafta sonu eklerindeki bilim ile
ilgili sayfalarını anımsattı sık sık. Ama iddaam şudur:
Nagel & Newman'ı anlasanız bile nasıl anladığınızı anlayamazsanız,
ya da neyi anladığınızı başka birine mümkün değil anlatamazsınız.
_______________________________________________
cs-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
