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

Nouveau commentaire
 
Alexey Oreshkin:

Un excellent exemple théorique ! En pratique, quelqu'un a-t-il déjà effectué des milliers de transactions ?

p.s. Je n'essaie pas de prouver que c'est de la merde et que personne n'en a besoin. J'essaie de comprendre la valeur pour le commerce réel. Je ne suis pas un théoricien en général, mais un pur praticien.

Il ne s'agit pas de 1000 échanges ou de seulement 10. Le fait est que nous écrivons un code court, qui fonctionne aussi efficacement avec 10 ou 1000000..... transactions.
 

Décrire brièvement la mise en œuvre actuelle deCHashMap:

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;

     .................................

     .................................

  }

Tout d'abord, découvrons ce qu'estEntry<TKey,TValue>.
Essentiellement, il s'agit d'un nœud, comme dans CLinkedList, qui contient :

- placé dans un conteneur de clés et de valeurs
- valeur de hachage en cache pour la clé - hash_code
- next - "pointeur" vers la prochaineEntry<TKey,TValue> pour résoudre les collisions par liste à sens unique


m_entries[] - tableau de "cellules" où la clé et la valeur ajoutées, le hash_code, le suivant sont placés. La taille du tableau correspond à la capacité.
m_count - indique l'indice de la première cellule inutilisée dans m_entries. La valeur initiale est 0, elle augmente jusqu'à la capacité, puis elle reconstruit toutes les matrices en augmentant la capacité et la taille de toutes les matrices.
m_buckets[] - tableau d'index sur m_entries[]. La valeur par défaut est -1. La taille du tableau correspond à la capacité.


Pas de collision, ajout d'une valeur unique au conteneurCHashMap :

  1. Calculer le hash par clé, obtenir le hash_code
  2. Mettre la clé, la valeur, le code de hachage dans m_entries[] par index m_count. (next = -1 car l'exemple n'a pas de collisions)
  3. Mettre dans m_buckets[] par hash_code % (ArraySize(m_buckets)) la valeur de l'index de l'élément qui vient d'être ajouté dans m_entries[] (c'est m_count).
  4. Augmenter m_count de +1

Sans collisions, récupérer la valeur par clé dans le conteneurCHashMap:

  1. Calculer le hachage à partir de la clé, obtenir le code de hachage (hash_code)
  2. De m_buckets[], par hash_code % (ArraySize(m_buckets)) obtenir la valeur qui est un index du tableau m_entries[]
  3. En utilisant l'index obtenu m_buckets[hash_code % (ArraySize(m_buckets))], obtenez notre valeur du tableau m_entries[].

Résolution des collisions :

Pour des clés différentes, il peut arriver que hash_code_key_1 % (ArraySize(m_buckets)) soit égal à hash_code_key_2 % (ArraySize(m_buckets)) C'est ce qu'on appelle une collision.
Tous les éléments avec collision ajoutés à m_entries[] sont liés par la liste à une connexion avec next (voir structureEntry<TKey,TValue>)
Et m_buckets[] pointe toujours vers l'index du premier élément de tête dans cette liste de collisions.
Nous n'obtenons pas une grande liste avec des collisions, mais de nombreuses petites listes.


Collision, obtenir la valeur par clé dans le conteneurCHashMap:

  1. Sur la clé, on calcule le hash, on obtient le hash_code.
  2. En utilisant l'index hash_code % (ArraySize(m_buckets)), récupérer la valeur du tableau m_entries[].
  3. Nous pouvons voir que la valeur de next n'est pas égale à -1, ce qui indique qu'il y a une collision.
  4. Parcourir la liste à entrée unique constituée d'éléments de m_entries[] et comparer la valeur recherchée et la clé enregistrée pour vérifier l'égalité.


Suppression d'une valeur du conteneurCHashMap:

- Lors de la suppression d'une cellule dans m_entries[], aucune suppression n'est effectuée ; la cellule est marquée comme libre et hash_code = -1.
- les cellules libres forment leur propre liste de cellules libres (en utilisant le même suivant de Entry<TKey,TValue>),m_free_list
- les cellules libres sont d'abord utilisées pour ajouter de nouvelles valeurs au conteneur.
-m_free_count est utilisé pour contrôler le nombre actuel de cellules libres.


Reconstruction de la table de hachage (processus visant à augmenter la capacité) :

- reconstruire uniquement lorsque la capacité est remplie à 100%.
- La taille de capacité suivante est prise dans la liste :

const static int  CPrimeGenerator::s_primes[]=
  {
   3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
   1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
   17519,21023,25229,30293,36353,43627,52361,62851,75431,90523,108631,130363,156437,
   187751,225307,270371,324449,389357,467237,560689,672827,807403,968897,1162687,1395263,
   1674319,2009191,2411033,2893249,3471899,4166287,4999559,5999471,7199369
  };

- Les tableaux m_entries[] et m_buckets[] sont incrémentés.
- m_buckets[] est vidée et complètement remplie, sur la base des données de m_entries[] (valeur de hachage en cache pour la clé - hash_code)



Forum sur le trading, les systèmes de trading automatisés et les tests de stratégie

Generic Class Library - bugs, description, questions, utilisation et suggestions

Sergey Dzyublik, 2017.12.09 01:12

Je me suis familiarisé avec l'implémentation deCHashMap
. Honnêtement, j'ai aimé.


Il y a plusieurs suggestions d'améliorations possibles :

1) À mon humble avis, l'implémentation contient une sélection de capacité pas tout à fait correcte - à la fois la taille initiale 3 et les suivantes lors de la reconstruction de la table de hachage.
Oui, il est exact qu'un nombre premier doit être choisi pour l'uniformité de la distribution.
Cependant, l'implémentation de CPrimeGenerator ne répond pas aux attentes et contient des omissions de nombres premiers.
L'objectif d'un tel "générateur" est clair : fournir un facteur d'incrémentation de l'ordre de 1,2 avec la génération automatique de nombres premiers.
Toutefois, ce coefficient n'est-il pas trop faible ? En C++ pour les vecteurs, le coefficient est généralement de 1,5 à 2,0, selon la bibliothèque (car il affecte fortement la complexité moyenne de l'opération).
La solution pourrait être un coefficient constant suivi d'un arrondi au nombre premier via une recherche binaire d'une liste de nombres premiers.
Et une taille initiale de 3 est trop petite, nous ne vivons pas au siècle dernier.

2) Actuellement, la table de hachage est reconstruite (Redimensionnement) uniquement lorsque la capacité est remplie à 100% (toutes les m_entries[] sont remplies).
De ce fait, il peut y avoir un nombre important de collisions pour les clés qui ne sont pas distribuées de manière très uniforme.
En option, envisagez d'introduire un facteur de remplissage qui réduit de 100% la limite nécessaire pour effectuer une reconstruction de la table de hachage.


 
Alexey Oreshkin:

En pratique, quelqu'un a-t-il déjà opéré sur des milliers de transactions ?

Oui, des millions d'appels d'histoire sur une passe sont pratiqués par beaucoup.

 
Vasiliy Sokolov:

Sur les Forts tous les premiers.

C'est clair.

Envoyer des commandes par l'algorithme hft et les récupérer pour les analyser sont des choses différentes. Ces hachages ne sont pas nécessaires pour l'envoi, et ils ne sont pas non plus nécessaires pour l'analyse, car ils sont analysés d'une manière différente.

Donc, sans vouloir vous offenser. Vous avez également besoin de théorie.

 
Alexey Oreshkin:

C'est clair.

Envoyer des commandes par l'algorithme hft et les récupérer plus tard pour les analyser sont des choses différentes. Vous n'avez pas besoin de ces hachages pour l'envoi, et vous n'en avez pas besoin non plus pour l'analyse, car ce n'est pas ce qui est analysé.

Donc, sans vouloir vous offenser. Nous avons également besoin de théorie.


Je n'utilise pas de lave-vaisselle, j'utilise une éponge.
Sans vouloir vous offenser. Les lave-vaisselles sont nuls, à quoi ils servent.

 
Alexey Oreshkin:

C'est clair.

Envoyer des ordres par l'algorithme hft et les relever plus tard pour analyse sont des choses différentes. Vous n'avez pas besoin de ces hachages pour les soumettre et vous n'en avez pas besoin pour l'analyse puisque nous analysons autre chose par la suite.

Donc, sans vouloir vous offenser. Nous avons également besoin de théorie.

Quelles rancunes ? Continuez à écrire vos béquilles.

 
Sergey Dzyublik:

Brève description de l'implémentation actuelle deCHashMap

Merci, je vais l'utiliser lors de l'analyse du code source.

 
Vasiliy Sokolov:

Quelles rancunes ? Continuez à écrire vos béquilles.

Le fait est que je n'utilise pas le sujet proposé ici, et que j'essaie de comprendre si j'ai raison ou non. Je suis satisfait des tableaux associatifs ordinaires, mais je veux toujours faire mieux.
 
fxsaber:

Merci, je l'utiliserai lors de l'analyse des sources.


Omission de la vérification de l'existence de la clé dans le conteneur lors de l'ajout d'une nouvelle paire clé-valeur, exécutée en premier.
Mais ce n'est pas important.

 
Face à un message d'erreur causé par l'absence de cette
//+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TryGetValue(const int index,T &value) const

S'il vous plaît, réparez quelque chose comme ça dans tous les génériques.

1...101112131415161718192021222324...38
Nouveau commentaire
Raison: