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

 

Depuis le 6 décembre 2017, la livraison standard de MetaTrader 5 comprend des classes dites génériques qui mettent en œuvre des algorithmes efficaces pour le stockage et la récupération des données. Ce fil de discussion est créé pour décrire ces classes, des exemples de travail avec elles et des suggestions pour améliorer leur travail.

Qu'est-ce qu'une classegénérique? Les classesgénériques sont des classes modèles spéciales qui peuvent stocker des types de données personnalisés. L'identification du type est effectuée au moment de la compilation, ce qui permet d'obtenir des performances élevées.

Pourquoi les classes génériques ? En règle générale, les programmeurs débutants ne connaissent qu'un seul type de collection : un tableau. Or, il existe de nombreuses tâches pour lesquelles l'utilisation d'un tableau est inefficace. Imaginons que nous disposions d'un tableau composé d'un million d'identifiants uniques, par exemple un millier de commandes. Comment pouvons-nous vérifier si, dans ce millier de commandes, il y a une commande portant le numéro N ? Si nous utilisons l'une des classes génériques, cette tâche peut être exécutée presque instantanément, en un temps constant qui ne dépendra pas du nombre d'éléments parmi lesquels la recherche aura lieu. Il existe d'autres tâches pour lesquelles l'algorithme correct de la collection générique peut être plus rapide que l'algorithme inventé par un programmeur.

Algorithmes génériques. Vous trouverez ci-dessous un tableau des classes génériques, accompagné d'une brève description de leur fonction :

ClasseDescription de la classe
CArrayList.Un tableau, avec répartition automatique de la taille. Permet de tirer parti d'un tableau sans avoir à contrôler ce qui en sort.
CHashMap.Un ensemble clé-valeur. Permet d'insérer, d'extraire 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é lorsque le numéro est utilisé comme clé.
CHashSetEnsemble d'éléments uniques. Il permet de faire les mêmes choses que CHashMap, mais ne nécessite pas de clé. Les éléments stockés dans cette collection ne doivent pas être répétés. Il permet également la recherche, l'extraction et l'ajout instantanés d'un élément.
CLinkedListUne liste doublement liée. Elle permet d'insérer et de supprimer facilement des éléments. Toutefois, la recherche de l'élément souhaité prend un temps qui dépend linéairement du nombre d'éléments de la liste.
CQueueTas. Organise une file d'attente de type FIFO
CStackPile. Organise une file d'attente de type LIFO
CRedBlackTreeArbre noir rouge. Permet d'insérer, d'extraire et de retrouver rapidement (en temps logarithmique) des éléments. Contrairement à CHashMap et CHashSet, il permet d'implémenter efficacement des algorithmes de relation supplémentaires tels que more than, less than, between, etc.
CSortedMapEnsemble trié par clé. Stocke les valeurs clé-valeur. Dans ce cas, la clé est triée.
CSortedSetEnsemble trié par valeur. Stocke un ensemble ordonné de valeurs.

Nous continuerons plus tard à examiner les caractéristiques de mise en œuvre de ces classes.

 
Vasiliy Sokolov:

Imaginons que nous ayons un tableau d'un million d'identifiants uniques, par exemple un millier de commandes. Comment vérifier si dans ce millier de commandes, il y a une commande avec le numéro N ? Si nous utilisons l'une des classes génériques, cette tâche peut être accomplie presque instantanément, en un temps constant, qui ne dépend pas du nombre d'éléments que nous recherchons.

Je ne connais pas du tout le sujet. Mais le surlignage semble illogique.

 

Malheureusement, la bibliothèque vient d'être libérée et est encore brute. J'ai déjà trouvé la première erreur dans ce document (je vais mettre en évidence les erreurs par marqueur) :

Erreur dans CSortedSet :

//+------------------------------------------------------------------+
//| Class CSortedSet<T>.                                             |
//| Usage: Represents a collection of objects that is maintained in  |
//|        sorted order.                                             |
//+------------------------------------------------------------------+
template<typename T>
class CSortedSet: public ISet<T>
  {
   ...
   bool              TryGetMin(T &min)    { return(m_tree.TryGetMin(min)); }
   bool              TryGetMax(T &max)    { return(m_tree.TryGetMin(max)); }
   ...
  }

La méthode TryGetMax renvoie l'élément minimum au lieu de l'élément maximum, de même que TryGetMin

 
fxsaber:

... Mais le surlignage semble illogique.

Pourquoi ça ?

 
Vasiliy Sokolov:

Pourquoi ça ?

Faire des hachages, les trier dans l'ordre croissant. Mais la recherche sera là de toute façon.

 
fxsaber:

Je ne connais pas du tout le sujet. Mais le surlignage semble illogique.

temps moyen O(1) pire O(n) et la performance dépend fortement du hachage.
 
fxsaber:

Faire des hachages ...

Définissons la terminologie. Rien n'est instantané. Toute opération prend du temps. Quand je dis instantané, je simplifie pour que les programmeurs novices me comprennent. Strictement parlant, il existe plusieurs classes de complexité, les principales que nous allons traiter sont les suivantes :

  • Complexité constante cO(1).
  • Logarithmique : cO(log n).
  • Linéaire : cO (n).
  • Algorithmes nécessitant un temps d'exécution non linéaire.

J'ai délibérément introduit un signe c - comme une sorte de constante qui apparaît lors du calcul du hash et d'autres manipulations techniques. Mais dans ce cas, la discussion sur l'optimisation de la constantec est hors sujet de ce fil. Nous nous intéressons ici uniquement aux classes génériques et à leur application dans la pratique.

 
fxsaber:

Faites des hachages, triez-les dans l'ordre croissant. Mais il y aura une recherche dans tous les cas.

Combinateur:
Temps moyen O(1) pire O(n) et la performance dépend fortement du hachage.

+

p.s. Pour illustrer, voici un exemple où cette même performance tombera à O(n) si vous ne manipulez pas CHashMap correctement.

 

Je suggère de simplifier les noms - de les rendre plus logiques. Par exemple, CArrayList est-il un tableau ou une liste dans mql5, une implémentation des deux ?

Tout cela est source de questions et de confusion. IMHO, nous devrions utiliser stl et non C# ou Java. Ou alors, enlevez le C devant, et laissez-le être juste ArrayList.


Si vous faites des noms normaux :

- la lisibilité augmentera de plusieurs fois.

- vous aurez votre propre style spécifique de mql5.

- les débutants pourront immédiatement naviguer dans le code (car le stl est inclus dans le standard)

 
Vasiliy Sokolov:

...

Si vous pouvez donner des exemples, par exemple sur la recherche parmi des milliers d'offres.