Libreria di classi generiche - bug, descrizione, domande, caratteristiche d'uso e suggerimenti - pagina 10

[Vasiliy Sokolov]

Informazioni sulle funzioni hash

Dagli esempi precedenti, è chiaro che la funzione hash prende il grosso del carico. Una funzione hash può essere il più veloce possibile, ma molto probabilmente sarà molto incline alle collisioni. E viceversa, una funzione hash può essere resa il più possibile resistente alle collisioni, ma la sua complessità computazionale sarà inadeguata al compito da svolgere. Consideriamo due esempi estremi. Esempio 1, la funzione hash più veloce possibile:

int GetHashCode(string word)
{
   return 0;
}

Restituirà sempre lo stesso numero. Se il nostro dizionario memorizzerà una sola parola, allora il suo lavoro sarà sufficiente, perché questa parola si troverà all'indice 0. Se però abbiamo 10 parole, allora tutte e dieci le parole saranno all'indice 0 (non dimenticate che abbiamo un array di array).

Per il secondo esempio, passiamo a una crittografia reversibile, per esempio basata su una rete Feistel con numero di giri N. Questa non è una funzione hash, e non è affatto soggetta a collisioni. Cioè per due stringhe diverse otterremo numeri diversi garantiti. La lunghezza dei numeri ottenuti sarà uguale alla lunghezza della stringa. Quindi, se la stringa è lunga 1000 caratteri, otterremo un array uchar con dimensione 1000. Se abbiamo bisogno di memorizzare questa stringa in un dizionario di 3 elementi, non pensate che sarebbe strano calcolare un codice così complesso per trovare una parola con solo tre elementi.

Quindi, dovremmo sempre cercare una via di mezzo (come giustamente sottolineato da fxsaber): abbiamo bisogno di una funzione che calcoli rapidamente gli hash e di solito non ottiene collisioni. Stimiamo la probabilità di collisioni per la nostra precedente funzione hash:

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

Ci sono 26 caratteri nell'alfabeto. Supponiamo che il numero di parole che iniziano con il simbolo 'a' sia uguale al numero di parole che iniziano con qualsiasi altro simbolo. Allora se il nostro dizionario contiene 988 parole, 38 di esse iniziano con a, 38 con b, 38 con c, ... 38 alla lettera w e 38 alla lettera - z. La probabilità che si verifichi una collisione in ogni caso sarebbe 1/26 o 3,8461%. Se abbiamo 988 parole, allora otteniamo 988*3,8461 = 37,999 parole per indice.

È chiaro che più parole ci sono per una stessa lettera, più è difficile trovare una parola particolare. Nel nostro caso non dobbiamo solo calcolare l'indice della prima lettera, ma anche cercare tutte le parole che iniziano con la stessa lettera. Per evitare questo, possiamo complicare la funzione hash:

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

Cioè prendiamo i primi due caratteri della parola. Allora le combinazioni possibili non saranno 26, ma 26^2 = 676. Va notato che la complessità della seconda variante di calcolo della funzione hash è aumentata linearmente, più o meno della metà, mentre la sua resistenza alle collisioni è aumentata in modo non lineare, di un quadrato.

Per la seconda variante, la media sarebbe una collisione ogni 676 parole. Nel nostro caso, per 988 parole, ci sarebbero 988/676 = 1,4615 collisioni per indice. Ciò significa che ogni indice conterrà in media o una parola o 2 parole. Quindi in media non ci saranno collisioni (un confronto), o saranno molto brevi (due confronti).

Se il rapporto tra la dimensione del dizionario e i cobmins della funzione hash è vicino a 1.0000000, allora in media non sarà necessaria la forza bruta, perché ogni elemento si troverà da solo al suo indice. Se una funzione hash fornirà una gamma molto ampia di valori, il rapporto tra la dimensione del dizionario e le possibili combinazioni della funzione hash sarà sempre inferiore a 1,0. Per esempio, se una funzione hash produce 2^32 combinazioni, allora per qualsiasi dimensione N inferiore a 2^32 il rapporto N/2^32 < 1,0 sarà valido. Se N è molto piccolo, allora si normalizza semplicemente il numero ottenuto dalla funzione hash, in modo che sia sempre nel limite di N:

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

Se la funzione di hash genera risultati in modo uniforme, in media, otterremo un rapporto di 1.000. Cioè ci sarà solo una parola in un indice dell'array. Così possiamo dire che un dizionario è un caso speciale di un array con una chiave invece di un indice.

[Vasiliy Sokolov]

Tag Konow:

La dimensione dell'array può essere facilmente cambiata per corrispondere alla dimensione del dizionario.

Non prendo in considerazione le varianti infinite.

Il punto è che la dimensione del dizionario è spesso sconosciuta. Un semplice esempio, diciamo che abbiamo un Expert Advisor che fa trading. Tiene traccia delle transazioni effettuate. Una volta che un trade appare nella storia, abbiamo bisogno di collegare questo trade con il Medjik dell'EA. Per questo è logico usare il dizionario. Dove il numero di trade è usato come chiave (identificatore unico), e il numero magico dell'Expert Advisor è usato come valore. Il problema è che all'inizio dell'EA non possiamo determinare in anticipo se avremo 100 trade, 1000 o nessun trade. Qualunque sia la memoria allocata in anticipo, sarà o troppo poca o troppo grande.

[Реter Konow]

Vasiliy Sokolov:

Questo è il punto: la dimensione del dizionario è spesso sconosciuta. Un semplice esempio, diciamo che abbiamo un consulente che fa trading. Tiene traccia delle transazioni effettuate. Quando un trade appare nella storia, dobbiamo collegare questo trade con il Medjack dell'Expert Advisor. Per questo è logico usare il dizionario. Dove il numero di trade è usato come chiave (identificatore unico), e il numero magico dell'Expert Advisor è usato come valore. Il problema è che all'inizio dell'EA non possiamo determinare in anticipo se avremo 100 trade, 1000 o nessun trade. Non importa quanta memoria si alloca in anticipo, sarà sempre o troppo poca o troppo grande.

Beh, ovviamente, ci sono diversi compiti.

Stavo risolvendo un compito in cui dovevo creare un dizionario conveniente per una lingua umana. La dimensione del mio array non è esatta, ma che problema c'è ad adattarla al numero di parole di una lingua specifica? Può entrare facilmente lì dentro.

Per esempio una lingua russa. Supponiamo che contenga 10 000 parole base. Tutte queste parole si adattano bene alla mia matrice.

La prima dimensione - 66 lettere (piccole e grandi), la seconda dimensione - il numero di lettere nella parola (fino a 25 per esempio), la terza dimensione - corrisponde alla prima lettera e il numero di lettere - 50.

Tutta la lingua si adatta.

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

Inizialmente, stavo risolvendo esattamente questo problema. Ora stai sostituendo il problema originale con un altro e dicendo che la soluzione non è buona.

[Реter Konow]

Vasiliy Sokolov:

Non importa quanta memoria si alloca in anticipo, sarà o troppo poca o troppo grande.

Giusto.

Così come è vero che non esiste una soluzione universale per tutti i compiti.

[Alexey Viktorov]

Tag Konow:

Vero.

È anche vero che non c'è una soluzione unica per tutti.

Completamente indiscutibile.

[Vasiliy Sokolov]

Sergey Dzyublik:

Abbassa la voce, compagno. Nessuno è immune dagli errori, nemmeno tu. Quindi siate abbastanza gentili da far notare gli errori degli altri con un tono più morbido. Lo correggerò ora.

[Sergey Dzyublik]

Alexey Viktorov:

Quello giusto rimarrà un segreto?

Non ci può essere una variante corretta di tabelle hash e hash in linea di principio - tutto dipende dagli scopi specifici e dalle condizioni di applicazione.
È come fare un panino. Forse qualcuno non mangia la maionese o il ketchup, o è un vegan....
Ma mettere il ketchup sul tavolo e metterci sopra il pane - è abbastanza chiaro che non è ....


Nozioni di base sull'argomento per i pigri:
https://www.slideshare.net/mkurnosov/6-32402313

In realtà è molto più complicato e viene discusso nella letteratura pertinente o in buoni corsi di "algoritmi e strutture dati".

[Vasiliy Sokolov]

In breve, la funzione di hash dovrebbe funzionare in primo luogo: rapidamente, in secondo luogo, non c'è bisogno di inventare qualcosa di molto complicato, perché l'aspetto degli stessi valori è normalmente risolto all'interno del dizionario per forza bruta diretta. L'importante è non avere collisioni troppo frequenti, tutto qui. In Generic, un insieme di funzioni nel file HashFunction.mqh è responsabile dell'hash delle funzioni dei tipi base. Per essere sicuri che tutto sia semplice lì, vediamo come è organizzato:

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

Itipi interi sono restituiti così come sono, o per i tipi interi corti, vengono usate operazioni di conversione bitwise non complicate. Per i tipi che non entrano in 32 cifre, si usa un o esclusivo seguito da un join sinistra-destra. Per le stringhe, un hash non complicato è anche calcolato tramite forza bruta diretta. Per i numeri reali si prende una rappresentazione in bit con l'unione e la si usa come hash.

[Vasiliy Sokolov]

Gli algoritmi di tipo dizionario sono convenzionalmente divisi in due parti:

• Insiemi di coppie chiave-valore, dove la chiave è unica e il valore non lo è. In Generico questo è CHashMap
• Insiemi di valori unici. In Generico questo è CHashSet.

Cos'è un CHashSet? È una collezione (un array per sua natura) dove ogni elemento è unico. Per esempio, una tale collezione può contenere i numeri 2,5,1,7,10,15,1024. Ma due numeri non possono essere uguali. Può anche contenere stringhe, numeri reali e persino tipi complessi personalizzati (di cui parleremo più avanti). Ma la regola è la stessa per qualsiasi tipo - non ci può essere un altro dello stesso tipo nel dizionario.

Cos'è CHashMap? È una collezione (anche un array per natura), dove ogni elemento è un tipo di chiave-valore complesso:

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

È strutturata quasi esattamente come CHashMap, ma permette una corrispondenza tra due insiemi tale che un elemento dell'insieme 1 corrisponde a un elemento dell'insieme 2. Questa è una cosa molto comoda, permettendo di scrivere algoritmi di interrogazione molto efficienti con un tempo medio di esecuzione di O(1).

Più avanti, guarderemo degli esempi per vedere come costruire una sorta di corrispondenza.

È interessante notare che qualsiasi dizionario chiave-valore stabilisce naturalmente una relazione non banale comeuno a molti. Per esempio, abbiamo un mucchio di ordini storici e un mucchio di trade che sono stati eseguiti sulla base di essi. Ogni trade corrisponde a un solo ordine, ma un ordine può corrispondere a più trade. Il dizionario di una tale relazione può memorizzare come chiave il numero del commercio, e come valore, il numero dell'ordine che è servito per aprirlo.

[Artyom Trishkin]

Per favore, non gettate il thread fuori tema.