Bibliothèque de classes génériques - bogues, description, questions, caractéristiques d'utilisation et suggestions - page 10

Nouveau commentaire
 

À propos des fonctions de hachage

D'après les exemples précédents, il est clair que la fonction de hachage prend le gros de la charge. Une fonction de hachage peut être aussi rapide que possible, mais elle sera très probablement sujette aux collisions. Et vice versa, une fonction de hachage peut être rendue aussi résistante aux collisions que possible, mais sa complexité de calcul sera inadaptée à la tâche à accomplir. Prenons deux exemples extrêmes. Exemple 1, la fonction de hachage la plus rapide possible :

int GetHashCode(string word)
{
   return 0;
}

Il renvoie toujours le même numéro. Si notre dictionnaire ne stocke qu'un seul mot, alors son travail sera suffisant, car ce mot sera situé à l'index 0. Si nous avons 10 mots, alors les 10 mots seront à l'index 0 (n'oubliez pas que nous avons un tableau de tableaux).

Pour le second exemple, tournons-nous vers un chiffrement réversible, par exemple basé sur un réseau de Feistel avec un nombre de tours N. Il ne s'agit pas d'une fonction de hachage, et elle n'est pas du tout sujette aux collisions. C'est-à-dire que pour deux cordes différentes, nous obtiendrons des chiffres différents garantis. La longueur des chiffres obtenus sera égale à la longueur de la chaîne. Ainsi, si la chaîne de caractères compte 1000 caractères, nous obtiendrons un tableau uchar de taille 1000. Si nous devons stocker cette chaîne dans un dictionnaire à 3 éléments, ne pensez-vous pas qu'il serait étrange de calculer un code aussi complexe pour trouver un mot avec seulement trois éléments.

Par conséquent, nous devons toujours chercher un juste milieu (comme l'a souligné à juste titre fxsaber) : nous avons besoin d'une fonction qui calcule rapidement les hachages et qui n'a généralement pas de collisions. Estimons la probabilité de collisions pour notre fonction de hachage précédente :

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

Il y a 26 caractères dans l'alphabet. Supposons que le nombre de mots commençant par le symbole "a" soit égal au nombre de mots commençant par tout autre symbole. Alors si notre dictionnaire contient 988 mots, 38 d'entre eux commencent par a, 38 par b, 38 par c, ... 38 à la lettre w et 38 à la lettre - z. La probabilité qu'une collision se produise dans chaque cas serait de 1/26 ou 3,8461%. Si nous avons 988 mots, alors nous obtenons 988*3.8461 = 37.999 mots par index.

Il est clair que plus il y a de mots pour une même lettre, plus il est difficile de trouver un mot particulier. Dans notre cas, nous devons non seulement calculer l'indice de la première lettre, mais aussi rechercher tous les mots commençant également par la même lettre. Pour éviter cela, nous pouvons compliquer la fonction de hachage :

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

C'est-à-dire que nous prenons les deux premiers caractères du mot. Alors les combinaisons possibles ne seront pas 26, mais 26^2 = 676. Il convient de noter que la complexité de la deuxième variante du calcul de la fonction de hachage a augmenté linéairement, en gros deux fois, tandis que sa résistance aux collisions a augmenté non linéairement, au carré.

Pour la deuxième variante, la moyenne serait d'une collision pour 676 mots. Dans notre cas, pour 988 mots, il y aurait 988/676 = 1,4615 collisions par index. Cela signifie que chaque index contiendra en moyenne un ou deux mots. En moyenne, il n'y aura donc pas de collisions du tout (une comparaison), ou elles seront très courtes (deux comparaisons).

Si le rapport entre la taille du dictionnaire et les cobmins de la fonction de hachage est proche de 1,0000000, alors en moyenne aucune force brute ne sera nécessaire, car chaque élément sera localisé à son propre index par lui-même. Si une fonction de hachage fournit une très large gamme de valeurs, le rapport entre la taille du dictionnaire et les combinaisons possibles de la fonction de hachage sera toujours inférieur à 1,0. Par exemple, si une fonction de hachage produit 2^32 combinaisons, pour toute taille N inférieure à 2^32, le rapport N/2^32 < 1,0 sera respecté. Si N est très petit, il suffit de normaliser le nombre obtenu par la fonction de hachage, afin qu'il soit toujours dans la limite de N :

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

Si la fonction de hachage génère des résultats de manière uniforme, nous obtiendrons en moyenne un ratio de 1,000, c'est-à-dire qu'il n'y aura qu'un seul mot dans un index du tableau. On peut donc dire qu'un dictionnaire est un cas particulier de tableau avec une clé au lieu d'un index.

 
Tag Konow:

La taille du tableau peut facilement être modifiée pour correspondre à la taille du dictionnaire.

Je ne prends pas en compte les variantes infinies.

Le fait est que la taille du dictionnaire est souvent inconnue. Un exemple simple, disons que nous avons un conseiller expert qui effectue des transactions. Il permet de suivre les transactions effectuées. Une fois qu'une transaction apparaît dans l'historique, nous devons connecter cette transaction avec le Medjik de l'EA. Pour cela, il est logique d'utiliser le dictionnaire. Le numéro de transaction est utilisé comme clé (identifiant unique), et le numéro magique du conseiller expert est utilisé comme valeur. Le problème est qu'au début de l'EA, nous ne pouvons pas déterminer à l'avance si nous aurons 100 transactions, 1000 ou aucune transaction. Quelle que soit la mémoire que vous allouez à l'avance, elle sera soit trop petite, soit trop grande.

 
Vasiliy Sokolov:

C'est là le problème : la taille du dictionnaire est souvent inconnue. Un exemple simple, disons que nous avons un conseiller qui négocie. Il assure le suivi des transactions effectuées. Lorsqu'une transaction apparaît dans l'historique, nous devons connecter cette transaction avec le Medjack du conseiller expert. Pour cela, il est logique d'utiliser le dictionnaire. Le numéro de transaction est utilisé comme clé (identifiant unique), et le numéro magique du conseiller expert est utilisé comme valeur. Le problème est qu'au début de l'EA, nous ne pouvons pas déterminer à l'avance si nous aurons 100 transactions, 1000 ou aucune transaction. Quelle que soit la quantité de mémoire que vous allouez au préalable, elle sera toujours insuffisante ou excessive.

Eh bien, évidemment, il y a différentes tâches.

Je résolvais une tâche où je devais créer un dictionnaire pratique pour une langue humaine. La taille de mon tableau n'est pas exacte, mais quel est le problème de l'ajuster au nombre de mots d'une langue spécifique ? Il peut facilement y entrer.

Par exemple, une langue russe. Supposons qu'il contienne 10 000 mots de base. Tous ces mots peuvent s'inscrire dans mon tableau.

La première dimension - 66 lettres (petites et grandes), la deuxième dimension - le nombre de lettres du mot (jusqu'à 25 par exemple), la troisième dimension - correspond à la première lettre et au nombre de lettres - 50.

La langue entière s'adaptera.

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

Au départ, je résolvais exactement ce problème. Vous remplacez maintenant le problème initial par un autre et dites que la solution n'est pas bonne.

 
Vasiliy Sokolov:

Quelle que soit la quantité de mémoire que vous allouez au préalable, elle sera soit trop faible, soit trop importante.

Bien.

Tout aussi vrai qu'il n'existe pas de solution universelle pour toutes les tâches.

 
Tag Konow:

C'est vrai.

Il est également vrai qu'il n'existe pas de solution unique.

Complètement indiscutable.

 
Sergey Dzyublik:

Baisse la voix, camarade. Personne n'est à l'abri des erreurs, pas même vous. Soyez donc assez aimable pour souligner les erreurs des autres sur un ton plus doux. Je vais le corriger maintenant.

 
Alexey Viktorov:

Le bon restera-t-il un secret ?


En principe, il ne peut y avoir une variante correcte des tables de hachage et des hachages - tout dépend des objectifs spécifiques et des conditions d'application.
C'est comme faire un sandwich. Peut-être que quelqu'un ne mange pas de mayonnaise ou de ketchup, ou qu'il est un vegan.....
Mais mettre du ketchup sur la table et poser du pain dessus, c'est clair que ce n'est pas.....


Des notions de base sur le sujet pour les paresseux :
https://www.slideshare.net/mkurnosov/6-32402313

En réalité, c'est beaucoup plus compliqué et cela est abordé dans la littérature pertinente ou dans les bons cours d'"algorithmes et structures de données".

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

En bref, la fonction de hachage doit fonctionner premièrement : rapidement, deuxièmement, il n'est pas nécessaire d'inventer quelque chose de très compliqué, car l'apparition des mêmes valeurs est normalement résolue à l'intérieur du dictionnaire par force brute directe. L'essentiel est de ne pas avoir de collisions trop fréquentes, c'est tout. Dans Generic, un ensemble de fonctions dans le fichier HashFunction.mqh est responsable du hachage des fonctions des types de base. Pour s'assurer que tout y est simple, voyons comment il est organisé :

//+------------------------------------------------------------------+
//|                                                 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));
     }
  }
//+------------------------------------------------------------------+

Lestypes d'entiers sont soit retournés tels quels, soit, pour les types d'entiers courts, des opérations de conversion bit à bit non compliquées sont utilisées. Pour les types qui ne tiennent pas dans 32 chiffres, on utilise un ou exclusif suivi d'une jointure gauche-droite. Pour les chaînes de caractères, un hachage simple est également calculé par force brute directe. Pour les nombres réels, une représentation binaire est prise avec l'union et elle est utilisée comme un hachage.

 

Les algorithmes de type dictionnaire sont conventionnellement divisés en deux parties :

  • Ensembles de paires clé-valeur, où la clé est unique et la valeur ne l'est pas. En générique, il s'agit de CHashMap
  • Ensembles de valeurs uniques. En générique, il s'agit de CHashSet.

Qu'est-ce qu'un CHashSet ? Il s'agit d'une collection (un tableau par nature) où chaque élément est unique. Par exemple, une telle collection peut contenir les nombres 2,5,1,7,10,15,1024. Mais deux nombres ne peuvent pas être égaux. Il peut également contenir des chaînes de caractères, des nombres réels et même des types complexes personnalisés (nous y reviendrons plus tard). Mais la règle est la même pour tous les types - il ne peut pas y avoir d'autres types du même type dans le dictionnaire.

Qu'est-ce que CHashMap ? Il s'agit d'une collection (également un tableau par nature), où chaque élément est un type complexe clé-valeur :

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

Il est structuré presque exactement comme CHashMap, mais permet une correspondance entre deux ensembles telle qu'un élément de l'ensemble 1 correspond à un élément de l'ensemble 2. C'est une chose très pratique, permettant d'écrire des algorithmes de requête très efficaces avec un temps d'exécution moyen de O(1).

Plus tard, nous examinerons des exemples pour voir comment établir une sorte de correspondance.

Il est intéressant de noter que tout dictionnaire clé-valeur établit naturellement une telle relation non triviale deun à plusieurs. Par exemple, nous disposons d'un ensemble d'ordres historiques et d'un ensemble de transactions qui ont été exécutées sur cette base. Chaque transaction correspond à un seul ordre, mais un ordre peut correspondre à plusieurs transactions. Le dictionnaire d'une telle relation peut stocker comme clé le numéro de la transaction, et comme valeur, le numéro de l'ordre qui a servi à l'ouvrir.
 
S'il vous plaît, ne jetez pas le fil hors sujet.
1...34567891011121314151617...38
Nouveau commentaire