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

Nuevo comentario
 
Renat Fatkhullin:

Casi imposible y si te encuentras con uno, el acceso sigue siendo súper efectivo.

La colisión en cualquier nivel de eficiencia es mala. Gracias por la respuesta. Lo tendré en cuenta.

 
fxsaber:

La colisión en cualquier nivel de eficiencia es mala. Gracias por su respuesta. Lo tendré en cuenta.

Los Hashmaps no son, por definición, libres de colisiones.

 
fxsaber #:

Pregunta sobre las colisiones. ¿Es posible que se produzca una colisión en ese caso?

Si se han producido 27.000 registros.

Se producirán constantemente colisiones, especialmente cuando la colección crezca (cambie de tamaño). Ya que el hash se trunca adicionalmente al número de la banda, y siempre hay un número limitado de ellos (idealmente igual a uno).

Conclusiones:

1. No es la estabilidad criptográfica de la función hash lo que importa para el mapa, sino su velocidad. La función hash sólo tiene que proporcionar una buena aleatoriedad y ya está.

2. Es mejor evitar el cambio de tamaño por todos los medios. Es el cambio de tamaño lo que provoca la principal reducción, no las colisiones de la función hash. Siempre que sea posible, inicialice la colección con un número preestablecido de elementos. Aunque no los conozca con exactitud, dé una cifra aproximada: ayudará mucho al algoritmo.

3. Las colisiones son un mecanismo de compactación habitual. A través de colisiones, es posible almacenar tres registros con id, digamos, 159, 4'569'209, 29'459'876 en un array de longitud tres, en lugar de longitud 30 000 000, incluso si los dos últimos valores caen ambos en la banda con índice 2.

 
Vasiliy Sokolov #:

2. Es mejor evitar el cambio de tamaño por todos los medios. El principal inconveniente es el cambio de tamaño, no las colisiones de la función hash. Siempre que sea posible, inicialice la colección con un número preestablecido de elementos. Aunque no los conozcas con exactitud, da una cifra aproximada: será de gran ayuda para el algoritmo.

Por favor, muéstrelo con un ejemplo.

Sólo uso esto hasta ahora.

//+------------------------------------------------------------------+
//| Adds the specified key and value to the map.                     |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Add(TKey key,TValue value);
//+------------------------------------------------------------------+
//| Gets the value associated with the specified key.                |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::TryGetValue(TKey key,TValue &value);
 
fxsaber #:

Por favor, muéstrame un ejemplo.

Sólo uso esto hasta ahora.

Cuando crees una colección CHashMap, utiliza uno de los constructores que acepta el parámetro de capacidad. Consulte mi artículo sobre CDicionary para obtener detalles sobre el rendimiento durante el redimensionamiento. Hay un recorrido completo de este algoritmo.

 

He encontrado un comportamiento muy inusual en CHashMap.

// Демонстрация невозможности доступа по ключу после первого добавления.

#include <Generic\HashMap.mqh>

void OnStart()
{
  // Отсортированный массив неповторяющихся цен.
  const double Array[] =
{1.70682, 1.70691, 1.70700, 1.70709, 1.70710, 1.70717, 1.70721, 1.70742, 1.70749, 1.70752, 1.70757, 1.70766, 1.70768, 1.70769, 1.70771, 1.70773, 1.70774, 1.70777,
 1.70782, 1.70785, 1.70786, 1.70797, 1.70804, 1.70808, 1.70813, 1.70850, 1.70868, 1.70879, 1.70881, 1.70883, 1.70895, 1.70905, 1.70918, 1.70921, 1.70936, 1.70962,
 1.70966, 1.71022, 1.71027, 1.71047, 1.71056, 1.71080, 1.71081, 1.71093, 1.71096, 1.71109, 1.71112, 1.71119, 1.71120, 1.71127, 1.71128, 1.71135, 1.71136, 1.71138,
 1.71145, 1.71147, 1.71148, 1.71150, 1.71155, 1.71159, 1.71162, 1.71164, 1.71168, 1.71172, 1.71203, 1.71204, 1.71210, 1.71269, 1.71289, 1.71293, 1.71299, 1.71334,
 1.71337, 1.71343, 1.71357, 1.71358, 1.71367, 1.71371, 1.71374, 1.71380, 1.71402, 1.71410, 1.71414, 1.71425, 1.71426, 1.71427, 1.71429, 1.71430, 1.71446, 1.71474,
 1.71477, 1.71518, 1.71521, 1.71558, 1.71587, 1.71588, 1.71617, 1.71620, 1.71624, 1.71626, 1.71629, 1.71635, 1.71644, 1.71654, 1.71655, 1.71658, 1.71661, 1.71664,
 1.71689, 1.71700, 1.71712, 1.71718, 1.71727, 1.71752, 1.71769, 1.71775, 1.71780, 1.71782, 1.71786, 1.71792, 1.71795, 1.71797, 1.71798, 1.71801, 1.71815, 1.71827,
 1.71832, 1.71835, 1.71841, 1.71869, 1.71895, 1.71908, 1.71951, 1.71984, 1.71992, 1.72008, 1.72086, 1.72132, 1.72147, 1.72204, 1.72208, 1.72212, 1.72215, 1.72227,
 1.72230, 1.72233, 1.72234, 1.72336, 1.72374, 1.72378, 1.72381, 1.72405, 1.72454, 1.72464, 1.72477, 1.72488, 1.72541, 1.72553, 1.72562, 1.72588, 1.72625, 1.72651,
 1.72653, 1.72671, 1.72679, 1.72685, 1.72720, 1.72783, 1.72849, 1.72852, 1.72854, 1.72925, 1.72927, 1.72938, 1.72953, 1.72956, 1.72960, 1.72970, 1.72975, 1.72979,
 1.72996, 1.73014, 1.73028, 1.73034, 1.73050, 1.73056, 1.73084, 1.73085, 1.73119, 1.73137, 1.73176, 1.73278, 1.73328, 1.73337, 1.73344, 1.73345, 1.73362, 1.73377,
 1.73385, 1.73399, 1.73401, 1.73405, 1.73425, 1.73432, 1.73445, 1.73446, 1.73447, 1.73451, 1.73458, 1.73468, 1.73491, 1.73512, 1.73515, 1.73516, 1.73537, 1.73545,
 1.73553, 1.73580, 1.73581, 1.73598, 1.73611, 1.73630, 1.73635, 1.73643, 1.73658, 1.73678, 1.73694, 1.73695, 1.73698, 1.73712, 1.73713, 1.73721, 1.73746, 1.73748,
 1.73750, 1.73751, 1.73781, 1.73782, 1.73789, 1.73821, 1.73843, 1.73845, 1.73854, 1.73857, 1.73858, 1.73861, 1.73874, 1.73892, 1.74003, 1.74060, 1.74062};

  CHashMap<double, int> Index; // Будем по double-ключу хранить int-значения.
  
  for (int i = ArraySize(Array) - 1; i >= 0; i--)
    Index.Add(NormalizeDouble(Array[i], 5), 0); // Каждую цену массива используем в качестве ключа.
    
  // Все это было подготовкой, чтобы продемонстрировать поведение ниже.
  
  const double Price = 1.75141; // Берем новую цену.
  
  if (Index.Add(Price, 0)) // Если получилось добавить ее в качестве ключа.
  {
    int Value = 0;

    Print(Index.TryGetValue(Price, Value)); // (false) Проверяем, получается ли посмотреть данные по этому ключу.
    
    if (Index.Add(Price, 0)) // Пробуем повторно добавить в качестве ключа
      Print(Index.TryGetValue(Price, Value)); // (true) Проверяем, получается ли посмотреть данные по этому ключу.
  }
}


false
true

Parece que supuestamente se añade una clave, pero no se puede leer nada de ella. Sin embargo, en cuanto se vuelve a añadir la clave, ¡se puede leer!

¿Esto es una bolsa?


Si sustituye el precio1,75141 del ejemplo por otro, funcionará correctamente.


Fue infernalmente difícil detectar este comportamiento en un código enorme sin depurar y crear un ejemplo tan conciso.

 
Vasiliy Sokolov #:

Siempre que sea posible, inicialice la colección con un número predeterminado de elementos. Aunque no los conozcas con exactitud, da una cifra aproximada: será de gran ayuda para el algoritmo.

En el ejemplo anterior he intentado establecer la capacidad a través del constructor. A partir de un determinado valor de capacidad, el ejemplo empieza a funcionar correctamente.

Pero creo que esto es una coincidencia.

 
fxsaber #:

He encontrado un comportamiento muy inusual en CHashMap.


Parece que supuestamente se añade una clave, pero no se puede leer nada de ella. Sin embargo, en cuanto se vuelve a añadir la clave, ¡se puede leer!

¿Esto es una bolsa?


Si sustituye el precio1,75141 del ejemplo por otro, funcionará correctamente.


Fue infernalmente difícil detectar este comportamiento en un código enorme sin depurar y crear un ejemplo tan conciso.

Arreglado, estará en la versión de hoy.
 
MetaQuotes #:
Corregido, estará en la versión de hoy.

Gracias. Veo la edición.


 
fxsaber #:

En el ejemplo anterior, intenté establecer la capacidad a través del constructor. A partir de un determinado valor de capacidad, el ejemplo empieza a funcionar correctamente.

Pero creo que esto es una coincidencia.

Sí, hay un fallo tras otro. Le aconsejo encarecidamente que no utilice el Genérico.

1...28293031323334353637
Nuevo comentario
Razón de la queja: