Biblioteca de clases genéricas - errores, descripción, preguntas, características de uso y sugerencias - página 10

[Vasiliy Sokolov]

Acerca de las funciones hash

De los ejemplos anteriores, está claro que la función hash se lleva la mayor parte de la carga. Una función hash puede ser lo más rápida posible, pero lo más probable es que sea muy propensa a las colisiones. Y viceversa, una función hash puede hacerse tan resistente a las colisiones como sea posible, pero su complejidad computacional será inadecuada para la tarea que se realiza. Consideremos dos ejemplos extremos. Ejemplo 1, la función hash más rápida posible:

int GetHashCode(string word)
{
   return 0;
}

Siempre devolverá el mismo número. Si nuestro diccionario va a almacenar una sola palabra, entonces su trabajo será suficiente, porque esta palabra estará ubicada en el índice 0. Sin embargo, si tenemos 10 palabras, entonces las diez palabras estarán en el índice 0 (no olvidemos que tenemos un array de arrays).

Para el segundo ejemplo, pasemos a un cifrado reversible, por ejemplo, basado en una red Feistel con un número de rondas N. No se trata de una función hash, y no está sujeta a colisiones en absoluto. Es decir, para dos cadenas diferentes obtendremos números diferentes garantizados. La longitud de los números obtenidos será igual a la longitud de la cadena. Así, si la cadena tiene 1000 caracteres, obtendremos un array uchar de tamaño 1000. Si tenemos que almacenar esta cadena en un diccionario de 3 elementos, ¿no crees que sería extraño calcular un código tan complejo para encontrar una palabra con sólo tres elementos?

De ahí que debamos buscar siempre un término medio (como ha señalado acertadamente fxsaber): necesitamos una función que calcule rápidamente los hashes y que, por lo general, no tenga colisiones. Estimemos la probabilidad de colisiones para nuestra función hash anterior:

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

Hay 26 caracteres en el alfabeto. Supongamos que el número de palabras que comienzan con el símbolo "a" es igual al número de palabras que comienzan con cualquier otro símbolo. Entonces, si nuestro diccionario contiene 988 palabras, 38 de ellas empiezan por a, 38 por b, 38 por c, ... 38 a la letra w y 38 a la letra - z. La probabilidad de que se produzca una colisión en cada caso sería de 1/26 o 3,8461%. Si tenemos 988 palabras, obtenemos 988*3,8461 = 37,999 palabras por índice.

Está claro que cuantas más palabras haya para una misma letra, más difícil será encontrar una palabra concreta. En nuestro caso no sólo tenemos que calcular el índice de la primera letra, sino también buscar todas las palabras que también empiezan por la misma letra. Para evitarlo, podemos complicar la función 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;
}

Es decir, tomamos los dos primeros caracteres de la palabra. Entonces las combinaciones posibles no serán 26, sino 26^2 = 676. Cabe destacar que la complejidad de la segunda variante de cálculo de la función hash ha aumentado linealmente, a grandes rasgos, a la mitad, mientras que su resistencia a las colisiones ha aumentado de forma no lineal, al cuadrado.

Para la segunda variante, la media sería de una colisión por cada 676 palabras. En nuestro caso, para 988 palabras, habría 988/676 = 1,4615 colisiones por índice. Esto significa que cada índice contendrá de media una o dos palabras. Así que, por término medio, no habrá ninguna colisión (una comparación), o serán muy breves (dos comparaciones).

Si la relación entre el tamaño del diccionario y las coordenadas de la función hash es cercana a 1,0000000, entonces en promedio no se necesitará la fuerza bruta, porque cada elemento se ubicará en su propio índice por sí mismo. Si una función hash proporciona un rango muy grande de valores, la relación entre el tamaño del diccionario y las posibles combinaciones de la función hash será siempre inferior a 1,0. Por ejemplo, si una función hash produce 2^32 combinaciones, entonces para cualquier tamaño N menor que 2^32 se mantendrá la relación N/2^32 < 1,0. Si N es muy pequeño, entonces simplemente normalizamos el número obtenido por la función hash, para que siempre esté en el límite de N:

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

Si la función hash genera resultados de manera uniforme, en promedio, obtendremos una proporción de 1.000. es decir, habrá una sola palabra en un índice de la matriz. Así, podemos decir que un diccionario es un caso especial de un array con una clave en lugar de un índice.

[Vasiliy Sokolov]

Etiqueta Konow:

El tamaño de la matriz se puede cambiar fácilmente para que coincida con el tamaño del diccionario.

No tengo en cuenta las infinitas variantes.

La cuestión es que a menudo se desconoce el tamaño del diccionario. Un ejemplo sencillo, digamos que tenemos un Asesor Experto que opera. Hace un seguimiento de las operaciones realizadas. Una vez que una operación aparece en el historial, necesitamos conectar esta operación con el Medjik del EA. Para ello es lógico utilizar el diccionario. Donde el número de operación se utiliza como clave (identificador único), y el número mágico del Asesor Experto se utiliza como valor. El problema es que al inicio del EA no podemos determinar de antemano si tendremos 100 operaciones, 1000 o ninguna. Cualquiera que sea la memoria que se asigne por adelantado, será muy poca o demasiada.

[Реter Konow]

Vasiliy Sokolov:

Esa es la cuestión: a menudo se desconoce el tamaño del diccionario. Un ejemplo sencillo, digamos que tenemos un asesor que comercia. Hace un seguimiento de las operaciones realizadas. Cuando aparece una operación en el historial, tenemos que conectar esta operación con el Medjack del Asesor Experto. Para ello es lógico utilizar el diccionario. Donde el número de operación se utiliza como clave (identificador único), y el número mágico del Asesor Experto se utiliza como valor. El problema es que al inicio del EA no podemos determinar de antemano si tendremos 100 operaciones, 1000 o ninguna. No importa la cantidad de memoria que se asigne de antemano, seguirá siendo poca o demasiada.

Bueno, obviamente, hay diferentes tareas.

Estaba resolviendo una tarea en la que tenía que crear un diccionario conveniente para una lengua humana. El tamaño de mi matriz no es exacto, pero ¿qué problema hay en ajustarlo al número de palabras de un idioma concreto? Puede caber fácilmente ahí.

Por ejemplo, un idioma ruso. Supongamos que contiene 10 000 palabras base. Todas estas palabras pueden encajar muy bien en mi conjunto.

La primera dimensión - 66 letras (pequeñas y grandes), la segunda dimensión - el número de letras de la palabra (hasta 25, por ejemplo), la tercera dimensión - coincide con la primera letra y el número de letras - 50.

Todo el lenguaje encajará.

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

Al principio, resolvía exactamente este problema. Ahora estás sustituyendo el problema original por otro y diciendo que la solución no es buena.

[Реter Konow]

Vasiliy Sokolov:

No importa la cantidad de memoria que asignes de antemano, será muy poca o demasiada.

Sí.

Tan cierto como que no existe una solución universal para todas las tareas.

[Alexey Viktorov]

Etiqueta Konow:

Es cierto.

También es cierto que no hay una solución única para todos.

Completamente indiscutible.

[Vasiliy Sokolov]

Sergey Dzyublik:

Baja la voz, camarada. Nadie es inmune a los errores, ni siquiera tú. Así que sea lo suficientemente amable como para señalar los errores de los demás en un tono más suave. Lo corregiré ahora.

[Sergey Dzyublik]

Alexey Viktorov:

¿Seguirá siendo un secreto el correcto?

En principio, no puede haber una variante correcta de las tablas hash y los hashes: todo depende de los fines específicos y las condiciones de la aplicación.
Es como hacer un sándwich. Tal vez alguien no come mayonesa o ketchup, o es un vegano....
Pero poner el ketchup en la mesa y poner el pan encima, está claro que es not....


Lo básico sobre el tema para los perezosos:
https://www.slideshare.net/mkurnosov/6-32402313

En realidad es mucho más complicado y se discute en la literatura pertinente o en buenos cursos de "algoritmos y estructuras de datos".

[Vasiliy Sokolov]

En resumen, la función hash debe funcionar, en primer lugar: rápidamente, en segundo lugar, no es necesario inventar algo muy complicado, porque la aparición de los mismos valores se resuelve normalmente dentro del diccionario por fuerza bruta directa. Lo principal es no tener colisiones demasiado frecuentes, eso es todo. En Generic, un conjunto de funciones en el archivo HashFunction.mqh es responsable del hash de las funciones de los tipos base. Para asegurarnos de que todo es sencillo allí, veamos cómo 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));
     }
  }
//+------------------------------------------------------------------+

Los tipos de enteros se devuelven tal cual, o para los tipos de enteros cortos, se utilizan operaciones de conversión no complicadas a nivel de bits. Para los tipos que no caben en 32 dígitos, se utiliza una o exclusiva seguida de una unión izquierda-derecha. En el caso de las cadenas, también se calcula un hash sin complicaciones mediante fuerza bruta directa. Para los números reales se toma una representación de bits con la unión y se utiliza como un hash.

[Vasiliy Sokolov]

Los algoritmos de tipo diccionario se dividen convencionalmente en dos partes:

• Conjuntos de pares clave-valor, donde la clave es única y el valor no. En Generic esto es CHashMap
• Conjuntos de valores únicos. En Generic esto es CHashSet.

¿Qué es un CHashSet? Es una colección (un array por su naturaleza) donde cada elemento es único. Por ejemplo, dicha colección puede contener los números 2,5,1,7,10,15,1024. Pero no hay dos números iguales. También puede contener cadenas, números reales e incluso tipos complejos personalizados (más adelante se habla de ello). Pero la regla es la misma para cualquier tipo: no puede haber otro del mismo tipo en el diccionario.

¿Qué es CHashMap? Es una colección (también un array por naturaleza), donde cada elemento es un tipo clave-valor complejo:

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

Está estructurado casi exactamente como CHashMap, pero permite una correspondencia entre dos conjuntos tal que un elemento del conjunto 1 se corresponde con un elemento del conjunto 2. Esto es algo muy útil, ya que permite escribir algoritmos de consulta muy eficientes con un tiempo medio de ejecución de O(1).

Más adelante, veremos ejemplos para ver cómo construir algún tipo de correspondencia.

Curiosamente, cualquier diccionario clave-valor establece de forma natural una relación no trivial como la deuno a muchos. Por ejemplo, tenemos un montón de órdenes históricas, y un montón de operaciones que se ejecutaron en base a ellas. Cada operación corresponde a una sola orden, pero una orden puede corresponder a varias operaciones. El diccionario de dicha relación puede almacenar como clave el número de la operación, y como valor, el número de la orden que sirvió para abrirla.

[Artyom Trishkin]

Por favor, no tire el hilo fuera de tema.