>>>>> "BM" == Bulent Murtezaoglu <[EMAIL PROTECTED]> writes:
>>>>> "VST" == Vehbi Sinan Tunalioglu <[EMAIL PROTECTED]> writes:
VST> Ote yandan bunlar bana Regular Expression ve Turing Machine
VST> arasindaki kullanim farkini merak ettirdi. Computational
VST> complexity acisindan degil tabii ki... Ama az once gordugumuz
VST> gibi, regex yerine, bu tarz bir kod kullaninca (Turing
VST> Machine equivalent sanirim) daha az CPU cycle ve CONS ile
VST> isimizi halledebiliyoruz. Ne dersiniz?
BM> Hmm. Yok. Bunu belki biraz farkli ifade etmek lazim
BM> manasinin acik olmasi icin. Ben anlamadim bu paragrafi
BM> mesela.
Evet, pek acik degil. Hatta biraz da hatali belirtmisim.
Aciklayayim: Regular Expressionlar, Turing Machine'den cok daha
kisitli dillerdir. Bu haliyle "finite state automata" ile
islenebilirler. Yani cok daha az maliyetli ve performansi yuksek
cihazlar ile... Ancak, diyorum ki, Turing Machine diyerek
betimleyebilecegimiz programlarla, herhangi bir regex `pattern'ini bir
`finite state automata'dan daha verimli bir sekilde test edebilir
miyiz? Bizim buradaki ornegimizi ele alacak olursak, bildigim
kadariyla, regex girdinin tamamini okumadan karar vermiyor. Ornek:
Regex: ab.*
Bu ornekte "abfoobarfoobarfoobar" girdisinin tamami okunmadan karar
verilmiyor (mu acaba?). Burada dikkate deger nokta, regex makineleri
(finite state automatonlarin) bilgisayar ortaminda aslinda Turing
Machine ile (yani bir bilgisayar programlama dilinde yazilmis
programlarla) simule edildikleri icin `finite state automaton'un
basitliginden ve dolayisi ile hizindan mahrum kalmamiz.
Ayni `pattern' icin bir Turing Machine (kisacasi bir algoritma) ile
sunu da diyebilirdik:
TM: ilk iki harf sirasiyla a ve b'ye esitse KABUL, yoksa RED.
Burada anlatmaya ve anlamaya calistigim seyi bircok sekilde ifade
etmem mumkun. Bir kez de su sekilde bir soru kuruyorum:
Herhangi bir regex kutuphanesi de, kendi kendimize uyguladigimiz bir
algoritma da su islemi yapmiyor mu:
0. girdi bittiyse kabul et, aksi takdirde,
1. girdinin siradaki harfini register-1'e al,
2. kiyaslayacagin `pattern'deki siradaki harfi register-2'ye al,
3. iki registeri kiyasla, ayniysa bir sonraki harfe gec ve bu
proseduru uygulamaya devam et, degilse REDDET.
Burada dikkati cekmek istedigim olay, kiyaslama olayi.
Sonuc: Girdileri bir patternle kiyaslamak zaten hizli bir islem
degil. Regex kutuphanelerinin yazilmasinin sebebi, bu kiyaslamayi
hizli yapmak icin degilmis de hizli kod yazmak icinmis gibime
geliyor. Halbuki basit ama regexe kiyasla uygulamasi daha uzun
algoritmalarla is halletmek cok daha hizli sonuclar veriyor. Bu
genelleme dogru olabilir mi?
(Maalesef daha kisa aciklayabilecek kadar fazla zamanim yoktu,
muhabbet sogumasin dedim.)
VST> Ayrica optimizasyon icin CONS sayisi yeter gosterge midir?
BM> Kod aciksa gecin buraya bence, topluca elleyelim bakalim ne
BM> hale gelecek. Iyi bir egzersiz olur.
Agabey, izin ver, kodun oldugu dosyayi temizleyeyip, aciklamalariyla
beraber bahsettigim fonksiyonlari gondereyim. Zira, gereksiz ve
konumuzla ilgisiz bir cok fonksiyon ile kafanizi sisirmek istemem.
--vst
_______________________________________________
cs-lisp mailing list
cs-lisp@cs.bilgi.edu.tr
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
