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

Nouveau commentaire
 
Renat Fatkhullin:

Presque impossible et si vous en rencontrez un, l'accès reste super efficace.

La collision à tout niveau d'efficacité est mauvaise. Merci pour la réponse. Je garderai cela à l'esprit.

 
fxsaber:

La collision à tout niveau d'efficacité est mauvaise. Merci de votre réponse. Je garderai cela à l'esprit.

Par définition, les hashmaps ne sont pas sans collision.

 
fxsaber #:

Question sur les collisions. Est-il possible d'entrer en collision dans un tel cas ?

Si 27 000 enregistrements ont été produits.

Vous obtiendrez constamment des collisions, surtout lorsque la collection s'agrandit (se redimensionne). Puisque le hachage est en plus tronqué au numéro de gang, et qu'il y en a toujours un nombre limité (idéalement égal à un).

Conclusions :

1. Ce n'est pas la stabilité cryptographique de la fonction de hachage qui importe à la carte, c'est sa vitesse. La fonction de hachage doit simplement fournir un bon caractère aléatoire et c'est tout.

2. Le redimensionnement est à éviter par tous les moyens. C'est le redimensionnement qui provoque la principale baisse, et non les collisions de la fonction de hachage. Dans la mesure du possible, initialisez toujours la collection avec un nombre prédéfini d'éléments. Même si vous ne les connaissez pas exactement, donnez un chiffre approximatif - cela aidera grandement l'algorithme.

3. Les collisions sont un mécanisme régulier de compactage. Par le biais de collisions, il est possible de stocker trois enregistrements avec des id, disons, 159, 4'569'209, 29'459'876 dans un tableau de longueur trois, plutôt que de longueur 30 000 000, même si les deux dernières valeurs tombent toutes les deux dans le gang avec l'index 2.

 
Vasiliy Sokolov #:

2. Le redimensionnement est à éviter par tous les moyens. C'est le redimensionnement, et non les collisions de fonctions de hachage, qui constitue le principal inconvénient. Dans la mesure du possible, initialisez la collection avec un nombre prédéfini d'éléments. Même si vous ne les connaissez pas exactement, donnez un chiffre approximatif - c'est une aide précieuse pour l'algorithme.

Veuillez montrer par l'exemple.

Je n'utilise que ça pour l'instant.

//+------------------------------------------------------------------+
//| 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 #:

Veuillez me montrer un exemple.

Je n'utilise que ça pour l'instant.

Lorsque vous créez une collection CHashMap, utilisez l'un des constructeurs qui accepte le paramètre de capacité. Voir mon article sur CDicionary pour plus de détails sur les performances lors du redimensionnement. Il existe une présentation complète de cet algorithme.

 

J'ai trouvé un comportement très inhabituel dans 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

Il apparaît qu'une clé est censée être ajoutée, mais rien ne peut être lu à partir de celle-ci. Cependant, dès que la clé est à nouveau ajoutée, elle devient lisible !

C'est un SAC ?


Si vous remplacez le prix1.75141 dans l'exemple par un autre, cela fonctionnera correctement.


Il était très difficile de détecter ce comportement dans un code énorme sans déboguer et de créer un exemple aussi concis.

 
Vasiliy Sokolov #:

Dans la mesure du possible, initialisez toujours la collection avec un nombre prédéterminé d'éléments. Même si vous ne les connaissez pas exactement, donnez un chiffre approximatif - cela sera d'une grande aide pour l'algorithme.

Dans l'exemple ci-dessus, j'ai essayé de définir la capacité par le biais du constructeur. A partir d'une certaine valeur de capacité, l'exemple commence à fonctionner correctement.

Mais je pense que c'est une coïncidence.

 
fxsaber #:

J'ai trouvé un comportement très inhabituel dans CHashMap.


Il apparaît qu'une clé est censée être ajoutée, mais rien ne peut être lu à partir de celle-ci. Cependant, dès que je rajoute la clé, il devient lisible !

C'est un SAC ?


Si vous remplacez le prix1.75141 dans l'exemple par un autre, cela fonctionnera correctement.


Il était extrêmement difficile de détecter ce comportement dans un code énorme sans déboguer et de créer un exemple aussi concis.

Corrigé, ce sera dans la version d'aujourd'hui.
 
MetaQuotes #:
Corrigé, sera dans la version d'aujourd'hui.

Merci ! Je vois la modification.


 
fxsaber #:

Dans l'exemple ci-dessus, j'ai essayé de définir la capacité via le constructeur. A partir d'une certaine valeur de capacité, l'exemple commence à fonctionner correctement.

Mais je pense que c'est une coïncidence.

Oui, il y a un pépin sur un pépin. Je déconseille fortement l'utilisation de Générique.

1...2829303132333435363738
Nouveau commentaire