Forum: Duyurular RSS
Yeni ders: Object
acehreli (Moderatör) #1
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ı
Konu adı: Yeni ders: Object
  http://ddili.org/ders/d/object.html

Ali
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ı
Birisi bana mesaj atarak o dersteki toHash işlevlerinden bazılarının hatalı olduğunu söyledi:
class Saat
{
    int saat;
    int dakika;
    int saniye;
 
    override size_t toHash() const
    {
        return saat + dakika + saniye;
    }
 
    // ...
}
Yukarıdaki işlev şu nesnelerin ikisi için aynı hash değerini üretir:
auto s1 = new Saat(12, 30, 15);
auto s2 = new Saat(12, 15, 30);
toHash'in onlar için farklı değer üretmesi için şöyle bir işlev daha doğru olabilir:
    override size_t toHash() const
    {
        return saat + 60 * dakika + 3600 * saniye;
    }
Ama aslında benim yazdığım da hataya neden olmaz çünkü hash table hash değeri çakışmalarına hazırlıklıdır. Hash değerini hemen indeks olarak kullanmaz; o haneye rastlayan bütün nesneleri ayrıca opEquals (ve belki de opCmp) ile de karşılaştırır. Zaten o yüzden şu uyarı tekrarlanıyor:

Uyarı: Yalnızca bu işlevi tanımlamak yetmez. Bu işlevin eşleme tablolarında doğru olarak kullanılabilmesi için opEquals ve opCmp işlevlerinin de birbirleriyle tutarlı olarak tanımlanmış olmaları gerekir.

Ali
acehreli (Moderatör) #3
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ı
acehreli:
aslında benim yazdığım da hataya neden olmaz

Evet, hataya neden olmuyor ama farklı saat değerleri için aynı indeks değeri üretildiği için fazla sayıda çakışma (hash collision) oluyor.

Sayaçlar kullanarak şu programla denedim:
import std.stdio;
import std.random;
 
class Saat
{
    int saat;
    int dakika;
    int saniye;
 
    static {
        size_t opCmpToplamı = 0;
        size_t opEqualsToplamı = 0;
        size_t toHashToplamı = 0;
    }
 
    this(int saat, int dakika, int saniye)
    {
        this.saat = saat;
        this.dakika = dakika;
        this.saniye = saniye;
    }
 
    override bool opEquals(Object o) const
    {
        ++opEqualsToplamı;
 
        const sağdaki = cast(const Saat)o;
 
        return (sağdaki &&
                (saat == sağdaki.saat) &&
                (dakika == sağdaki.dakika) &&
                (saniye == sağdaki.saniye));
    }
 
    override int opCmp(Object o) const
    {
        ++opCmpToplamı;
 
        if (typeid(this) != typeid(o)) {
            return typeid(this).opCmp(typeid(o));
        }
 
        const sağdaki = cast(const Saat)o;
 
        if (saat != sağdaki.saat) {
            return saat - sağdaki.saat;
 
        } else if (dakika != sağdaki.dakika) {
            return dakika - sağdaki.dakika;
 
        } else {
            return saniye - sağdaki.saniye;
        }
    }
 
    override size_t toHash() const
    {
        ++toHashToplamı;
 
        return saat + dakika + saniye;
    }
 
    static void sayaçlarıYazdır()
    {
        writefln("opEquals: %8s", opEqualsToplamı);
        writefln("opCmp   : %8s", opCmpToplamı);
        writefln("toHash  : %8s", toHashToplamı);
    }
}
 
Saat rasgeleSaat()
{
    return new Saat(uniform(0, 24), uniform(0, 60), uniform(0, 60));
}
 
void main()
{
    enum adet = 10_000;
    int[Saat] tablo;
 
    /* Rasgele anahtar değerleriyle doldur. */
    foreach (i; 0 .. adet) {
        auto saat = rasgeleSaat();
        tablo[saat] = 0;    /* değerin önemi yok; öylesine 0 kullanıyorum */
    }
 
    /* Rasgele anahtar değerlerini ara. */
    foreach (i; 0 .. adet) {
        auto sonuç = (rasgeleSaat() in tablo);
    }
 
    Saat.sayaçlarıYazdır();
}
Çıktısı şöyle:

opEquals:        0
opCmp   :  1463529    <-- çakışmaların göstergesi
toHash  :    20000


Gözlem: dmd çakışma durumlarınd opEquals'ı değil, opCmp'ı kullanıyor. (Yani, soldaki == sağdaki yapmıyor da, demek ki soldaki.opCmp(sağdaki) == 0 yapıyor.) Başka derleyiciler başka davranabilir.

Şimdi toHash işlevindeki hesabı şöyle değiştiriyorum:
        return saat + 60 * dakika + 3600 * saniye;
Çakışmalar çok azalıyor ve sonuçta program çok hızlanıyor:

opEquals:        0
opCmp   :     1659
toHash  :    20000


Hash değerlerini hesaplamak için çok algoritma var. Şu İngilizce sayfa hoşuma gitti. Bu işin 33 ve 16777619 gibi sihirli sabitlere dayalı olabildiğini gösteriyor: :)

  http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_has…

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

Makale çok güzelmiş. Ben de genelde makalede yer alan 'Rotating hash'ı kullanıyordum çünkü basit oluyor. Hemen yukarısında bir XOR hash var. Belki foruma şöyle bir soru sorabiliriz:

Siz de özelleşmiş (size özel) bir  'hash function'u yazmış olsaydınız nasıl olurdu?

Hatırlarsanız Şifreli Metin başlığında bunu amaçlamıştım. Yani her yiğidin yoğurt yemesinin farklı oluşundan yola çıkarak meydana gelecek renk yelpazesini çık merak ediyorum. Henüz bu konuda çok katılımlı  bir şey yapamadık. Yapsak ya...:)

Sevgiler, saygılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #5
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:
Siz de özelleşmiş (size özel) bir  'hash function'u yazmış olsaydınız nasıl olurdu?

Hatırlarsanız Şifreli Metin başlığında bunu amaçlamıştım. Yani her yiğidin yoğurt yemesinin farklı oluşundan yola çıkarak meydana gelecek renk yelpazesini çık merak ediyorum. Henüz bu konuda çok katılımlı  bir şey yapamadık. Yapsak ya...:)

Bu ilgiyle ilgili! :-p Kendi adıma, hash veya şifreleme konuları ne kadar ilginç olsalar da bana yukarıdaki gibi makaleleri okumak yetiyor. Her iki konuda da dikkate değer sonuç almak günler sürecek gibi geliyor. Yine hash iyi çünkü onun performansını belirli bir veri türü için basit bir test programı ile ölçebiliriz.

Ama şifreleme konusu ya tam büyü, ya tam sonuna kadar matematik. Ya iyi bir algoritma bulduk diye seviniriz ama şifreleme uzmanları güler geçerler, ya da matematik ile kanıtlamadan zaten kendimiz bile iyi algoritmamıza güvenmemeliyizdir.

Belki ileride kafayı takarım ama sanmıyorum da. :)

Ali
Avatar
Salih Dinçer #6
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
İlgi önemli ama bence mükemmellik değil...:D

Yani algoritmanın benzerleri arasında üstün veya eşdeğer olması gerekmez. Maksat beyin jimnastiği yapmak ve çözüme giden yoldaki farklılıkları görmek. Aslında cevabı biliyorum hepsi farklı olacak. Yine de aklın yolu birdir hesabından yola çıkarsak yaptıklarımız birbirlerine çok benzeyebilir... :rolleyes:

Tıpkı, "üçlü zaman değeri (saat, dakika, saniye) için üretebileceğimiz en basit 'hash function'u nedir?" dediğimizde 'system tick' gibi bir şey hesaplamak:

acehreli:
toHash'in onlar için farklı değer üretmesi için şöyle bir işlev daha doğru olabilir:
    override size_t toHash() const
    {
        return saat + 60 * dakika + 3600 * saniye;
    }
Sanırım yukarıda küçük bir hata var. Aslında matematiğim çok kuvvetli sayılmaz ve belki yapılmak istenen farklı bir şey. Ama şimdi tekrar baktığımda sanki saat ve dakikayı saniyeye çevirmemiz hoş ve işlevsel olabilir:
    override size_t toHash() const
    {
        return saat * 3600 + dakika * 60 + saniye;
    }
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #7
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:
Sanırım yukarıda küçük bir hata var.

Haklısın! :) Hata üstüne hata yapıyorum. Evet, fikir o. Neyse ki performansı etkileyen bir hata olmamış.

Ali
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 #3
acehreli on 2012-11-05, 16:26:
Hash değerlerini hesaplamak için çok algoritma var. Şu İngilizce sayfa hoşuma gitti. Bu işin 33 ve 16777619 gibi sihirli sabitlere dayalı olabildiğini gösteriyor: :)

  http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_has…
Bu mavi zemin rengi olan sayfaya özel önem veriyorum ve bulmak için forumumuzu kullandım. Hash (Türkçesi ne olabilir?) işlevlerine değer katmak için, izninizle şu başlığı da eklemek istiyorum:

http://www.azillionmonkeys.com/qed/hash.html

Ayrıca bu konularda Ekim ayında (an itibariyle geçen ay!) basit bir uygulama geliştirmiştim. Çok çok büyük bir dosyayı hızlı şekilde (ama şüpheli olabilir!) MD5'lemek için başındaki küçük bir bölüme bakıp bu şekilde tüm dosyalarda devam etmesi (dosya parametresi ile gösterilen dizindeki tüm dosyaları taraması) mümkün. Bunu neden veriyorum; çünkü yukarıda değer katmak için verdiğim sitede de bir kodun hız analizleri yapılmış. Eminim bu bilgiler sık sık işimize yarayacaktır.

Belki tartışma yapmak isterseniz:

Ömrümüzün yetmesi (bu teknolojiyi görmemiz) küçük ihtimal olsa da Kuvantum Bilgisayarlar'ı laboratuvardan çıkıp masaüstlerimize gelirse verileri böyle tarayıp doğrulamak gerekmeyecek...:)

Çünkü verilerde bir bozulma meydana geldiğinde veya birileri bunlara erişip okumaya kalktığında biz bunu bileceğiz. Garip şeyler biliyorum ama Belirsizlik İlkesi ile alakalı. Her ne kadar son gelişmelerde bunları aştığımız söylense de elektronun konumunu öğrenmeye kalktığımızda bilgi belirsiz oluyor. Çünkü yönünü değiştirmiş olabiliyoruz. Aynı şekilde hızını tespit etmek istersek ölçülen değeri yanlış çıkaracak biçimde etkimiz oluyor.

Özetle, şimdi bu belirsizlikleri aşıp etkin ve kullanılabilir yöntemler geliştirmeye çalışıyoruz. Gelecekteki bilişim (IT) çok farklı olabilir...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
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: 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-21, 15:17:11 (UTC -08:00)