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

Nouveau commentaire
  
//+------------------------------------------------------------------+
//|                                              CompareFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\IComparable.mqh>
//+------------------------------------------------------------------+
//| Compares two objects and returns a value indicating whether one  |
//| is less than, equal to, or greater than the other.               |
//+------------------------------------------------------------------+
int Compare(const bool x,const bool y)
  {
   if(x>y)
      return(1);
   else if(x<y)
      return(-1);
   else
      return(0);
  }


La fonction est déclarée globalement. Pour cette raison, il y a un conflit avec leur comparaison par les utilisateurs.

'Compare' - function already defined and has body

Pour réduire les conflits de noms, l'auteur pourrait-il faire de toutes les fonctions auxiliaires globales de Generic des public-static-methods ?

 

fxsaber:

Pour réduire les conflits de noms, l'auteur pourrait-il faire de toutes les fonctions auxiliaires globales de Generic des public-static-methods ?

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

Bogue de compilation : 'operator=' - la structure a des objets et ne peut pas être copiée

fxsaber 2018.09.10 11:00 2018.09.10 10:00:13 RU
Alexey Navoykov:
C'est pour le moment. Si vous voulez inclure la bibliothèque de quelqu'un, vous découvrirez que l'auteur écrit aussi "primitif" que vous, en utilisant les mêmes noms de classes et de fonctions.

Je vais les clouer avec des macros.

Et les macros ?
 
A100:
Et les macros ?

Je ne parlais pas de moi.

 

J'ai lu toutes les pages de la discussion mais je ne comprends toujours pas comment l'utiliser ?

Quelqu'un peut-il me donner des exemples ?

 
Vladimir Pastushak:

J'ai lu toutes les pages de la discussion mais je ne comprends toujours pas comment l'utiliser ?

Quelqu'un peut-il me donner des exemples ?

Oublie ça. Vous ne pouvez pas l'utiliser tel qu'il est maintenant. Utilisez plutôt le standard CObject + CDictionary. Pour la plupart des tâches, c'est suffisant.

 
Vasiliy Sokolov:


ClasseDescription
CHashMapUn ensemble clé-valeur. Permet d'insérer, de récupérer et de rechercher efficacement des éléments en fonction de leur clé. La clé doit être unique. Par exemple, CHashMap peut trouver instantanément une commande avec un numéro spécifié, où le numéro est utilisé comme clé.

Question sur la récupération d'une valeur par clé. Dans le code de la bibliothèque, cette méthode ressemble à ceci

//+------------------------------------------------------------------+
//| Find index of entry with specified key.                          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
int CHashMap::FindEntry(TKey key)
  {
   if(m_capacity!=NULL)
     {
      //--- get hash code from key
      int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
      //--- search pair with specified key
      for(int i=m_buckets[hash_code%m_capacity]; i>=0; i=m_entries[i].next)
         if(m_entries[i].hash_code==hash_code && m_comparer.Equals(m_entries[i].key,key))
            return(i);
     }
   return(-1);
  }

Les outils de navigation ME (ALT+G et CTRL+-) par source refusent de fonctionner dans cette bibliothèque. Il est donc très difficile de retracer la logique. En particulier, je n'ai pas encore trouvé la valeur initiale dans la boucle en surbrillance. Mais il est entendu que s'il y a une vitesse, cette valeur doit être bien inférieure au nombre de touches.


Veuillez clarifier l'idée, quelle est la vitesse atteinte dans cette fonction ? La surenchère est clairement présente. Mais apparemment c'est court pour une raison quelconque.


SZ J'ai parcouru mon débogueur étape par étape. Tout est clair dans l'exemple TKey = int : m_bucket[Array[i]] = i. Seules les collisions lorsque Array[i] == Array[j] (i != j) ne sont pas claires.

 
fxsaber:

La question porte sur l'obtention de la valeur par la clé. Dans le code de la bibliothèque, cette méthode ressemble à ceci
Veuillez clarifier l'idée, qu'est-ce qui rend cette fonction rapide ? Le dépassement est évidemment présent. Mais apparemment c'est court pour une raison quelconque.

À un moment donné, j'ai passé en revue et décrit le fonctionnement deCHashMap
. Vous devez rechercher les entrées, probablement dans ce fil de discussion.

 

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

Bibliothèque de classes génériques - bugs, description, questions, particularités d'utilisation et suggestions

Sergey Dzyublik, 2017.12.11 13:41

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 le conteneur clé et valeur
- hash_code - une valeur de hachage en cache pour la clé
- next - "pointeur" vers l'entrée suivanteEntry<TKey,TValue> dans le but de résoudre les collisions dans une liste à connexion 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 d'augmentation de 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)


Comportement décrit à partir de2017.12.11
 Actuellement, peut avoir ajouté/modifié certains détails/coefficients.

 
Sergey Dzyublik:

J'ai à un moment donné démonté et décrit le fonctionnement deCHashMap
. Vous devez chercher les entrées, probablement dans ce fil de discussion.

Je l'ai trouvé sur

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

Bibliothèque des classes génériques - erreurs, descriptions, questions, particularités d'utilisation et suggestions

Sergey Dzyublik, 2017.12.07 14:21


Dans cet exemple, le hash est la date de naissance de l'élève.
Nous avons une armoire avec 365 étagères contenant les journaux intimes des élèves.
Nous avons placé chaque journal sur l'étagère correspondant à l'anniversaire de l'élève.

Nous avons besoin du journal de l'élève Petrov et nous savons quand il est né.
Maintenant, grâce à la date de naissance dans O(1), nous pouvons facilement trouver le journal de Petrov, ainsi que le journal de tout autre étudiant.
L'exception est lorsque deux élèves ont la même date d'anniversaire - cela s'appelle une collision.

Résoudre une collision, c'est utiliser les informations supplémentaires pour trouver lequel de deux ou plusieurs journaux nous avons besoin.
La résolution de collisions par le biais d'une liste consiste simplement à parcourir toutes les entrées de la collision une par une pour trouver une correspondance. Déchirez chaque journal et voyez à qui il appartient.
Une sous-rubrique organise une table de hachage des éléments impliqués dans la collision, mais selon un critère différent. Par exemple, selon l'heure de naissance de l'élève.


Si le sujet vous intéresse - je conseille un cours de MailRu sur youtube sur les algorithmes et les structures de données.

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

Bibliothèque des classes génériques - erreurs, description, questions, particularités d'utilisation et suggestions

Sergey Dzyublik, 2017.12.08 14:40

Les bases de ce sujet sont pour les paresseux :
https://www.slideshare.net/mkurnosov/6-32402313

En réalité, c'est beaucoup plus compliqué et cela est abordé dans la littérature pertinente ou dans les bons cours d'"algorithmes et structures de données".


Merci, le débogage a aidé. Il existe de petites listes pour les collisions. J'ai parcouru le fil et j'ai été horrifié. Il s'avère que j'étais dans le sujet...

 
Sergey Dzyublik:
Comportement décrit à partir de2017.12.11

A partir de maintenant, il se peut que certains détails/coefficients aient été ajoutés/changés.

Merci beaucoup ! Votre description m'a beaucoup aidé.

1...161718192021222324252627282930...38
Nouveau commentaire
Raison: