Thread overview
Bir split incelemesi
Feb 13, 2012
zafer
Feb 14, 2012
Salih Dinçer
Feb 14, 2012
zafer
Feb 15, 2012
zafer
February 14, 2012

Bir önceki konuda (http://ddili.org/forum/thread/711) leftJustify metodunu incelemeye çalışmış ama işin göründüğü gibi basit olmadığını anlayınca tabir yerinde ise yan çizmiş ve işi yarıda bırakmıştım :-D Şimdi bunu bir kez daha denemek istiyorum. Bu sefer split() metodunun basit bir versiyonunu incelemek niyetindeyim. Bakalım neler öğreneceğiz;

S[] split(S)(S s) if (isSomeString!S)
{
   size_t istart;
   bool inword = false;
   S[] result;

   foreach (i; 0 .. s.length)
   {
       switch (s[i])
       {
       case ' ': case '\t': case '\f': case '\r': case '\n': case '\v':
           if (inword)
           {
               result ~= s[istart .. i];
               inword = false;
           }
           break;
       default:
           if (!inword)
           {
               istart = i;
               inword = true;
           }
           break;
       }
   }
   if (inword)
       result ~= s[istart .. $];
   return result;
}

Ben split (http://www.dlang.org/phobos/std_array.html#split) metodu olarak phobos kütüphanesinin array modülünde yaşıyorum. Beni tasarlayanlar farklı tiplerle çalışabilmem için beni bir şablon (http://ddili.org/ders/d/sablonlar.html) metodu olarak tasarladırlar. Bu sebeple normal metodlardan bazı farklarım var.

S[] split(S)(S s) if (isSomeString!S)

İşlemlerimi S isimli bir tip ile yaparım ve bu S tipini senin bildirmeni beklerim, ayrıca üzerinde çalışabilmek için senin bildirdiğin S tipinde s isimli bir değişkende isterim. Tüm işlemlerimi bitirdiktan sonra sana yine S tipinde bir dizi göndereceğim. Sende ona göre gerekli hazırlıklarını yapmalısın. Bu arada küçük bir kısıtlamam var S tipini kafana göre seçemezsin bir string tipi olmalı.

   size_t istart;
   bool inword = false;
   S[] result;

Düzenli çalışmayı çok severim bundan dolayı öncelikle işlerim esnasında kullanacağım değişkenlerimi hazırlayayım.

foreach (i; 0 .. s.length)

Değişkenlerimde hazır olduğuna göre artık bana gönderilen karakter katarını incelemeye başlayabilirim. Ancak çalışma masam çok küçük hepsi buraya sığmaz, en güzeli ben hepsi ile teker teker ilgileneyim.

switch (s[i])

Evet şimdi ilk karakterimiz alalım bakalım kimmiş bu ?

       case ' ': case '\t': case '\f': case '\r': case '\n': case '\v':
           if (inword)
           {
               result ~= s[istart .. i];
               inword = false;
           }
           break

"Heyy, karakter acaba sen boşluk karakteri veya bir kaçış karakteri misin?" Eğer öyle isin seninle devam edebiliriz ama öncelikle bir şeyi daha kontrol etmem gerekiyor. Eğer inword değişkenim izin verirse istart değişkenimin söylediği noktadan başlayıp senin bulunduğun moktaya kadar olan bütün karakterleri alıp result değişkenime ekleyeceğim, ama seni eklemeyeceğim. Ayrıca inword değişkenimin değerinide false olarak ayarlamalıyım. Yok inword izin vermezse seninle bir işim yok demektir sıradaki karaktere gececeğim.

   default:
           if (!inword)
           {
               istart = i;
               inword = true;
           }
           break;

Eğer sen boşluk veya kaçış karakteri dışında başka herhangi bir karakter isen buradan devam edelim ama öncelikle inword değişkenimden izin almam gerekiyor. Eğer inword değişkenim izin verirse senin bulunduğun noktayı istart değişkenime söylemeliyim ve ardından inword değişkenimi true yapmalıyım. Yok inword izin vermezse seninle bir işim yok demektir sıradaki karaktere gececeğim.

if (inword)
       result ~= s[istart .. $];

Ohh! nihayet tüm karakterleri inceleme işimi bitirdim. Ancak inword değişkenimi bir kontrol edeyim hala sonuca eklemem gereken karakterler var mı? Varsa onlarıda ekleyeyim.

return result;

ve mutlu son...boşluk ve kaçış karakterlerinden ayrılmış metin listeni al ve güle güle kullan :)

'Gözlemler :'

case ' ': case '\t': case '\f': case '\r': case '\n': case '\v':

** Bu case satırı gerçekten güzel kurgulanmış, bu sayede split metni sadece boşluklardan ayırmakla kalmamış kaçış karakterlerinide metnin içinden temizlemeyi başarmış. Burada önemli bir nokta kaçış karakterleri olmuş yani normalde bu tür karakterler kelimelerin sonunda olur ama örneğin şöyle bir kelimede "za\tfer" split \t karakterinide bir ayraç gibi görüp kelimeyi "za" ve "fer" şekilnde parçalıyor. Bu da bize çok ender de olsa kütüphane kodlarının da da bazı uç durumlarda yanlış bilgi üretebileceğini ve bu durumu kontrol etmek için elimizdeki en iyi aracın unittestler olduğunu ortaya koyuyor. Ayrıca splitin metni boşluklardan böldükten sonra boşlukları temizlediğinide gözden kaçırmamk gerekir diye düşünüyorum. Örnek uygulama şöyle olabilir.

module main;

import std.stdio;
import std.array;

void main()
{
   string metin = "Za\tfer D ile çalışmayı\t seviyor.";

   // split!(string)(metin); açık yazımı bu şekildedir.
   string kelimeler[] = split(metin);

   foreach (kelime; kelimeler)
   {
       writefln("Yeni kelimeler: -%s-", kelime);
   }
}

** Bir diğer konu inword kullanımıdır. Bu değişken sayesinde split bir kelimenin başını ve sonunu bulabilir. Açıkcası case ve if'in bu şekilde organize edilmesi beni oldukça etkiledi. Kelimelerin başını ve sonunu bulmak için ne ölçüm yapılıyor nede bir kıyas sadece bir bayrak yardımı ile bu iş çok basitçe kotarılmış, benim hoşuma gitti.

Aslında başka dillerdeki split motodlarınıda araştırıp kıyaslar yaparak sadece D dili bilgimizi değil, kod okuma ve programcılık tekniklerimizide geliştirebiliriz diye düşünüyorum bu açıdan bakınca bu tür incelemelerin ne denli faydalı olduğununa bir kez daha inamış oldum. Ancak mümkünse iki veyda daha fazla kişi ile böyle bir çalışma çok daha verimli olur diye düşünüyoırum.

Evet, bu konuyu dahada zenginleştirmek isteyenler lütfen buyrun ;-)

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

February 14, 2012

Çok iyi bir yazı olmuş. Sırf karışmış olmak için karışacağım. :)

Alıntı (zafer):

>

bu S tipini senin bildirmeni beklerim

Örnek kullanımda da görüldüğü gibi işlev şablonlarında çoğu durumda S gibi türleri bildirmek gerekmez; onlar çıkarsanırlar (template parameter deduction).

Alıntı:

>

Eğer inword değişkenim izin verirse

Ben bayrak değişkenlerine hiç "izin" gözüyle bakmamışım. :) Ben "eğer bir sözcük içinde isek" gibi bir durum değişkeni (state variable) olarak görüyorum.

Alıntı:

>

"za\tfer" split \t karakterinide bir ayraç gibi görüp kelimeyi "za" ve "fer" şekilnde parçalıyor. Bu da bize çok ender de olsa kütüphane kodlarının da da bazı uç durumlarda yanlış bilgi üretebileceğini

Ama bu işlevin kullanım amacına göre '\t' de bir ayraçtır. O açıdan bakınca işlevin yanlış bilgi ürettiğini söyleyemeyiz. Eğer kullanıcısı '\t'nin ayraç olmasını istemiyorsa başka bir çözüm bulmalıdır.

Alıntı:

>

case ve if'in bu şekilde organize edilmesi

Evet, gerçekten çok temiz bir kod olmuş. :) Orada case kullanılmasının bir nedeni de derleyicilerin case'leri bir atlama tablosu (jump table) olarak gerçekleştirebilmeleri olabilir.

Normalde o uzun case satırı için teker teker karşılaştırma yapılır ve şunun eşdeğeri olur:

   auto değer = s[i];
   if ((değer == ' ') || (değer == '\t') || (değer == '\f') ||
       (değer == '\r') || (değer == '\n') || (değer == '\v'))

Eğer karakter '\v' ise ona gelene kadar bir sürü karşılaştırma yapılması gerekir.

Oysa bir tablo olsa:

   bool[] ayraç_mı = [ false, false, false, /* ... */ true, /* ... */ false ];

O tablonun içinde yalnızca ayraçlara karşılık gelen yerler true olur. O zaman kod şöyle daha hızlı işler:

   if (ayraç_mı[s[i]])

Yani değer indeks olarak kullanılır ve eğer orada true varsa ayraç demektir.

Tabii ayraç_mı gibi bir tabloyu programcı da tanımlayıp kullanabilir ama switch-case (veya if-else-if) ile yapmak daha kolaydır.

Ama derleyici işte perde arkasında zaten öyle bir tablo oluşturur. (Sanmışım ama aşağıdaki denemelere bakılırsa bu doğru değil. (?) Ya dmd bu eniyileştirmeleri yapmıyor ya da mikro işlemcilerin karşılaştırma komutları zaten çok hızlı olduğundan belki de tablo yöntemi daha bile yavaş kalıyor. (?)

Denemek için şu programı yazalım:

import std.stdio;

void main(string[] parametreler)
{
   string s = parametreler[0];

   switch (s[0]) {
   case ' ': case '\t': case '\f': case '\r': case '\n': case '\v':
       writeln("boşluk");
       break;

   default:
       break;
   }
}

O programı .o olarak derlemek için:

'$ dmd -c deneme.d'

Onun oluşturduğu deneme.o'yu assembly olarak görmek için:

'$ obj2asm deneme.o > deneme.s'

Şimdi deneme.s'yi açarsak _Dmain ile başlayan bölümde şunu görüyoruz:

' cmp ECX,020h
je L6C
cmp ECX,9
je L6C
cmp ECX,0Ch
je L6C
cmp ECX,0Dh
je L6C
cmp ECX,0Ah
je L6C
cmp ECX,0Bh
je L6C
jmp short L81
L6C: push dword ptr _TMP0@PC32[04h][RIP]
push dword ptr FLAT:.rodata[0Ch][RIP]
call _D3std5stdio16__T7writelnTAyaZ7writelnFAyaZv@PC32
'

cmp, mikro işlemcinin "compare" (karşılaştır) komutu. je, "jump if is equal to" (eğer eşitse şu etikete atla) komutu... ECX yazmacındaki değer peş peşe ' ', '\t', vs. değerleriyle karşılaştırılıyor ve eşit olduğunda L6C etiketine atlanıyor. O etiketin üçüncü komutu olarak bir call var. Yani bir işlev çağrısı.

Yani yukarıdaki duruma bakınca '\v' geldiğinde gerçekten de şanssız bir durumda olduğumuzu görüyoruz. Hatta, en kötüsü boşluk olmayan karakterlerde karşımıza çıkıyor: 'a' gibi bir karakter geldiğinde önce altı karşılaştırma ile boşluk olup olmadığına bakılacak ve değilse devam edilecek. (Bu örnekte devam etme kodu "jmp short L81" komutu. O, default'a karşılık geliyor.)

Şimdi aynı kodu -O seçeneği ile derleyelim ve onun assembly karşılığına bakalım:

'$ dmd -c deneme.d -O
$ obj2asm deneme.o > deneme_HIZLI.s'

Şaşırıyorum! Çünkü onun durumu da aynı. -O kullanıldığı halde yine art arda cmp ve je komutları var. Hmmm. Belki de 6 çift cpm ve je zaten yavaş değillerdir. Belki de mikro işlemci onları koşut olarak işletiyordur. dmd de bunu bildiğinden belki de bir atlama tablosuna gerek görmüyordur.

Bu noktada ilgimi kaybettim. :-p

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

February 14, 2012

Öncelikle lezzetli bir inceleme olmuş, teşekkürler...

Boş vakit bulduğum an, ben de katkı sağlayacağım inşaallah.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

February 15, 2012

Alıntı (acehreli):

>

Örnek kullanımda da görüldüğü gibi işlev şablonlarında çoğu durumda S gibi türleri bildirmek gerekmez; onlar çıkarsanırlar (template parameter deduction).

Haklısın Ali, ben daha çok hikayeyi metodun kendi ağzından anlatır gibi yazmaya çalıştım. Bu sebeple S tipinin bildirilmesi gerekir diye düşünmüştüm. Burada bildirimi açıkca kullanıcı yapabileceği gibi D kendi imkanları ile de yapabilir tabi, sorun yok ;-)

Alıntı:

>

Ben bayrak değişkenlerine hiç "izin" gözüyle bakmamışım. :) Ben "eğer bir sözcük içinde isek" gibi bir durum değişkeni (state variable) olarak görüyorum.

Belkide bu farklı bakış açıları bu forumu zengin hale getiriyor :) Ben belki biraz daha farklı açıdan bakıp içerikten ziyede sadece değişkenin görevine odaklandığım için böyle düşünmülş olabilirim.

Alıntı:

>

Ama bu işlevin kullanım amacına göre '\t' de bir ayraçtır. O açıdan bakınca işlevin yanlış bilgi ürettiğini söyleyemeyiz. Eğer kullanıcısı '\t'nin ayraç olmasını istemiyorsa başka bir çözüm bulmalıdır.

Benim split (http://www.dlang.org/phobos/std_array.html#split) metodundan anladığım boşlukları ayraç olarak kullanarak metni kelimelere ayırdığı şeklinde. Böyle anladığım için kaçış karekterlerini ayraç olarak kullanması bana yanlış gelmişti. Yoksa tabi ki ayraçları bizim belirlediğimiz bir split sürümüde mevcut.

Alıntı:

>

Oysa bir tablo olsa:

>     bool[] ayraç_mı = [ false, false, false, /* ... */ true, /* ... */ false ];
> ```

>
> O tablonun içinde yalnızca ayraçlara karşılık gelen yerler true olur. O zaman kod şöyle daha hızlı işler:
>
>
>
if (ayraç_mı[s[i]])
>

Yani değer indeks olarak kullanılır ve eğer orada true varsa ayraç demektir.

Bu tablo olayını anlamadım. Yani bu dizide ayraçlar true ise false olanlar ne? Yada bu dizinin boyutu nedir? Nasıl oluşturulur gibi sorulardan dolayı bu kısımdan sonrası biraz sisli oldu :)

Ali böyle alt düzeye doğru iniyoruz, aslında hoşumada gidiyor ama tabi pek aşina olduğumuz konular olmadığı için anlamkata pek kolay olmuyor ama keyifle okuyup inceliyorum. Biraz Assembly dilinede bakmakta fayda var, seni takip edebilmek için :-D

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

February 15, 2012

Alıntı (zafer):

>

boşlukları ayraç olarak kullanarak

Ama '\t' (TAB) karakteri de geleneksel olarak boşluktur. Konsolda veya internette 'man isspace' yapınca okuduğumuz belgede C'den gelen whitespace kavramının '\t'yi de içerdiğini görürüz.

Alıntı:

>
>     bool[] ayraç_mı = [ false, false, false, /* ... */ true, /* ... */ false ];
> ```

>
> O tablonun içinde yalnızca ayraçlara karşılık gelen yerler true olur. O zaman kod şöyle daha hızlı işler:
>
>
>
if (ayraç_mı[s[i]])
>

Yani değer indeks olarak kullanılır ve eğer orada true varsa ayraç demektir.

Alıntı:

>

Yani bu dizide ayraçlar true ise false olanlar ne?

Ayraçların kodların karşılık gelen yerlerde true var, diğer karakterlere karşılık gelen yerlerde false var.

Alıntı:

>

bu dizinin boyutu nedir?

  1. Karakterin kodu indeks olarak kullanılıyor ve orada true varsa boşluktur, false varsa değildir. (if deyiminde indeks olarak s'in i'inci karakteri kullanılıyor. Yani s dizgisinin i'inci karakteri ayraç_mı dizisinin indeksi oluyor.)

Daha basit ve çok saçma bir örnekle göstereyim:

import std.stdio;
import std.exception;

/*
* [0,6] aralığında gün sayısı alır ve 5 veya 6 ise true döndürür.
*/
bool haftaSonu_mu(size_t indeks)
{
   enforce(indeks < 7, "indeks [0,6] aralığında olmalıdır");
   bool[7] tablo = [ false, false, false, false, false, true, true ];
   return tablo[indeks];
}

void main()
{
   auto sonuç = haftaSonu_mu(5);
}

Yani aslında bir eşleme tablosu gibi kullanıyoruz. Anahtar, karakterin değeri oluyor, değer de dizide orada bulunan false/true değeri.

Alıntı:

>

Nasıl oluşturulur

Tablo derleme sırasında kaynak koda yazılır (veya çok uzunsa hesaplanarak oluşturulur) ve en iyisi 'immutable' olarak işaretlenir.

Alıntı:

>

Ali böyle alt düzeye doğru iniyoruz

Birlikte öğreniyoruz. :)

Alıntı:

>

Biraz Assembly dilinede bakmakta fayda var, seni takip edebilmek için :-D

Benim assembly bilgim bu konuda görüldüğü kadardır.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

February 15, 2012

Alıntı (acehreli):

>

Ama '\t' (TAB) karakteri de geleneksel olarak boşluktur. Konsolda veya internette 'man isspace' yapınca okuduğumuz belgede C'den gelen whitespace kavramının '\t'yi de içerdiğini görürüz.

Hımm... Enterasan ve güzel bir nokta, haklısın tab netice bir boşluk üretiyor. Ancak orada ben \t karakterini sadece örnek olarak vermiştim. Şimdi bu açıklamadan sonra "\t, \f, \r, \n, \v" karakterlerinide boşluk olarak mı değerlendirmek gerek? En azından ben \r karakterinin satırbaşı olduğunu biliyorum. Şimdi satırbaşıda temelde bir boşluk mudur gibi bir soru aklıma takıldı :)

Alıntı:

>

Ayraçların kodların karşılık gelen yerlerde true var, diğer karakterlere karşılık gelen yerlerde false var.

Anladığım kadarıyla metin içindeki her bir karektere karşılık bir true veya false degeri içeren tablo oluşturuyoruz. Bu tabloyu doldururken önce metindeki ilgili karaktere bakıyor ve bir ayraç ise true değilse false değerini tablonun ilgili indeksine yazıyoruz.

Bunun ardından artık tek tek karşılaştırmak yerine metindeki karakterin indeks numarasından faydalanıp tablodan ayraç olup olmadığına bakıyoruz. Bence güzel bir yöntem aslında böyle bir deneme yapmak gerek, sanki daha hızlı bir yöntem gibi görünüyor.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

February 16, 2012

Alıntı (zafer):

>

bir deneme yapmak gerek, sanki daha hızlı bir yöntem gibi görünüyor.

İşte en önemlisi de o! Deneme yapmadan hiçbir şey bilemeyiz. :) Belki de bu bool tablosu daha yavaş olacaktır.

Bununla ilgili bir konuyu şurada açtım:

http://ddili.org/forum/thread/724

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]