Forum: Duyurular RSS
Yığıt (sürüm2)
Stack v2
Sayfa:  önceki  1  2 
Avatar
Salih Dinçer #16
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj ID 7828
Çok çok önemli bir düzeltme....:)
    T pop() @property
    {
        auto value = stack[--konum];
        stack.length = konum;
        return value;
    }
Bunu Ali hocamın verdiği, üsttekininiYazdır() örneğini denerken gördüğümüz hata için uygulamalıydık!

Çözümünü ise üretmek için kafa yormadım (hadi artislik olsun; bir kaç saniye düşünsem bulurdum...:)); Robert Sedgewick'in Stack dersinde gördüm. Tabi orada Java kullanıldığı için dizinin uzunluğunu değiştirmeyip null değerine eşitlemiş ama biz D programladığımıza göre çift yönlü çalışan length özelliğini kullanmalıydık...:)

Şimdi içime sine sine, hatta yavaş ve sancılı bir şekilde 2.2 sürümü oluyor gibi. Ancak bir dizi güvenlik düzenlemesi yaparak yığıt3.d'ye geçmeyi düşünüyorum...

Ne dersiniz?

Sürüm 3'de FIFO (ilk giren ilk çıkar) ve LIFO (son giren ilk çıkar) olayına geçmek iyi olmaz mı? Biliyorum; Firefox'un son günlerde yaptığı gibi (herhalde dikkat çekmek için?) sık sık sürüm değiştiriyorum. Öyle ki Linux dünyasında gelenekselleşen bol noktalı ve çok adetli sürüm numaralarına uymuyorum. Ama sonuçta bu basit bir sınıf/yapı öyleyse, gelin birlikte gidelim 7.7'ye...:)

Peki; aç gözlülüğün sınırlarında kalmak kaydıyla...:)

Başka neler ekleyebiliriz? Örneğin yığıtın büyüklüğünü öğrenmek iyi olabilir ki bu basit bir şey. Ama şu FIFO ve LIFO olayını, kurucu işlev tarafından alınacak bir parametre ile yapabilsek bile tek sınıfta zor olsa gerek. Sizce nasıl yapalım? İki farklı sınıf mı? Yoksa tek sınıf içinde bolca düzenlemeye giderek mi?

Teşekkürler...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #17
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ı
Bu yaptıkların harika şeyler ve görüldüğü gibi çok şey öğreniyorsun. :) Umarım "feature creep"in zararlarını da yaşayarak görürsün. ;) (Feature creep, olanakların zamanla yavaş yavaş artması ve türün gittikçe karmaşıklaşmasıdır.)

Stack veri yapısı yeni elemanın üste yerleştirildiği ve eleman erişiminin yalnızca o elemanla yapıldığı bir veri yapısıdır. (Bu arada, stack zaten LIFO'dur ve yapılması gereken de odur.)

Bu tanıma göre C gibi bir dilde yalnızca push() ve pop() olarak yapılabilir. Ama C++ ve D gibi hata düzeneği olan dillerde pop() tehlikelidir. (Bunu daha önce konuşmuştuk.) O yüzden pop()'un yan etkisiz olması gerektiği için bir de top() işlevi gerekir.

Ek olarak, yığıtta eleman bulunup bulunmadığını anlamak için empty() de mantıklı çünkü o yoksa C'deki pop()'ın veya diğerlerindeki top()'ın özel bir değer kullanmaları gerekir. Örneğin elemanların dinamik olmaları şart koşulur ve top() null döndürdüğünde boş anlamına gelebilir. Hoş değil. O yüzden empty() iyidir.

Aslında length() bile şart değildir ama o da başka veri yapılarında var diye eklenebilir. Ancak, C++'a TR1 ile sonradan eklenen tek bağlı listesi forward_list size() içermez! Listenin büyüklüğü böylece küçüldüğünden forward_list hash table uygulamalarında kullanılmaya aday küçük bir veri yapısı haline gelir (daha doğrusu, küçüklüğünü korumuş olur). Bir de uzunluğu olsaydı hash table'ın her gözünün büyüklüğü bir de size_t kadar artardı.

İşte o yüzden length() bile yığıt için seçime bağlı olmalıdır. Bunun nedenlerinden birisi, isteyenlerin (veya senin) o olanağı basitçe ekleyebilmendir:

import std.stdio;
 
class Yığıt
{
    void foo()
    {
        writeln("foo");
    }
 
    // ... Yalnızca gerçekten gereken işlevler: push(), top(), pop(), empty()
}
 
class UzunlukluYığıt
{
    size_t uzunluk;
    Yığıt asılYığıt;
 
    this()
    {
        asılYığıt = new Yığıt();
    }
 
    alias asılYığıt this;
 
    // ... @property olarak length()
}
 
void main()
{
    auto y = new UzunlukluYığıt();
    y.foo();
}

Böylece yalnızca Yığıt'ın işlevselliğini isteyenler küçük bir tür kullanmış olurlar. Özellikle uzunluk da isteyenler UzunlukluYığıt kullanırlar.

Arayüzleri olabildiğince küçük tutmanın daha yararlı olduğunu göreceksin. :)

Ali
acehreli (Moderatör) #18
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ı
Ha ha! Tabii ki verdiğim örnek yanlış! :) alias this kullanırsak her pop() ve push() çağrısında uzunluk'u değiştiremeyiz.

Aslında C++'ın std::stack'inin de size()'ı olduğuna göre Yığıt'ta da length() olabilir. Ben yalnızca arayüzün küçük de yapılabileceğini göstermek istedim.

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

Sanırım bunu düşünmüştüm. Her ne kadar üretilen object-code olarak çok şey değişmese de bu şekilde miras alma gibi olanaklar kodun kullanımını ve okunmasını sadeleştiriyor. Böylece büyüğen kodun "feature creep" durumuna düşmesi engelleniyor. Ancak ne yaparsak yapalım, sanki "feature creep" olayından uzaklaşamıyoruz. Atomu bile parçalarken karşılaştığımız indirgenemez karmaşıklık hayret vericiyken, elektronlardan oluşan kodlarımızı OOP ile dizgilenmeye çalışıyoruz.

Bu vesileyle herkese tekrar teşekkür etmeliyim...

Çünkü bu foruma üye olduğumdan itibaren OOP hakkında daha çok şey öğrenmeye başladım. Kendime Java'yı seçmiştim ve hatta kolay diye C#'a yönelmiştim. Sonra baktım D'de hazine D.amarı varmış ve kazmamıza bile gerek yokmuş; Ali Çehreli bunu bizim için yapmış...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #20
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yeni bir sürüm ile karşınızdayım!

Tataaaa...:)

module sdb.ikibinoniki.stacks;
 
/****************************************************/
  class Stack(T) {
/****************************************************/
    int index;
    T[] stack;
                              /* #1: */
    void push (T data) @property {
        stack ~= data;
        this.index++;
    }
                              /* #2: */ 
    T pop () @property {
        return stack[--this.index];
    }
                              /* #3: */
    int size () @property {
        return this.index;
    }
                              /* #4: */
    bool empty () const @property {
        return this.index == 0;
    }
}
unittest { /* Class Stack Tests */
    auto myStack = new Stack!int;
    int sum, i = 11;
 
    foreach(data; 0..i) {
        myStack.push(data);     // #1.
    }
    assert (i == myStack.size); // #3.
 
    while(!myStack.empty()) {   // #4.
        sum += myStack.pop();   // #2.
    }
    assert (sum == 55);
 
    assert (myStack.size == 0);
}
 
debug void main() {
/* Compile parameters:
 * dmd sdb/ikibinoniki/stacks.d -debug -unittest
 */
}
Evet, görüldüğü gibi gelişeceğine kırpılmış bir sürümü ile karşılaştınız...:)

Dış görünüş aldatıcı çünkü bu sadece modülün bir parçası. Bu hale dönüşmesine, ne zamandır düşündüğüm derleme çalışması sebep oldu. Baktım; yığıtlar ile ilgili birbirine benzer çok şey yapmışım. Öyleyse, pekala temel bir sınıftan bunları türetebilirdik. Örneğin şurada değindiğim yığıt, artık yukarıdaki modülden türemiş olarak şu şekilde kullanılabilir:
import sdb.ikibinoniki.stacks;
 
/****************************************************/
  class BoolStack(T) : Stack!T {
/****************************************************/
  public:
/***********/
    immutable length_t = (T.sizeof * 8);
 
    this (size_t size) {
        size_t lenOverflow = size % length_t ? 1 : 0;
        super.stack = new T[(size / length_t) + lenOverflow];
    }
                              /* #b1: */
    void clear () @property {
        foreach(ref cell; stack) {
            cell = 0;
        }
        super.index = 0;
    }
                              /* #b2: */
    auto length () const @property {
        return (stack.length * T.sizeof) + index.sizeof;
    }
 
  private
/***********/
    bool bitTest (size_t bit) {
        T xCell = stack[bit / length_t];
        T xMask = cast(T)1 << bit % length_t;
 
        return (xCell & xMask) != 0;
    }
 
  override:
/***********/
                              /* #b3: */
    void push (T data) @property {
        immutable index = super.index / length_t;
        immutable xMask = super.index % length_t;
         
        if(index >= stack.length) {
            throw new Exception("Stack is full!");
        }
        stack[index] |= data << xMask;
        super.index++;
    }
                              /* #b4: */
    T pop () @property {
        if(!super.index) {
            throw new Exception("Stack is empty!");
        }
        return cast(T)bitTest(--super.index);
    }
                              /* #b5: */
    string toString () @property { 
        string result = "[";
        foreach(i; 0..super.index) {
            result ~= bitTest(i) ? "1" : "0";
        }
        return result ~ "]";     
    }
}
 
unittest { /* Class BoolStack Tests */
    auto data = [ false, true, false, false, true, false, true, true,
                  true ]; //<-- 2/1 byte ---------------------------^
    auto test = new BoolStack!ubyte(data.length);
    // 4(int) + 2(ubyte) = 6
    assert (test.length == 6 ); // #b2.
 
    assert (test.empty);        // #s4.
 
    test.push (false);
    assert (!test.empty);
 
    test.push (true);
    assert (test.size == 2);    // #s3.
 
    test.clear;                 // #b1.
    assert (test.empty);
    
    foreach(d; data) {
        test.push(d);           // #b3.
    }
    assert (!test.empty);
 
    assert (test.toString ==
           "[010010111]");      // #b5.
 
    foreach_reverse(d; data) {
        assert (d == test.pop); // #b4.
    }
    assert (test.empty);
}
Bir de bu temelden, yeni bir sınıf (örn. RangeStack) türetilip iki aralık işlevi de (popFront(), front() işlevleri) eklenirse, görünürde çok karışmayan/şişmeyen ama aralıklarla da kullanılabilen yeni bir sınıfımız olabilir.

Kolay gelsin...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Bu mesaj 4 defa değişti; son değiştiren: Salih Dinçer; zaman: 2013-01-04, 15:36.
Değişiklik nedeni: Unutulmuş olan bir iki nokta ve lenOverflow değişkeni eklendi...
Avatar
Salih Dinçer #21
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Merhaba,

Aradan geçen yaklaşık 1 senenin ardından, çok sevdiğim başlığıma (belki küçük bir proje) geri dönüş yaptım...:)

Buna sebep; her ne kadar yığıt yapıları, çok çeşitlendirmeye/yeni özellikler eklemeye müsait olsa da işler zamanla karışacağından tıpkı yukarıdaki son iletim gibi miras alma ve belki arayüz(interface) oluşturma gerekliliği doğurabilir. Çünkü Ali hocam çok tehlikeli bir şeyden bahsetmişti:

Feature Creep

Ali hocam geçenlerde, benim değinmem üzerine yine başka bir şeyden daha bahsetti:
acehreli on 2013-11-17, 08:38:
Klasik veri yapılarının hepsinin olması şart. D'de standart kabul edilebilecek benim bildiğim iki seçenek var:

  http://dlang.org/phobos/std_container.html

  https://github.com/schveiguy/dcollections

Ancak, ikisi de modern Phobos'a uymuyorlar. Yeni bir topluluk modülü gelecek ama onun olabilmesi için öncelikle şu anda taslak aşamasında bulunan std.allocator modülünün tamamlanması gerekiyor.
Taslak yapıdaki konuya uzak olduğum için, tam olarak 'modern Phobos'dan kastın neydi tam bilmiyorum; ama ben, kendi uygulamalarım için, foreach() içinde ve pratik bir şekilde kullanabilmek benim için yeterince modern görünüyor. O yüzden geliştirmelerimi bu bağlamda devam etmek istiyorum...

Az önce, yazılanları hızlıca okuma (read over) fırsatım oldu. Yığıt içine FIFO'yu yedirme çabam olduğunu ama bunu unuttuğumu fark ettim. Acaba işleri çok karıştırmadan LIFO ile FIFO ortak bir paydada birleştirilebilir mi?

Tamam, belki yığıt olmaktan çıkacak ama top() dahil belki bizi bir çok şeyden kurtaracak! Adeta dizinin başı ve sonu üzerinde cirit atmamızı sağlayabilir...:)

Bugün küçük bir deneme yapmayı düşünüyorum...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #22
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Aşağıdaki gibi basit bir şey kodladım. Yığıt, 2 özelliği barındırdığı için fazladan rewind() işlevine ihtiyaç duydum ve bir nevi Flip/Flop gibi çalışıyor. Yani LIFO durumundayken FIFO'ya geçirebilirsiniz veya tersi...:)
  import std.stdio;
 
  class Yığıt(T) {
    int index;
    T[] stack;
 
    alias back = front;
      
    this(T[] data) {
      this.stack = data;
      rewind();
    }
    
    @property:
 
    void push(T data) {
      this.stack ~= data;
    }
    
    void rewind() { // LIFO <> FIFO
      if(index < 0) {
        index = 0;
      } else {
        index = cast(int)stack.length - 1;
      }
    }
    
    bool empty()  {
      auto FIFO = (index == stack.length);
      auto LIFO = (index < 0);
      
      return FIFO || LIFO;
    }
    
    T front() const{ // LIFO
      return stack[index];
    }
 
    void popFront() {    --index;       }
      
    void popBack()  {    ++index;       }
  }
 
void main() {
  int[] numbers = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ];
  auto test = new Yığıt!int(numbers);
 
  test.push(13)// yeni bir değer gönderiliyor ama (!)
  test.rewind()// popFront() bize öncesini verebilirdi...
    
  foreach(t; test) {  // LIFO
    t.write(",");
  }
  putchar(8);" ".writeln(); // sondaki fazla virgülü siler...
 
  test.rewind(); // FIFO'ya boş aralık dönmemesi için!
  
  foreach_reverse(t; test) { // FIFO
    t.write(",");
  }
  putchar(8);" ".writeln(); // sondaki fazla virgülü siler...
}/*Çıktısı:
13,12,11,10,9,8,7,6,5,4,3,2,1 
1,2,3,4,5,6,7,8,9,10,11,12,13 
*/
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #23
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 #21
Salih Dinçer:
Taslak yapıdaki konuya uzak olduğum için, tam olarak 'modern Phobos'dan kastın neydi tam bilmiyorum;

Bazı modüllerin başında da yazıyorlar: "Warning: This module is considered out-dated and not up to Phobos' current standards. It will remain until we have a suitable replacement, but be aware that it will not remain long term."

  http://dlang.org/phobos/std_xml.html

Ben en çok "Phobos'un diğer modülleriyle pek uyumlu olmamak" diye anlıyorum. Örneğin, aralık arayüzü sunmuyorsa std.algorithm ve std.range ile kullanılamaz.

std.allocator'ın taslağı ile ilgili bağlantılar ve tartışması şurada:

  http://forum.dlang.org/thread/l4btsk$5u8$1@digitalmars.com

Adeta dizinin başı ve sonu üzerinde cirit atmamızı sağlayabilir...:)

Belki de double-ended queue'ya dönüşecektir. :) C++'taki std::deque topluluğu gibi...

Ali
Avatar
Salih Dinçer #24
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
acehreli:
Belki de double-ended queue'ya dönüşecektir. :) C++'taki std::deque topluluğu gibi...
Çok kapsamlı bir taşıyıcı (container) imiş: http://www.cplusplus.com/reference/deque/deque/

Bugün çift yönlü bu yığıtı kullanırken bir kaç eksikliğini tespit ettim. Bahsettiğin olacak gibi görünüyor ama işe bak ben karışmasın istiyorum. Demek ki bir şey ek nitelikler verdikçe karmaşıklaşmasından kaçamıyoruz...:)

Sevgiler, saygılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #25
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ı
Ben yanlış anlamışım: deque, iki ucundaki elemanlara eriştirir. (Aslında, doğal bir BidirectionalRange.) Seninki bütünüyle doğasını değiştiriyormuş.

Sondaki fazla virgülü silme işi de hep belalı oluyor. Ben artık onun gibi alt düzey sorunlarla uğraşmak zorunda kaldığımda hep üst düzey bir çözümü unutmuş olacağımı düşünmeye başladım. Örneğin, o for döngüleriyle aslında şunu söylemek istiyoruz: Aralarında virgülle yazdır. main'in sonu şöyle değiştirilebilir:
import std.range;
// ...
    writefln("%(%s,%)", test);
    test.rewind();
    writefln("%(%s,%)", test.retro);
%( düzen belirteçleri sona ayraç yazmayacak kadar akıllılar. Ama retro'nun işleyebilmesi için Yığıt'ın bir BidirectionalRange'e dönüştürülmesi gerekiyor.

Onun için save() üye işlevinin eklenmesi gerekir:
    Yığıt save()
    {
        Yığıt kopya = this;
        return kopya;
    }
Fazla virgülü eklemeyen başka bir işlev de std.algorithm.joiner:
import std.stdio;
import std.algorithm;
 
void main()
{
    writeln([ "bir", "iki" ].joiner(","));    // bir,iki yazar
}
Ama o çözümde ayraçla elemanların aynı türden olmaları gerekiyor ("," de string elemanlar da).

Ali
Avatar
Salih Dinçer #26
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Bu çözümlerden, en azından gruplama düzen belirteçini biliyorum ki bununla ilgili bir başlık açmıştın. Ama char(8) karakterini konsol uygulamaları için çok seviyorum; yazılıma neredeyse hiç bir yük getirmiyor. Bazense foreach()'in index'ini bir if() ile kontrol ederek bunu sağlayabiliyorum.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Bu mesaj Salih Dinçer tarafından değiştirildi; zaman: 2013-12-05, 11:40.
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:
Sayfa:  önceki  1  2 
Forum: Duyurular 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, 00:44:34 (UTC -08:00)