Forum: Ders Arası RSS
triBit
trinaryStack.d
Avatar
Salih Dinçer #1
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: triBit
Merhaba,

Bir süredir program yazmıyorum ve az önce, ara verdiğim sırada gerçekleşen önceki tartışmalara bakıyordum. Ali hocanın program fikri (-bknz. Banka hesap numarası okuma) aklıma, en az üç konumlu (True/False haricinde bir de Conflict) mantık değerinin çok işe yarabileceğini getirdi...

- Biliyorsunuz, Quantum Computing biliminde, elektronların alabileceği diğer karışık durum (hem 1, hem 0) gibi olaylar var.
- Hatta üç boyutlu modellemede (3D Modelling) X, Y haricinde bir Z'ye ihtiyaç duyuyoruz.
- Olayı daha da ileri götürüp (hali hazırda bir olanak) DNA bazı çiftlerini (A-T ve C-G) temsil edilebilir!

Bunlar için şöyle bir dizi ikilisi oluşturacağım:
    private T[] highBit;  // lowBit ve highBit 1 ise Z; tersi N(ull)
    private T[] lowBit;   // lowBit 1, highBit 0 ise Y; tersi X 
Sonra bunları aşağıdaki veri türü ile döndürmeyi düşünüyorum...
    enum triBit { N, X, Y, Z }
Ama veriler, daha önce forumda dolaylı olarak paylaştığım "Universal Stack" ile yapılacak. Böylece bellekte az yer kaplayacağı için çok verimli olacak. Ancak yukarıdan anlaşılacağı üzere (ve an itibariyle) kolaya kaçmış durumdayım. Çünkü highBit ve lowBit isminde iki diziden faydalanıp 00, 01, 10 ve 11 durumlarını iki değişken üzerinde tutmaya karar verdim...

Peki; sizce bunu yapmak yerine, CPU'dan biraz daha feragat edip (böylece %50 bellek tasarrufu mümkün) tek dizi üzerinden (küçük bir trick ile mümkün görünüyor!) yapmak daha mantıklı olabilir mi? Yani demek istediğim 1 byte'lık veri içersinde 4 tane tüm olasılıkları (00, 01, 10, 11) yerleştirebiliriz. Bunun için yapılacak trick ise sanki şu satır ile başlamak:
    public:
        immutable type_length = (T.sizeof * 4); //<-- 8 idi sadece 4 yaptım ve belki olacak...:) 
Bu arada universalStack kodlarını vereyim. Bu yığıt, benim gerçekten çok işime yarıyor. Çünkü bellekte true/false olarak duran veriler çok yer kaplıyorlar. Oysa biraz işlemle daha az yer kaplamaları mümkün.
class universalStack(T) {
    private int konum;
    private T[] stack;
     
    public:
        immutable type_length = (T.sizeof * 8);
 
    this (size_t size) {
        size_t taşmaVar_mı = size % type_length ? 1 : 0;
        stack = new T[(size / type_length) + taşmaVar_mı];
    }
   
    void push(bool veri) @property {
        immutable index = konum / type_length;
        immutable xMask = konum % type_length;
 
        if(veri) stack[index] |= cast(T)1 << xMask;
        konum++;
    }
    
    private bool bitTest(size_t bit) {
        T xCell = stack[bit / type_length];
        T xMask = cast(T)1 << bit % type_length;/*
                       ^----bu çok önemli çünkü
                       ulong'da sıkıntı yapıyor! */
        return (xCell & xMask) != 0;
    }
 
    override string toString() { 
        string sonuç = "[";
        foreach(i; 0..(type_length * stack.length)) {
            sonuç ~= bitTest(i) ? "1" : "0";
        }
        return sonuç ~ "]";     
    }
}
 
import std.stdio;
 
void main() {
  auto data = [ true, true, false, false, true, true ];
  auto test = new universalStack!ubyte(1);
  
  foreach(d; data) test.push(d);
  
  test.writeln;
}
İlgili kaynaklara da bakınız:
- http://en.wikipedia.org/wiki/Four_value_logic
- http://en.wikipedia.org/wiki/Quaternary_numeral_system
- http://en.wikipedia.org/wiki/Qubit
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Evet, universalStack çok kullanışlı bir tür olmuş.

Gereksiz notlar: :)

  • İsmi boolStack de olabilirmiş.

  • Taşmaya bağlı olarak yer ayırmak için ben şunu biliyorum:
    this (size_t size) {
        stack = new T[size + type_length - 1) / type_length];
    }
* xMask'ın ismi bana & ve | işleçleriyle maskelemeyi çağrıştırıyor. Sanırım sen onu maske olarak değil de, maskeyi oluştururken kaydırma değeri olarak kullanıyorsun.

  • push() içindeki if(veri) yalnızca hız kazancı içinmiş gibi görünüyor çünkü o denetimi kaldırsak bile veri false olduğunda etkisizdir. Ama onun için kaydırma değeri olarak veri'yi kullanmak gerekirdi:
    stack[index] |= cast(T)veri << xMask;
Ama eğer amaç gerçekten hız kazancı ise, o zaman o denetim işlevin bütün içeriğini de kapsayabilir.

  • Çok kişisel bir tercih olarak, bitTest() yerine bit() gibi bir ismi (veya opIndex()'i) beğenirdim. Böylece belirli bir konumdaki değeri döndürmüş olurdu. Ama çok önemsiz bir ayrıntı... :)

  • toString içindeki döngünün konum'a kadar ilerlemesi daha doğru olabilir çünkü gösterdiğin örnekte 6 veri olmasına rağmen 8 değer gösteriyor.

Ali
Avatar
Salih Dinçer #3
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yorumlar için teşekkürler...

Kolayına kaçarak ilk aklıma gelen yöntem bitti! Moleküler biyoloji ile ilgilenenler için ikinci bir tür ile kullanıma hazır:
enum triBit {
  N,  // 00 - Null     (A)
  X,  // 01 - False    (C)
  Y,  // 10 - True     (G)
  Z   // 11 - Conflict (T)
}
enum DNA { A, C, G, T }
 
class Stack(T) {
    private int konum;
    private T[] highBit;  // lowBit ve highBit 1 ise Z; tersi N(ull)
    private T[] lowBit;   // lowBit 1, highBit 0 ise X; tersi Y
     
    public:
        immutable type_length = (T.sizeof * 8);
 
    this (size_t size) {
        size_t taşmaVar_mı = size % type_length ? 1 : 0;
        highBit = new T[(size / type_length) + taşmaVar_mı];
         lowBit = new T[(size / type_length) + taşmaVar_mı];
    }
   
    triBit pop(size_t index) {
        auto merge = bitTest(index) ? 1 : 0;
             merge <<= 1;
             merge |= bitTest(index, false) ? 1 : 0;
             
        return cast(triBit)merge;
    }
    void push(int veri) @property {
        immutable index = konum / type_length;
        immutable xMask = konum % type_length;
 
        if(veri > 1) highBit[index] |= cast(T)1 << xMask;
        if(veri % 2)  lowBit[index] |= cast(T)1 << xMask;
        konum++;
    }
    
    bool bitTest(size_t bit, bool high_low = true) {
        T xCell;
        if(high_low) xCell = highBit[bit / type_length];
        else xCell = lowBit[bit / type_length];
        
        T xMask = cast(T)1 << bit % type_length;/*
                       ^----bu çok önemli çünkü
                       ulong'da sıkıntı yapıyor! */
        return (xCell & xMask) != 0;
    }
 
    string toString() { 
        string sonuç = "highBit = [";
 
        foreach(i; 0..(type_length * highBit.length)) {
            sonuç ~= bitTest(i) ? "1" : "0";
        }
        sonuç ~= "]\nlowBit  = [";
        
        foreach(i; 0..(type_length * lowBit.length)) {
            sonuç ~= bitTest(i, false) ? "1" : "0";
        }
        
        return sonuç ~ "]";
    }
}
 
import std.stdio;
 
void main() {
  int[] data;
  with(DNA) data = [ T, A, C, C, C, G, G, G ];
  auto test = new Stack!ubyte(2);
  
  foreach(d; data) test.push(d);
  
  test.writeln;
 
  foreach(i, d; data) {
    d.write(": ");
    (cast(DNA)test.pop(i)).writeln;
  }  
}
Çıktısı:
highBit = [10000111]
lowBit  = [10111000]
3: T
0: A
1: C
1: C
1: C
2: G
2: G
2: G
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #4
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Tek bitleri sakladığına benzer biçimde iki bit de yan yana saklanabilir mi? highBit ve lowBit'e neden gerek olduğunu tam anlamadım.

Ayrıca isimlendirme konusunda bir kaç şikayetim daha var çünkü isimler çok önemli:

  • tribit: Daha önceki açıklamana ve ismin baş tarafına bakılırsa üç değerli durumlarla ilgileniyoruz. Ama bit olarak 2 bit var ve durum sayısı üç değil, dört. Bu durum beni karıştırıyor. :)

  • high_low parametresinin ne anlama geldiği isminden anlaşılamıyor. Örneğin onun değerinin true olması ne demek olabilir? Bunu anlayabilmemin tek yolu var: kodu okumak. Eğer öyleyse ismi yeterince iyi değil demektir. :-/

Anladığıma göre, belirli bir konumdaki değeri bilebilmek için bitTest()'i iki kere, false ve true değerleriyle çağırmak gerekiyor. Bu durumda hızın ne kadar önemli olduğunu bilmiyorum ama daha hızlı yöntemler olabilir.

Ali
Avatar
Salih Dinçer #5
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #2
acehreli:
Gereksiz notlar: :)
Estağfirullah...

acehreli:
İsmi boolStack de olabilirmiş.
Bence de...:)

acehreli:
Taşmaya bağlı olarak yer ayırmak için ben şunu biliyorum:
    this (size_t size) {
        stack = new T[size + type_length - 1) / type_length];
    }

Bu daha basit bir yöntem ve tercih edilebilir. Gerçi diğerinde, "taşmaVar_mı" değişkeni sayesinde, açıklamaya ihtiyaç bırakmadan ayrılan yerin kayıt edilen bellek biriminden fazla olduğunda çalışacağını ifade ediyor. Hız açısından da hiç fark etmeyeceğinden o da güzel.

acehreli:
  • xMask'ın ismi bana & ve | işleçleriyle maskelemeyi çağrıştırıyor. Sanırım sen onu maske olarak değil de, maskeyi oluştururken kaydırma değeri olarak kullanıyorsun.

  • push() içindeki if(veri) yalnızca hız kazancı içinmiş gibi görünüyor çünkü o denetimi kaldırsak bile veri false olduğunda etkisizdir. Ama onun için kaydırma değeri olarak veri'yi kullanmak gerekirdi:
    stack[index] |= cast(T)veri << xMask;
Ama eğer amaç gerçekten hız kazancı ise, o zaman o denetim işlevin bütün içeriğini de kapsayabilir.

Aslında övünmek gibi olmasın ama burada muazzam bir kodlama pratikliği var! Belki açıklamak için yüzyüze gelmemiz lazım. Yani maske oluşturulurken veri işleniyor. Çünkü işlenecek veri sadece 1 rakamından ibaret. Bu yoksa veriyi işlemeyeceğinden bulunduğu yer sıfır olacaktır. Çünkü bu bir yığıt ve her zaman 0 olan bir bellek birimine erişiliyor. Dolayısıyla kaydırma sayısı maskenin kendisini oluşturuyor. Bu bit olayı çoğumuzun kafasını karıştıracaktır ama o kodun doğru çalışması için if()'in olması gerekiyor...:)

acehreli:
  • Çok kişisel bir tercih olarak, bitTest() yerine bit() gibi bir ismi (veya opIndex()'i) beğenirdim. Böylece belirli bir konumdaki değeri döndürmüş olurdu. Ama çok önemsiz bir ayrıntı... :)

Estağfirullah, opIndex()'li kullanımını merak ettim doğrusu. Aslında bu işlevi, iç kullanım için düşünmüştüm. Tabi dışarıya da açılabilir de. Özellikle trinaryStack için yeni bir parametre eklemek zorunda kaldım. Çünkü test edilen artık iki bit yani dizi var.

acehreli:
  • toString içindeki döngünün konum'a kadar ilerlemesi daha doğru olabilir çünkü gösterdiğin örnekte 6 veri olmasına rağmen 8 değer gösteriyor.

Burada daha çok toString'i bir kolaylık olarak kullanıyorum. Yani sınıfı test etmek için var. Olmayabilir de çünkü pop() işlevleri ile veriyi çekebiliyoruz. Gerçi burada şimdi dikkat ettiğim ve unutmuş olduğum bir değişiklik yapılması gerekiyor. Her pop() çağrıldığında konum-- olduktan (eksiltildikten) sonra o hücreyi 0'a (son yığıtımızda iki hücre) eşitlemeli. Yoksa tekrar push() yapıldığında işler karışacaktır.

Özetle burada yaptığımız; iki bit'i kullanarak iki kat veriyi temsil edebildik. Gerekirse DNA bazlarını da ifade edebiliriz 3 durumlu (triState) verileri de. Üç durumlular için kalan 4. durum ise null olarak kullanırsak sanırım verinin işlenmediğ ve/veya hücreye hiç erişilmediği durumu temsil edebiliriz. Bu yığıt ile yapılabilecekleri hayal ediyorum da, söylemeyeyim ve bende kalsın...:)

Sevgiler, saygılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #6
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Salih Dinçer:
o kodun doğru çalışması için if()'in olması gerekiyor...:)

Sen hep 1 kullandığın için öyle. veri'yi kullanırsan gerekmiyor:
    void push(bool veri) @property {
        immutable index = konum / type_length;
        immutable xMask = konum % type_length;
 
        stack[index] |= cast(T)veri << xMask;    // <-- 1 değil, veri
        konum++;
    }
Dolayısıyla senin if denetiminin tek işlevi hız oluyor. Eğer öyleyse ve gerçekten daha hızlı oluyorsa, neden önceki iki işlemi de kapsamasın:
    void push(bool veri) @property {
        if (veri) {
            immutable index = konum / type_length;
            immutable xMask = konum % type_length;
 
            stack[index] |= cast(T)1 << xMask;
        }
 
        konum++;
    }
Söylemek istediğim oydu. Ama tabii her zaman olduğu gibi ölçmek gerek: if denetimi için gereken kodun hıza etkisi ne kadar?

Ali
Avatar
Salih Dinçer #7
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #4
acehreli:
Tek bitleri sakladığına benzer biçimde iki bit de yan yana saklanabilir mi? highBit ve lowBit'e neden gerek olduğunu tam anlamadım.

Önce soruyu cevaplarsak bu mümkün ama push() işlevinde kodlamayı yeniden yazmalıyım. Bu da zor olduğu için önce kolayına
kaçayım dedim. Kolayı ise zaten yaptığımız işlemi ikinci bir if() kullanarak diğer dizi için yapmak. Yani highBit ve lowBit dizileri birbirini tamamlayıcı iki bitlik bir değişken gibi kullanılıyorlar. Biri yoksa diğeri anlamsız...

acehreli:
Ayrıca isimlendirme konusunda bir kaç şikayetim daha var çünkü isimler çok önemli:

Estağfirullah, Türkçeyi iyi kullanmama rağmen bu isim olaylarında çok yetenekli değilim. Çünkü benim içim anlamlı olan bana yetiyor ama başkası için çok anlamsız olabiliyor...:)

acehreli:
* tribit: Daha önceki açıklamana ve ismin baş tarafına bakılırsa üç değerli durumlarla ilgileniyoruz. Ama bit olarak 2 bit var ve durum sayısı üç değil, dört. Bu durum beni karıştırıyor. :)
Örneğin bu...:)

Gerçekten de ben orada üç durum görüyorum. Bu benim garip olduğumdan olabilir çünkü enum'un reel'de ifade ettiği 4 durum var. Aslında imaginer size_t.max'a kadar gider de karıştırmayalım. Belki de null'u yani 0 durumunu ben durumdan saymadığım için böyle düşünüyorum. Gerçekten de yazacağım yazılımlarda bunu kullanırken yine üç durumu dikkate alacağım Null ihtiyaç olması halinde reserve edilmiş durumda. Örneğin DNA'in A bazı için...

acehreli:
* high_low parametresinin ne anlama geldiği isminden anlaşılamıyor. Örneğin onun değerinin true olması ne demek olabilir? Bunu anlayabilmemin tek yolu var: kodu okumak. Eğer öyleyse ismi yeterince iyi değil demektir. :-/

Bence çok iyi bir isim...:)

Çünkü biz Evet/Hayır diyeceğimize İngilizce'de True/False deriz. Bunlar da 1 ile 0 ve dolayısıyla high ve low'a eşittir...

acehreli:
Anladığıma göre, belirli bir konumdaki değeri bilebilmek için bitTest()'i iki kere, false ve true değerleriyle çağırmak gerekiyor. Bu durumda hızın ne kadar önemli olduğunu bilmiyorum ama daha hızlı yöntemler olabilir.
Yukarıda da ifade ettiğim gibi (tabi bu satırları yazdığımda birbirimizin yazdıklarını görmemiştik) bitTest() bir iç komut. Dolayısıyla veriye pop() ile inanılmaz hızlı bir şekilde erişlebiliyoruz. Ne bir if() var ne de bir ikinci değişken. İşte bu yüzden çift dizi kullanımı iki kat bellek ihtiyacı hissettirse de ....

( Bir dakika! Böyle bir şey yok çünkü ben veriyi tek diziye yazsaydım da bu sefer dizi de iki kat uzun olacaktı...:) )

... bence en optimum çözüm bu! Sanırım 3B modellemede bunun hızını görebiliriz. Henüz SDL'de bu kadar ilerlemedim ama yapılabilecek çok şeyin olduğuna inanıyorum. Ömrümüz yeterse!

Başarılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #8
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #6
acehreli:
    void push(bool veri) @property {
        immutable index = konum / type_length;
        immutable xMask = konum % type_length;
 
        stack[index] |= cast(T)veri << xMask;    // <-- 1 değil, veri
        konum++;
    }
İşte bakış açısı..:D

Bu yazdığın daha bir yöntem!

Ben adeta atların gözlerine takılan ve iki yandan tedirgin olmasını engelleyen perde gibi hep ileriye (1'e ve onun maskesine) bakıyormuşum. Oysa oraya veri'yi koymak çok akıllıca...:)

Ama sanırım aynı şeyi trinaryStack'a uygulayamayız. Bu yüzden binaryStack için iyi bir çözüm olduğu için izninle kullanacağım?

Sevgiler, saygılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #9
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #7
Salih Dinçer:
Çünkü biz Evet/Hayır diyeceğimize İngilizce'de True/False deriz. Bunlar da 1 ile 0 ve dolayısıyla high ve low'a eşittir...

Öyle açıklayınca mantıklıymış. Daha önce karşılaştığım bir açıklama değil. Onun sorunu, işlevin çağrıldığı noktada devam eder:
    // "true ne anlamdaydı? Parametrenin ismi high_low muydu, yoksa low_high
    // mıydı?" gibi...
    bitTest(i, true);
Ben bu gibi durumlarda enum'ı yeğliyorum çünkü o zaman hiç karışıklık olmuyor:
enum Bit { low, high }
 
void foo(size_t konum, Bit bit = Bit.high)
{
    // ...
}
 
void main()
{
    size_t i = 8;
    foo(i, Bit.low);
    foo(i, Bit.high);
}

( Bir dakika! Böyle bir şey yok çünkü ben veriyi tek diziye yazsaydım da bu sefer dizi de iki kat uzun olacaktı...:) )

Onun bir yararı da verinin bellekteki yakınlığıdır. Bütün veri mikroişlemcinin ara belleğinde olduğu için hız olarak daha iyi durumdadır. İki farklı dilim olunca o dilimler bellekte birbirlerinden uzakta olabilirler ve ara belleğe bir birisinin bir diğerinin okunması gerekebilir. (Tamamen hayal: ölçmeden bilinemez! :))

trinaryStack

Eğer özellikle kelime oyunu yapmıyorsan ternaryStack de olabilir. ;) (Ek: "trinary" de varmış! Hiç duymamıştım; öğrendim. :))

Ali
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Forum: Ders Arası RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-19, 20:02:39 (UTC -08:00)