Genel sınıflar kütüphanesi - hatalar, açıklamalar, sorular, kullanım özellikleri ve öneriler - sayfa 10

Yeni yorum
 

Hash fonksiyonları hakkında

Önceki örneklerden, hash fonksiyonunun yükün büyük kısmını üstlendiği açıkça görülmektedir. Karma işlevi olabildiğince hızlı yapılabilir, ancak büyük olasılıkla bu durumda çarpışmalara oldukça açık olacaktır. Tersine, bir karma işlevi mümkün olduğunca çarpışmalara karşı dirençli hale getirilebilir, ancak hesaplama karmaşıklığı gerçekleştirilen görev için yetersiz olacaktır. İki uç örneğe bakalım. Örnek 1, en hızlı hash fonksiyonu:

 int GetHashCode( string word)
{
   return 0 ;
}

Her zaman aynı numarayı döndürür. Sözlüğümüz sadece bir kelimeyi saklayacaksa, çalışması yeterli olacaktır, çünkü bu kelime indeks 0'da olacaktır. Ancak, eğer 10 kelime varsa, o zaman on kelimenin tümü sıfır indeksinde olacaktır (bir dizi dizimiz olduğunu unutmayın).

İkinci örnek için, örneğin N turlu bir Feistel ağına dayalı olarak tersine çevrilebilir şifrelemeye dönelim.Bu bir karma işlevi değildir ve çarpışmalara tabi değildir. Onlar. iki farklı dizi için garantili farklı sayılar elde ederiz. Ortaya çıkan sayıların uzunluğu, dizenin uzunluğuna eşit olacaktır. Bu nedenle, 1000 karakter uzunluğunda bir dize için 1000 boyutunda bir uchar dizisi alacağız. Bu dizeyi 3 öğe boyutunda bir sözlükte saklamamız gerekirse, bunun garip olduğunu kabul edeceksiniz. sadece üç elemanlı bir kelime aramak için böyle karmaşık bir kodu hesaplamak.

Bu nedenle, her zaman bir orta yol aramalıyız (fxsaber'ın haklı olarak işaret ettiği gibi): hash'i hızlı bir şekilde hesaplayacak ve kural olarak çarpışma vermeyecek bir fonksiyona ihtiyacımız var. Önceki hash fonksiyonumuzun çarpışma olasılığını tahmin edelim:

 int GetHashCode( string word)
{
   int index = StringGetCharacter (word, 0 )- 'a' ;
}

Alfabede 26 karakter vardır. 'a' karakteriyle başlayan kelimelerin sayısının, herhangi bir başka karakterle başlayan kelimelerin sayısına eşit olduğunu varsayacağız. O zaman sözlüğümüzde 988 kelime varsa, bunlardan 38'i a harfiyle, 38'i - b harfiyle, 38 - c harfiyle, ... 38 - w harfiyle ve 38'i harfiyle başlayacak - z . Her durumda çarpışma olasılığı 1/26 veya %3,8461 olacaktır. 988 kelimemiz varsa, indeks başına 988*3.8461 = 37.999 kelime elde ederiz.

Aynı harf için ne kadar çok kelime olursa, belirli bir kelimeyi bulmanın o kadar zor olduğu açıktır. Bizim durumumuzda, sadece ilk harfin indeksini hesaplamak değil, aynı zamanda kelimeleri tam olarak karşılaştırmak için aynı harfle başlayan tüm kelimeleri sıralamak gerekecektir. Her ne ise, hash fonksiyonunu karmaşık hale getirebiliriz:

 int GetHashCode( string word)
{
   uchar i1 = ( uchar )word[ 0 ]- 'a' ;
   uchar i2 = ( uchar )word[ 1 ]- 'a' ;
   int hash = i1<<( sizeof ( uchar )* 8 );
   hash += i2;
   return hash;
}

Onlar. zaten bir kelimenin ilk iki karakterini alıyoruz. O zaman 26 olası kombinasyon olmayacak, ancak 26^2 = 676 olacak. Karma işlevinin hesaplanmasının ikinci varyantının karmaşıklığının doğrusal olarak, kabaca iki kez arttığını, çarpışmalara karşı direncinin doğrusal olmayan bir şekilde arttığını not ediyorum, kare.

İkinci seçenek için ortalama olarak her 676 kelime için bir çarpışma olacaktır. Bizim durumumuzda 988 kelime için indeks başına 988/676 = 1.4615 çarpışma olacaktır. Onlar. her dizin ortalama olarak bir kelime veya 2 kelime içerecektir. Onlar. ortalama olarak, hiç arama yapılmayacaktır (bir karşılaştırma) veya çok kısa olacaktır (iki karşılaştırma).

Sözlük boyutunun karma işlev kombinasyonlarına oranı 1.0000000 eğilimindeyse, ortalama olarak numaralandırmaya gerek yoktur, çünkü her öğe yalnızca kendi dizininde yer alacaktır. Eğer hash fonksiyonu çok geniş bir değer aralığı üretecekse, o zaman sözlüğün boyutunun hash fonksiyonunun olası kombinasyonlarına oranı her zaman 1.0'dan bile az olacaktır. Örneğin, karma işlevi 2^32 kombinasyon üretecekse, 2^32'den küçük herhangi bir N boyutu için N/2^32 < 1.0 oranı karşılanacaktır. N çok küçükse, özet fonksiyonu tarafından elde edilen sayıyı her zaman N limitinde olacak şekilde normalleştiririz: 

int index = GetHashCode(word)% ArraySize (m_array);

Karma işlevi tek tip sonuçlar veriyorsa, ortalama olarak 1.000 oranını elde ederiz. onlar. dizi indeksi başına sadece bir kelime olacaktır. Bu nedenle, bir sözlüğün, bir dizin yerine bir anahtarın belirtildiği bir dizinin özel bir durumu olduğunu söyleyebiliriz.

 
Peter Konow'un fotoğrafı.

Bir dizinin boyutu, bir sözlüğün boyutuna uyacak şekilde kolayca değiştirilebilir.

Sonsuz seçenekler dikkate alınmaz.

İşin aslı, bir sözlüğün boyutunun çoğu zaman bilinmemesidir. Basit bir örnek, diyelim ki bir Uzman Danışmanımız var. Tamamlanan işlemlerin kaydını tutar. Anlaşmanın tarihe geçmesinden sonra, bu anlaşmayı, diyelim ki uzmanın büyüsüyle ilişkilendirmek gerekiyor. Bunu yapmak için bir sözlük kullanmak mantıklıdır. İşlem numarasının anahtar (benzersiz tanımlayıcı) olarak kullanıldığı ve uzmanın sihirli numarasının değer olarak kullanıldığı durumlarda. Sorun şu ki, bir danışman başlatırken, 100 işlemimiz mi yoksa 1000 işlemimiz mi olacağını önceden belirlemek imkansız. Önceden ne kadar bellek ayırırsanız ayırın, yine de ya çok az ya da çok fazla olacaktır.

 
Vasili Sokolov :

İşin aslı, bir sözlüğün boyutunun çoğu zaman bilinmemesidir. Basit bir örnek, diyelim ki bir Uzman Danışmanımız var. Tamamlanan işlemlerin kaydını tutar. Anlaşmanın tarihe geçmesinden sonra, bu anlaşmayı, diyelim ki uzmanın büyüsüyle ilişkilendirmek gerekiyor. Bunu yapmak için bir sözlük kullanmak mantıklıdır. İşlem numarasının anahtar (benzersiz tanımlayıcı) olarak kullanıldığı ve uzmanın sihirli numarasının değer olarak kullanıldığı durumlarda. Sorun şu ki, bir danışman başlatırken, 100 işlemimiz mi yoksa 1000 işlemimiz mi olacağını önceden belirlemek imkansız. Önceden ne kadar bellek ayırırsanız ayırın, yine de ya çok az ya da çok fazla olacaktır.

Eh, görevlerin farklı olduğu açıktır.

Bir insan dili için uygun bir sözlük oluşturmanın gerekli olduğu bir sorunu çözdüm. Dizimin boyutu kesin değil, ancak onu belirli bir dildeki sözcük sayısına uydurmanın sorunu nedir? Oraya kolayca sığar.

Örneğin, Rusça. Diyelim ki 10.000 temel kelime içeriyor. Tüm bu kelimeler dizime mükemmel bir şekilde yerleştirilebilir.

İlk boyut 66 harftir (küçük ve büyük), ikinci boyut bir kelimedeki harf sayısıdır (örneğin 25'e kadar), üçüncü boyut ilk harf ve harf sayısı - 50 için eşleşmelerdir.

Bütün dil sığacak.

//------------------------------------

Başlangıçta, tam olarak bu sorunu çözdüm. Şimdi asıl sorunu bir başkasıyla değiştiriyorsunuz ve çözümün iyi olmadığını söylüyorsunuz.

 
Vasili Sokolov :

Önceden ne kadar bellek ayırırsanız ayırın, yine de ya çok az ya da çok fazla olacaktır.

Doğru.

Tüm problemler için evrensel bir çözüm olmadığı da doğrudur.

 
Peter Konow'un fotoğrafı.

Doğru.

Tüm problemler için evrensel bir çözüm olmadığı da doğrudur.

Kesinlikle inkar edilemez.

 
Sergey Dzyublik :

Sessiz yoldaş. Hiç kimse hatalardan bağışık değildir, sen bile. Bu nedenle, nazik olun, başkalarının hatalarını daha yumuşak bir tonda belirtin. Şimdi düzelteceğim.

 
Alexey Viktorov :

Ve doğru seçenek bir sır olarak kalacak ???


Prensip olarak, hash tablolarının ve hash'lerin doğru bir versiyonu olamaz - bunların hepsi belirli hedeflere ve kullanım koşullarına bağlıdır.
Sandviç yapmak gibi. Belki biri mayonez ya da ketçap yemiyor ya da vegan....
Ancak masaya ketçap serpmek ve üzerine ekmek koymak - bunun olmadığı açık görünüyor ....


Tembel için konuyla ilgili temel bilgiler:
https://www.slideshare.net/mkurnosov/6-32402313

Gerçekte, her şey çok daha karmaşıktır ve ilgili literatürde veya iyi "algoritmalar ve veri yapıları" derslerinde tartışılmaktadır.

Лекция 6: Хеш-таблицы
Лекция 6: Хеш-таблицы
  • 2014.03.17
  • Mikhail Kurnosov, Associate Professor (Docent) Follow
  • www.slideshare.net
Лекция 6 Хеш-таблицы Курносов Михаил Георгиевич к.т.н. доцент Кафедры вычислительных систем Сибирский государственный университет телекоммуникаций и информатик…
 

Kısacası, önce karma işlevi çalışmalıdır: hızlı, ikincisi - tamamen karmaşık bir şey icat etmeye gerek yoktur, çünkü aynı değerlerin görünümü normalde sözlük içinde doğrudan numaralandırma ile çözülür. Ana şey, çok sık çarpışma olmamasıdır, hepsi bu. Generic'te, HashFunction.mqh dosyasındaki bir dizi işlev, temel türlerin işlev karmasından sorumludur. Orada her şeyin basit olduğundan emin olmak için nasıl çalıştığını görelim:

 //+------------------------------------------------------------------+
//|                                                 HashFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
//+------------------------------------------------------------------+
//| Unioun BitInterpreter.                                           |
//| Usage: Provides the ability to interpret the same bit sequence in|
//|        different types.                                          |
//+------------------------------------------------------------------+
union  BitInterpreter
  {
   bool               bool_value;
   char               char_value;
   uchar             uchar_value;
   short              short_value;
   ushort             ushort_value;
   color             color_value;
   int                int_value;
   uint               uint_value;
   datetime          datetime_value;
   long               long_value;
   ulong              ulong_value;
   float              float_value;
   double             double_value;
  };
//+------------------------------------------------------------------+
//| Returns a hashcode for boolean.                                  |
//+------------------------------------------------------------------+
int GetHashCode( const bool value )
  {
   return (( value )? true : false );
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for character.                                |
//+------------------------------------------------------------------+
int GetHashCode( const char value )
  {
   return (( int ) value | (( int ) value << 16 ));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned character.                       |
//+------------------------------------------------------------------+
int GetHashCode( const uchar value )
  {
   return (( int ) value | (( int ) value << 16 ));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for short.                                    |
//+------------------------------------------------------------------+
int GetHashCode( const short value )
  {
   return ((( int )(( ushort ) value ) | ((( int ) value ) << 16 )));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned short.                           |
//+------------------------------------------------------------------+
int GetHashCode( const ushort value )
  {
   return (( int ) value );
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for color.                                    |
//+------------------------------------------------------------------+
int GetHashCode( const color value )
  {
   return (( int ) value );
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for integer.                                  |
//+------------------------------------------------------------------+
int GetHashCode( const int value )
  {
   return ( value );
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned integer.                         |
//+------------------------------------------------------------------+ 
int GetHashCode( const uint value )
  {
   return (( int ) value );
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for datetime.                                 |
//+------------------------------------------------------------------+
int GetHashCode( const datetime value )
  {
   long ticks=( long ) value ;
   return ((( int )ticks) ^ ( int )(ticks >> 32 ));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for long.                                     |
//+------------------------------------------------------------------+
int GetHashCode( const long value )
  {
   return ((( int )(( long ) value )) ^ ( int )( value >> 32 ));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned long.                            |
//+------------------------------------------------------------------+  
int GetHashCode( const ulong value )
  {
   return ((( int ) value ) ^ ( int )( value >> 32 ));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for float.                                    |
//+------------------------------------------------------------------+
int GetHashCode( const float value )
  {
   if ( value == 0 )
     {
       //--- ensure that 0 and -0 have the same hash code
       return ( 0 );
     }
   BitInterpreter convert;
   convert.float_value= value ;
   return (convert.int_value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for string.                                   |
//+------------------------------------------------------------------+
int GetHashCode( const double value )
  {
   if ( value == 0 )
     {
       //--- ensure that 0 and -0 have the same hash code
       return ( 0 );
     }
   BitInterpreter convert;
   convert.double_value= value ;
   long lvalue=convert.long_value;
   return ((( int )lvalue) ^ (( int )(lvalue >> 32 )));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for string.                                   |
//| The hashcode for a string is computed as:                        |
//|                                                                  |
//| s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]                     |
//|                                                                  |
//| using int arithmetic, where s[i] is the ith character of the     |
//| string, n is the length of the string, and ^ indicates           |
//| exponentiation. (The hash value of the empty string is zero.)    |
//+------------------------------------------------------------------+
int GetHashCode( const string value )
  {
   int len=StringLen( value );
   int hash= 0 ;
//--- check length of string
   if (len> 0 )
     {
       //--- calculate a hash as a fucntion of each char
       for ( int i= 0 ; i<len; i++)
         hash= 31 *hash+ value [i];
     }
   return (hash);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for custom object.                            |
//+------------------------------------------------------------------+
template<typename T>
int GetHashCode(T value )
  {
//--- try to convert to equality comparable object  
   IEqualityComparable<T>*equtable=dynamic_cast<IEqualityComparable<T>*>( value );
   if (equtable)
     {
       //--- calculate hash by specied method   
       return equtable.HashCode();
     }
   else
     {
       //--- calculate hash from name of object
       return GetHashCode(typename( value ));
     }
  }
//+------------------------------------------------------------------+

Tamsayı türleri ya olduğu gibi döndürülür ya da kısa tamsayı türleri için basit bit düzeyinde dönüştürme işlemleri kullanılır. 32 bit'e sığmayan türler için, sağ ve sol kısımların özel veya ardından gelen birleşimi kullanılır. Dizeler için, doğrudan numaralandırma yoluyla karmaşık olmayan bir karma da hesaplanır. Reel sayılar için birleşim yardımı ile bir bit gösterimi alınır ve zaten hash olarak kullanılır.

 

Sözlük tipi algoritmalar şartlı olarak iki kısma ayrılır:

  • Anahtarın benzersiz olduğu ve değerin olmadığı anahtar/değer çiftleri kümeleri. Genel olarak CHashMap'tir
  • Benzersiz değerler kümesi. Genel olarak, bu CHashSet'tir.

CHashSet nedir? Bu, her öğenin benzersiz olduğu bir koleksiyondur (özünde bir dizi). Örneğin, böyle bir koleksiyon 2,5,1,7,10,15,1024 sayılarını içerebilir. Ama hiçbir iki sayı aynı değildir. Ayrıca diziler, gerçek sayılar ve hatta kullanıcı tanımlı karmaşık türleri de içerebilir (daha sonra anlatacağız). Ancak herhangi bir tür için kural aynıdır - sözlükte böyle bir tane olamaz.

CHashMap nedir? Bu, her öğenin karmaşık bir anahtar/değer türü olduğu bir koleksiyondur (özünde de bir dizidir):

 template < typename TKey, typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected :
   int                m_buckets[];
   Entry<TKey,TValue>m_entries[];
   int                m_count;
   int                m_free_list;
   int                m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool               m_delete_comparer;
};

CHashMap'e çok benzer şekilde yapılandırılmıştır, ancak set öğesi 1'in set 2'ye karşılık gelmesi için iki seti eşlemenize izin verir. Bu, ortalama bir O(1) yürütme süresi ile çok verimli sorgu algoritmaları yazmanıza izin veren çok kullanışlı bir özelliktir.

Daha sonra, örnekler kullanarak bir tür yazışmanın yapısını inceleyeceğiz.

İlginç bir şekilde, herhangi bir anahtar/değer sözlüğü doğal olarak böyle önemsiz olmayan bire çok ilişki kurar. Örneğin, elimizde bir sürü tarihi emir ve bunlara dayalı olarak gerçekleştirilen bir sürü işlem var. Her anlaşma yalnızca bir siparişe karşılık gelir, ancak bir sipariş birkaç anlaşmaya karşılık gelebilir. Böyle bir ilişkinin sözlüğü, anlaşmanın numarasını bir anahtar olarak ve bir değer olarak, onu açmaya yarayan siparişin numarasını saklayabilir.
 
Lütfen konu dışı konuyu kirletmeyin.
1...34567891011121314151617...38
Yeni yorum