http://ddili.org/ders/d/object.html

Ali

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

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:

Alıntı:

Ali

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

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 (http://ddili.org/forum/thread/1007) 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...

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

Alıntı (acehreli):

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_hashing.aspx

Ali

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

İ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:

Alıntı (acehreli):

>     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;
}

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

Alıntı (Salih Dinçer):

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

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

Alıntı (Salih Dinçer):

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

Ali

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

Alıntı (acehreli:1352161575):

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 (http://ddili.org/forum/thread/995) 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 (http://tr.wikipedia.org/wiki/Belirsizlik_ilkesi) 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...

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