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

Nouveau commentaire
 

Exécutez ceci

#include <Generic\ArrayList.mqh>
#include <Generic\HashMap.mqh>

CHashMap<int, int> MagicsByDeals;

#define  AMOUNT 1000000

template <typename T>
int Test( T &Object )
{
  int Res = 0;
  
  for(int i = 0; i < AMOUNT; i++)
  {
    int Tmp = 0;
    
    if (Object.TryGetValue(i, Tmp))    
      Res += Tmp;
  }
  
  return(Res);
}

#define  BENCH(A)                                                              \
{                                                                             \
  const ulong StartTime = GetMicrosecondCount();                              \
  A;                                                                          \
  Print("Time[" + #A + "] = " + (string)(GetMicrosecondCount() - StartTime)); \
} 

void OnStart()
{   
  CArrayList<int> CollectionList;
  CHashMap<int, int> CollectionHash;
  
  for(int i = 0; i < AMOUNT; i++)
  {      
    CollectionHash.Add(i, i);
    CollectionList.Add(i);
  }
  
  BENCH(Print(Test(CollectionList)));
  BENCH(Print(Test(CollectionHash)));
}


et j'ai obtenu ceci.

1783293664
Time[Print(Test(CollectionList))] = 24819
1783293664
Time[Print(Test(CollectionHash))] = 91270


CArrayList est plus rapide que la variante de hachage. Je suis entré dans les entrailles de CArrayList, et il y a ceci

template<typename T>
class CArrayList: public IList<T>
  {
protected:
   T                 m_items[];
   int               m_size;

Je me sens trompé maintenant. CArrayList s'est avéré être une enveloppe pour un tableau habituel. Je pensais que c'était une liste normale avec des pointeurs Prev/Next, mais cela ressemble à ceci

template<typename T>
bool CArrayList::TryGetValue(const int index,T &value)
  {
//--- check index
   if((uint)index<(uint)m_size)
     {
      //--- get value by index
      value=m_items[index];
      return(true);
     }
   return(false);
  }
 
fxsaber:
Outre les algorithmes proprement dits pour travailler avec des structures, il y a le problème du choix du bon conteneur en fonction des spécificités de la tâche.
 
Combinateur:
Outre les algorithmes de travail avec les structures elles-mêmes, il y a aussi le problème du choix du bon conteneur en fonction des spécificités de la tâche.

L'interface peut donc être la même pour différentes implémentations. Une certaine déception, non pas à cause de l'interface, mais de l'implémentation spécifique - le tableau. Comparé au hachis, c'est le paradis et la terre.

 
fxsaber:

Je me sens trompé maintenant. CArrayList s'est avéré être une enveloppe pour un tableau normal. Je pensais que c'était une liste normale avec des pointeurs Prev/Next, mais voilà


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

Algorithmes, méthodes de résolution, comparaison des performances

Sergey Dzyublik, 2017.12.10 20:52


Quel genre de SGBD, que dites-vous à un homme qui ne connaît rien auxstructures de données.
S'il n'y a pas de concept de ArrayList (vecteur du C++), de quoi pouvons-nous parler ici......


C'est plus votre inattention ici...
Lire toute la liste disponible -https://www.mql5.com/ru/docs/standardlibrary/generic

CArrayList est un analogue de std::vector du C++.
CLinkedList est très probablement un analogue de std::list du C++.

 
fxsaber:

Exécutez ceci

et j'ai obtenu ceci.

CArrayList est plus rapide que la variante de hachage. Je suis entré dans les entrailles de CArrayList, et il y a ceci

Je me sens trompé maintenant. CArrayList s'est avéré être une enveloppe pour un tableau habituel. Je pensais que c'était une liste normale avec des pointeurs Prev/Next mais cela ressemblait à ceci

Historiquement, List n'est pas du tout une feuille - c'est un tableau. Donc, c'est bon. Si vous obtenez une liste en générique, elle sera probablement appelée LinkedList ou quelque chose comme ça.

 
fxsaber:

Une certaine frustration, non pas avec l'interface, mais avec l'implémentation spécifique - le tableau.

Eh bien... ce conteneur est un tableau (c'est à dire un analogue du vecteur en C++), et le tableau natif de mql est très bon, donc arraylist est plus une réflexion après coup, un peu plus pratique à utiliser.
 

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.09 01:12


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

1) À mon humble avis, l'implémentation contient un choix de capacité pas tout à fait correct - à 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éduirait de 100 % la limite nécessaire à la reconstruction de la table de hachage.

1) Le facteur de croissance du volume (capacité) n'est pas égal à 1,2, la méthode CPrimeGenerator::ExpandPrime est utilisée pour calculer le nouveau volume dans CHashMap :

int CPrimeGenerator::ExpandPrime(const int old_size)
  {
   int new_size=2*old_size;
   if((uint)new_size>INT_MAX && INT_MAX>old_size)
      return INT_MAX;
   else
      return GetPrime(new_size);
  }

Dans cette méthode, l'ancienne taille de la collection est multipliée par deux, puis nous trouvons le nombre simple le plus proche du sommet pour la valeur résultante et le retournons comme nouveau volume.

Concernant la valeur initiale de la capacité - je suis d'accord, elle est très faible.

Mais d'un autre côté, il y a toujours des constructeurs, où vous pouvez spécifier explicitement la capacité initiale :

class CHashMap: public IMap<TKey,TValue>
  {
public:
                     CHashMap(const int capacity);
                     CHashMap(const int capacity,IEqualityComparer<TKey>*comparer);
  }

Je ne vois donc pas l'intérêt de changer quoi que ce soit ici.

2) L'ajout d'un paramètre de facteur de remplissage permettrait vraiment d'éviter les collisions dans certains cas. Le plus susceptible d'être mis en œuvre.

 
Roman Konopelko:

1) Le coefficient de capacité n'est pas égal à 1,2, pour calculer le nouveau volume dans CHashMap, on utilise la méthode CPrimeGenerator::ExpandPrime :

Dans cette méthode, l'ancienne taille de la collection est multipliée par deux, puis pour la valeur résultante, nous trouvons le nombre premier le plus proche du sommet et le renvoyons comme nouveau volume.

Concernant la valeur initiale de la capacité - je suis d'accord, elle est très faible.

Mais d'un autre côté, il y a toujours des constructeurs, où vous pouvez spécifier explicitement la capacité initiale :

C'est pourquoi je ne vois pas de raison de changer quelque chose ici.

2) L'ajout du paramètre de facteur de remplissage permettra vraiment d'éviter les collisions dans certains cas. Il est fort probable qu'elle sera mise en œuvre.

Roman, je crois que tu as mal compris. Maintenant, certaines classes ne contiennent même pas les méthodes les plus nécessaires. Avez-vous déjà essayé de les utiliser ? Prenez CRedBlackTree, par exemple, l'implémentation classique d'un arbre rouge-noir. Algorithme plutôt cool mais sans la possibilité d'itération. Qu'est-ce que vous entendez par là ? Il y a beaucoup d'autres choses dont vous pourriez avoir besoin mais que personne n'a pris la peine de mettre en œuvre pour une raison quelconque. Le truc GetHashCode est horrible. Désolé, mais ce n'est pas au niveau de MQ !

 
Vasiliy Sokolov:

Roman, je ne pense pas que tu fasses la bonne chose là. Or, certaines classes génériques ne contiennent même pas les méthodes les plus nécessaires. Avez-vous essayé de les utiliser ? Prenez par exemple CRedBlackTree - une implémentation classique d'un arbre rouge-noir. Algorithme plutôt cool mais sans la possibilité d'itération. Qu'est-ce que vous entendez par là ? Il y a beaucoup d'autres choses dont vous pourriez avoir besoin mais que personne n'a pris la peine de mettre en œuvre pour une raison quelconque. Le truc GetHashCode est horrible. Désolé, mais ce n'est pas le niveau de MQ !

Je suis bien conscient du besoin d'itérateurs pour toutes les collections de modèles de la bibliothèque Genric, mais sans la possibilité de créer des classes imbriquées et l'héritage multiple des interfaces, vous ne pouvez pas les mettre en œuvre correctement.

J'aimerais entendre des commentaires plus spécifiques sur GetHashCode.

 
Roman Konopelko:

...

Quant à GetHashCode, j'aimerais entendre des remarques plus précises.

Problème

De toute évidence, GetHashCode ne peut pas être mis en œuvre correctement dans un environnement MQL5 personnalisé. En effet, tous les objets ne sont pas accessibles. Et si l'implémentation fonctionne bien pour les membres primitifs comme double int, pour les objets complexes (classes, structures et même énumérations) le hachage est calculé par nom. Si nous avons des milliers de CObjects ou même ENUM_something_that, alors CHashMap et CHashSet dégénéreront en LinkedList :

#include <Generic\HashSet.mqh>
//+------------------------------------------------------------------+
//| Безобидное перечисление, но может быть класс или структура       |
//+------------------------------------------------------------------+
enum ENUM_NUMBER
{
   NUMBER_FIRTS,  // First
   NUMBER_SECOND, // Second
   NUMBER_THIRD   // Third
};
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
{
   CHashSet<ENUM_NUMBER> set_enum;
   for(int i = 0; i < 3; i++)
      set_enum.Add((ENUM_NUMBER)i);
   //-- Поздравляю, мы выродились в LinkedList.... 
   for(int i = 0; i < 3; i++)
   {
      //-- Здесь дикий оверхед по производительности, который тчательно скрывается...
      string is = set_enum.Contains((ENUM_NUMBER)i) ? " присутствует " : " отсутствует ";
      //...
   }
}

Nous ne pouvons pas éviter cela car tout ce que nous avons au niveau de l'utilisateur est le nom de l'objet :

//+------------------------------------------------------------------+
//| 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));
     }
  }

Par conséquent, les hachages de tous les objets de types complexes sont égaux les uns aux autres et le code de recherche implique ici une énumération complète des tableaux :

//+------------------------------------------------------------------+
//| Determines whether a set contains the specified element.         |
//+------------------------------------------------------------------+
template<typename T>
bool CHashSet::Contains(T item)
  {
//--- check buckets
   if(ArraySize(m_buckets)!=0)
     {
      //--- get hash code for item      
      int hash_code=m_comparer.HashCode(item);
      //--- search item in the slots       
      for(int i=m_buckets[hash_code%ArraySize(m_buckets)]-1; i>=0; i=m_slots[i].next)
         if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,item))
            return(true);
     }
   return(false);
  }

En fait, c'est tellement important que cela va à l'encontre de l'intérêt d'utiliser tous les génériques à la racine. Le fait est que, dans la plupart des cas, vous devez associer ou stocker des objets complexes : énumérations, structures ou classes. Si vous deviez opérer uniquement avec des types simples, vous pourriez vous contenter de quelque chose de plus simple.


Solution

De toute évidence, MQL5 est un langage de programmation personnalisé à sécurité intrinsèque fonctionnant dans une machine virtuelle interne. Quelque chose comme Net. Cela signifie que l'accès nécessaire aux objets existe toujours, mais à un niveau plus systémique. D'où,peut-être écrire la fonction système GetHashCode avec le prochain prototype :

int GetHashCode(void sample);

Comment cela doit-il fonctionner ? Tout d'abord, il doit être omnivore et rapide. Il devrait donner une distribution uniforme. Par exemple :

int hash = GetHashCode(3);
// hash = 3

hash = GetHashCode(3.14159);
// hash = 2039485

enum EType{E1, E2, E3};
hash = GetHashCode(E2);
// hash = 2

class C1{};
C1* class1 = new C1();
hash = GetHashCode(class1);
//hash = 39203847

struct S1{};
S1 struct1;
hash = GetHashCode(struct1);
//hash = 83928342

Cette fonction pourrait être située dans la section des fonctions du système. Je ne vois pas d'autres solutions.

Je ferai d'autres suggestions concernant les interfaces, l'héritage multiple et d'autres aspects de l'héritage C++ un peu plus tard.
1...111213141516171819202122232425...38
Nouveau commentaire
Raison: