22 Tem 2006 tarihinde Volkan YAZICI dedi ki:
> 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.
Parrot assembly ile diğer dillerin vmlerini nasıl karşılaştırdınız
anlamadım. Muhtemelen daha hızlıdır ama derleme zamanını göreceli olarak
ortadan kaldırsanız bile derleyicilerin verimsizliğini hesaba katmanız
gerekir. (asm vs c misali)
> 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:
...
> 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
Aslında konu dışı ama kartezyen çarpmayla uğraşmak istemeyenler
alternatif olarak 0'dan 2^n-1'e kadar saydırıp 1 olan bitlere karşılık
gelen elemanları alabilir.
(Başka bir algoritma, başka bir dil (ruby))
def komb (d)
(1...(2**d.size)).map do |i|
d.values_at *(0...d.size).map {|j| (i[j]==1) ? j : nil}.compact
end
end
tabii bu kadar çok map(collect) ve compact pratikte çok hızlı sonuç
vermez.
...
> 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ı.)
burdan öyle görünüyor :)
>
> Şimdi sorum şu: Bu kadar ufak bir Python kodunun gerçekten tam olarak
> Lisp dialektlerindeki karşılığı bu kadar karmaşık mı?
karmaşıklığı nasıl tanımladığınıza bağlı. matematiksel olarak bana daha
basit görünüyor ama her şeyin temelinde işlev olması biz ölümlüler için
okuma güçlüğü yaratabiliyor. Ama Lisp kesinlikle gördüğüm en tutarlı
dil (lambda vs defun ayrımını saymazsak).
> Sizin
> algoritmanın Lisp/Scheme ile yazımına ya da kendisine getireceğiniz
> öneriler nelerdir?
O python algoritması için yukardaki forcer'ın kodundan daha "temiz" kod
benim aklıma gelmiyor. Yalnız hem python hem scheme için boş kümeyi sayan
bir algoritma azıcık daha güzel olurdu.
>
> Yemekten sonra tatlı olarak da şöyle bir Haskell kodumuz mevcut:
>
> combinations [] = [[]]
> combinations (x:xs) = combinations xs ++ [ x:xs' | xs' <- combinations xs ]
ocaml (biraz hileli):
let rec comb = function [] -> [[]]
| hd::tl -> let c=comb tl in (List.map (fun x -> hd::x) c) @ c
not: bu kod haskell kodu gibi boş kümeyi sayar
ocaml'in haskell kadar ilginç operatörleri olmayabilir ama oldukça sağlam
bir operatör yükleme mekanizması var. Zorunlu olmayan tembel
değerlendirme, isteğe bağlı emirsel ve nesnel programlama yapıları da
cabası.
sml kodu da birazcık daha "güzel"dir ama işte ruhumuzu hıza satıyoruz.
Pek adları geçmediği için reklam yapma ihtiyacı duydum :)
...
> Bence GEB olayın hikaye kısmını biraz fazla sulandırmış.
Bana da öyle gelmişti. Hatta bazı mantıksal önermeleri de çok
anlamlı değildi ama gene de konusu ve yaklaşımı güzeldi.
İyi çalışmalar
--
Bu harflerin yazımında emeği geçen GNU Emacs
İşletim Sistemi'ne teşekkürü bir borç biliriz.
http://www.bayazit.net/alphan/
_______________________________________________
cs-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
