Biblioteca de classes genéricas - bugs, descrição, perguntas, recursos de uso e sugestões - página 10

[Vasiliy Sokolov]

Sobre as funções hash

Dos exemplos anteriores, é claro que a função de hash leva o peso da carga. Uma função hash pode ser tão rápida quanto possível, mas muito provavelmente será muito propensa a colisões. E vice-versa, uma função de hash pode ser feita o mais resistente possível à colisão, mas sua complexidade computacional será inadequada para a tarefa que está sendo executada. Vamos considerar dois exemplos extremos. Exemplo 1, a função hash mais rápida possível:

int GetHashCode(string word)
{
   return 0;
}

Sempre devolverá o mesmo número. Se o nosso dicionário vai armazenar apenas uma palavra, então o seu trabalho será suficiente, porque esta palavra estará localizada no índice 0. Se tivermos 10 palavras, no entanto, então todas as dez palavras estarão no índice 0 (não se esqueça que temos um conjunto de arrays).

Para o segundo exemplo, vamos recorrer a uma encriptação reversível, por exemplo, baseada em uma rede Feistel com número de rondas N. Isto não é uma função hash, e não está sujeito a colisões. Ou seja, para duas cordas diferentes, teremos números diferentes garantidos. O comprimento dos números obtidos será igual ao comprimento da corda. Portanto, se a corda tiver 1000 caracteres, teremos um uchar de matriz com tamanho 1000. Se precisarmos armazenar esta string num dicionário de 3 elementos, não acha que seria estranho calcular um código tão complexo para encontrar uma palavra com apenas três elementos.

Portanto, devemos sempre procurar um meio de comunicação feliz (como corretamente apontado pelo fxsaber): precisamos de uma função que calcule rapidamente os hashes e que normalmente não colida. Vamos estimar a probabilidade de colisões para a nossa função hash anterior:

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

Há 26 caracteres no alfabeto. Vamos assumir que o número de palavras que começam com o símbolo 'a' é igual ao número de palavras que começam com qualquer outro símbolo. Então se o nosso dicionário contém 988 palavras, 38 delas começam com a, 38 com b, 38 com c, ... 38 à letra w e 38 à letra - z. A probabilidade de ocorrer uma colisão em cada caso seria de 1/26 ou 3,8461%. Se tivermos 988 palavras, então obtemos 988*3,8461 = 37,999 palavras por índice.

É claro que quanto mais palavras há para uma mesma letra, mais difícil é encontrar uma palavra em particular. No nosso caso, não só temos que calcular o índice da primeira letra, mas também procurar todas as palavras que começam também com a mesma letra. Para evitar isso, podemos complicar a função do 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;
}

Isto é, tomamos os dois primeiros caracteres da palavra. Então as combinações possíveis não serão 26, mas 26^2 = 676. Deve-se notar que a complexidade da segunda variante da função hash de cálculo aumentou linearmente, grosso modo, pela metade, enquanto sua resistência a colisões aumentou não-linearmente, por um quadrado.

Para a segunda variante, a média seria uma colisão para cada 676 palavras. No nosso caso, para 988 palavras, haveria 988/676 = 1,4615 colisões por índice. Isto significa que cada índice conterá em média uma palavra ou 2 palavras. Assim, em média não haverá colisões (uma comparação), ou elas serão muito curtas (duas comparações).

Se a razão entre o tamanho do dicionário e a função hash estiver próxima de 1.0000000, então em média não será necessária força bruta, pois cada elemento estará localizado em seu próprio índice por si só. Se uma função hash fornecer uma gama muito grande de valores, a razão entre o tamanho do dicionário e as combinações possíveis da função hash será sempre inferior a 1,0. Por exemplo, se uma função hash produz 2^32 combinações então para qualquer tamanho N menor que 2^32 a proporção N/2^32 < 1.0 irá se manter. Se N é muito pequeno, então nós simplesmente normalizamos o número obtido pela função hash, de modo que ele estaria sempre no limite de N:

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

Se a função hash gera resultados uniformemente, em média, obteremos uma proporção de 1.000. Ou seja, haverá apenas uma palavra em um índice de array. Assim, podemos dizer que um dicionário é um caso especial de um array com uma chave em vez de um índice.

[Vasiliy Sokolov]

Tag Konow:

O tamanho da matriz pode ser facilmente alterado para corresponder ao tamanho do dicionário.

Eu não levo em conta infinitas variantes.

A questão é que o tamanho do dicionário é muitas vezes desconhecido. Um exemplo simples, digamos que temos um Expert Advisor que negocia. Acompanha os negócios realizados. Uma vez que uma troca aparece na história, precisamos conectar essa troca com o Medjik da EA. Para isso, é lógico usar o dicionário. Onde o número da negociação é usado como chave (identificador único), e o número mágico do Expert Advisor é usado como um valor. O problema é que no início da EA não podemos determinar antecipadamente se teremos 100 negociações, 1000 ou nenhuma negociação. Seja qual for a memória alocada antecipadamente, ela será muito pequena ou muito grande.

[Реter Konow]

Vasiliy Sokolov:

O problema é esse: o tamanho do dicionário é muitas vezes desconhecido. Um exemplo simples, digamos que temos um consultor a negociar. Rastreia os negócios realizados. Quando uma troca aparece na história, precisamos de ligar esta troca com o Medjack do Expert Advisor. Para isso, é lógico usar o dicionário. Onde o número da negociação é usado como chave (identificador único), e o número mágico do Expert Advisor é usado como um valor. O problema é que no início da EA não podemos determinar antecipadamente se teremos 100 negociações, 1000 ou nenhuma negociação. Não importa quanta memória você alocar de antemão, ela ainda será muito pequena ou muito grande.

Bem, obviamente, há tarefas diferentes.

Eu estava a resolver uma tarefa em que tinha de criar um dicionário conveniente para uma língua humana. O tamanho da minha matriz não é exato, mas qual é o problema em ajustá-la ao número de palavras de uma língua específica? Pode caber facilmente lá dentro.

Por exemplo, uma língua russa. Suponha que contenha 10 000 palavras base. Todas estas palavras podem caber bem na minha matriz.

A primeira dimensão - 66 letras (pequenas e grandes), a segunda dimensão - o número de letras na palavra (até 25, por exemplo), a terceira dimensão - corresponde à primeira letra e o número de letras - 50.

A língua inteira vai caber.

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

Inicialmente, eu estava a resolver exactamente este problema. Agora você está substituindo o problema original por outro e dizendo que a solução não é boa.

[Реter Konow]

Vasiliy Sokolov:

Não importa quanta memória você alocar de antemão, ela será muito pequena ou muito grande.

Certo.

Tão verdade como não existe uma solução universal para todas as tarefas.

[Alexey Viktorov]

Tag Konow:

É verdade.

Também é verdade que não existe uma solução única para todos.

Completamente indiscutível.

[Vasiliy Sokolov]

Sergey Dzyublik:

Fale baixo, camarada. Ninguém é imune a erros, nem mesmo você. Portanto, seja gentil o suficiente para apontar os erros dos outros em um tom mais suave. Vou corrigi-lo agora.

[Sergey Dzyublik]

Alexey Viktorov:

Será que o certo continuará a ser segredo?

Não pode haver uma variante correta de tabelas de hash e hashes em princípio - tudo depende de propósitos específicos e condições de aplicação.
É como fazer uma sanduíche. Talvez alguém não coma maionese ou ketchup, ou seja um vegan....
Mas pôr ketchup na mesa e pôr-lhe pão em cima - é mais ou menos claro que não é....


Noções básicas sobre o assunto para os preguiçosos:
https://www.slideshare.net/mkurnosov/6-32402313

Na realidade é muito mais complicado e é discutido na literatura relevante ou em bons cursos de "algoritmos e estruturas de dados".

[Vasiliy Sokolov]

Em suma, a função hash deve funcionar em primeiro lugar: rapidamente, em segundo lugar, não há necessidade de inventar algo muito complicado, porque a aparência dos mesmos valores é normalmente resolvida dentro do dicionário pela força bruta direta. O principal é não ter colisões muito frequentes, só isso. Em Genéricos, um conjunto de funções no arquivo HashFunction.mqh é responsável pelo hash de funções de tipos de base. Para ter certeza de que tudo é simples lá, vamos ver como está organizado:

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

Os tipos inteiros são devolvidos como estão, ou para tipos inteiros curtos, são usadas operações de conversão bitwise não complicadas. Para tipos que não cabem em 32 dígitos, é usado um exclusivo ou seguido por uma união esquerda-direita. Para cordas, um hash descomplicado também é calculado através da força bruta direta. Para números reais, um pouco de representação é tomado com união e é usado como um hash.

[Vasiliy Sokolov]

Os algoritmos do tipo dicionário são convencionalmente divididos em duas partes:

• Conjuntos de pares de chaves de valor, onde a chave é única e o valor não é. Em Genéricos, este é CHashMap
• Conjuntos de valores únicos. Em genérico este é CHashSet.

O que é um CHashSet? É uma colecção (um conjunto pela sua natureza) onde cada elemento é único. Por exemplo, tal coleção pode conter números 2,5,1,7,10,15,1024. Mas não há dois números que possam ser iguais. Também pode conter cadeias de caracteres, números reais e até tipos complexos personalizados (mais sobre isso mais tarde). Mas a regra é a mesma para qualquer tipo - não pode haver outro do mesmo tipo no dicionário.

O que é o CHashMap? É uma colecção (também uma matriz por natureza), onde cada elemento é um tipo de valor chave complexo:

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

É estruturado quase exatamente como o CHashMap, mas permite uma correspondência entre dois conjuntos de forma que um elemento do conjunto 1 corresponde a um elemento do conjunto 2. Isto é muito útil, permitindo escrever algoritmos de consulta muito eficientes com um tempo médio de execução de O(1).

Mais tarde, vamos ver exemplos para ver como construir algum tipo de correspondência.

Curiosamente, qualquer dicionário de valores-chave estabelece naturalmente uma relação não trivial comouma para muitas. Por exemplo, temos um monte de ordens históricas, e um monte de negócios que foram executados com base nelas. Cada negociação corresponde apenas a uma ordem, mas uma ordem pode corresponder a várias negociações. O dicionário de tal relação pode armazenar como chave o número do negócio, e como valor, o número da ordem que serviu para abri-la.

[Artyom Trishkin]

Por favor, não deite o fio fora do tópico.