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

Nouveau commentaire
 
Sergey Dzyublik:

Les hachages sont en moyenne O(1) si la taille du dictionnaire par rapport au nombre d'éléments attendus le permet.
Et ensuite, cela dépend des implémentations de la gestion des collisions, cela peut être par le biais d'une liste, peut-être plus subhash.....

Mon ignorance terminologique m'empêche d'entrer dans le vif du sujet. Je vais attendre des exemples. Je voudrais des informations succinctes et précises - mandats, tics et autres.

 
fxsaber:

Mon ignorance terminologique m'empêche d'entrer dans le vif du sujet. Je vais attendre des exemples. Je voudrais des informations succinctes et précises - mandats, tics et autres.


Les mandats sont hors de question. Je suis intéressé par les transactions.

 
fxsaber:

Je l'ai lu sur le wiki. Le genre de cas où vous ne comprenez pas du tout la logique du raisonnement intuitif.


365 jours, c'est la limite de la taille du dictionnaire
le nombre d'élèves dans la classe est le nombre attendu d'articles dans la collection
la coïncidence des anniversaires est une collision

 
Sergey Dzyublik:

365 jours est une limite à la taille du dictionnaire.
le nombre d'élèves dans la classe est le nombre attendu d'articles dans la collection
la coïncidence des anniversaires est une collision

Merci, cette définition terminologique est plus claire. Je ne comprends pas ce que ce "paradoxe" a à voir avec le sujet du fil de discussion ?

 
Sergey Dzyublik:

365 jours, c'est la limite de la taille du dictionnaire
le nombre d'étudiants dans la classe est prévu le nombre d'articles dans la collection
la coïncidence des anniversaires est une collision


Dans cet exemple, le hash est l'anniversaire de l'élève.
Nous avons une armoire avec 365 étagères où sont conservés les agendas des élèves.
Nous avons placé chaque journal sur une é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.
Résoudre 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-hache consiste à organiser 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 vous suggère un cours youtube de MailRu sur les algorithmes et les structures de données.

 
Sergey Dzyublik:

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

Nous avons besoin du journal intime de Petrov et nous savons quand il est né.
Maintenant par la date de naissance dans O(1) nous pouvons facilement trouver le journal de Petrov ainsi qu'un 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, à l'heure de la naissance d'un élève.


Si le sujet vous intéresse, je vous suggère un cours youtube de MailRu sur les algorithmes et les structures de données.

C'est comme ça que je l'imaginais au départ. Je ne comprends pas celle qui est surlignée. Le hachage n'est pas un index, vous pouvez donc le trouver par décalage dans un tableau de pointeurs. Tout de même, nous devrions chercher dans la liste. Et ceci est une recherche binaire avec un tri approprié.

 
fxsaber:

C'est comme ça que je l'imaginais depuis le début. Je ne comprends pas celle qui est surlignée. Le hachage n'est pas un index, vous pouvez donc le trouver par décalage dans un tableau de pointeurs. Vous devez cependant effectuer votre recherche dans une liste. Et ceci est une recherche binaire avec un tri approprié.


Les fautes de frappe verbales sont surlignées)) Et déjà corrigée.
Le hachage est un index. Il est donné à la taille du dictionnaire.

Chaque étagère a la même hauteur et, grâce au numéro de l'étagère, vous pouvez savoir exactement à quelle hauteur la chercher. O(1)

 

Le plus simple possible sur le tableau associatif #1

De nombreux algorithmes présentés dans Generic sont basés d'une manière ou d'une autre sur un tableau associatif ou un dictionnaire. C'est également l'un des deux algorithmes les plus utilisés. Je pense être proche de la vérité lorsque j'affirme que 90 % de toutes les tâches de programmation sont couvertes par les tableaux et les dictionnaires. Avant de passer à la pratique, décrivons le travail du dictionnaire de la manière la plus claire et la plus simple possible, en simplifiant volontairement certains détails.

Nous allons montrer le dictionnaire sur un exemple très simple : une liste de mots réguliers. Supposons que nous n'ayons que quelques mots, qui commencent tous par des lettres différentes de l'alphabet :

string words[] = {"apple", "cat", "fog", "dog", "walk", "zero"};

L'alphabet anglais contient 26 caractères. Créons un tableau de chaînes de caractères, de taille 26 éléments :

string dictionary[26];

Maintenant, si nous acceptons de stocker les mots dans des index correspondant à leur première lettre, nous obtiendrons un dictionnaire simple. Nous allons indexer à partir de zéro. Le mot "pomme" sera stocké dans notre dictionnaire à l'index 0, car le caractère "a" est la première lettre de l'alphabet, "chat" - à l'index 1, "chien" - à l'index 3, brouillard - occupera l'index 4, marche - index 24 et zéro - le dernier index 25.

Notez que les index 5 à 23 ne seront pas utilisés. C'est un gaspillage supplémentaire de mémoire, mais nous pouvons accéder instantanément, par exemple, au mot "walk", car nous savons que s'il existe, il est situé à l'index 24.

Écrivons notre premier dictionnaire vide :

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
string words[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   if(words[index] == NULL)
   {
      words[index] = word;
      return true;
   }
   return false;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   Add("apple");
   if(Contains("apple"))
      printf("Словарь содержит слово apple");
   else
      printf("Словарь не содержит слово apple");
  }
//+------------------------------------------------------------------+

Si nous y ajoutons le mot "pomme" et que nous le trouvons ensuite, l'opération de recherche pour accéder à ce mot sera instantanée. Parce que nous connaissons à l'avance l'index par lequel ce mot peut être trouvé. Il ne peut y avoir d'autres variantes d'index, il n'est donc pas nécessaire de parcourir toute la liste. C'est en gros la base de tous les dictionnaires.

Dans l'exemple suivant, nous allons l'améliorer pour qu'il puisse stocker les mots qui commencent par la même lettre.

 

Le plus simple possible sur le tableau associatif n°2

Il arrive que des mots différents commencent par la même lettre de l'alphabet. Si nous mettons "apple" dans notre dictionnaire précédent, et que nous essayons ensuite d'y mettre "application", cela ne fonctionnera pas. L'index 0 sera occupé par le mot apple. Dans ce cas, on parle de collision de fonctions de hachage. Notre fonction de hachage est très simple - elle renvoie le numéro du premier caractère du mot, les collisions dans cette fonction seront donc très fréquentes. Afin de stocker des mots différents, commençant par la même lettre, nous ferons une addition : nous stockerons les éléments non pas dans un tableau, mais dans un tableau de tableaux. Dans ce cas, l'index 0 contiendra un autre tableau avec deux mots : "apple" et "application" :

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
#include <Arrays\ArrayObj.mqh>
#include <Arrays\ArrayString.mqh>
CArrayString* WordsArray[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words = WordsArray[index];
   if(words == NULL)
      return false;
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return true;
   return false;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words;
   if(WordsArray[index] == NULL)
      WordsArray[index] = new CArrayString();
   words = WordsArray[index];
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return false;
   words.Add(word);
   return true;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   //ArrayResize(WordsArray, 26);
   Add("apple");
   Add("application");
   if(Contains("application"))
      printf("Словарь содержит слово application");
   else
      printf("Словарь не содержит слово application");
  }
//+------------------------------------------------------------------+

Maintenant, notre dictionnaire stocke les mots commençant par la même lettre. Mais le coût d'accès aux mots ayant la même première lettre augmente. En effet, nous devons maintenant effectuer une recherche complète de tous les mots commençant par "a" pour savoir si le mot "application" figure dans le dictionnaire ou non. Si notre fonction de hachage devait produire des nombres différents même si les mots ne diffèrent que d'un seul caractère, alors la probabilité d'essayer des mots avec les mêmes index tendrait vers zéro, et l'accès à un élément arbitraire tendrait vers o(1).. Dans les dictionnaires réels, c'est exactement ce qui se passe, les fonctions qui y sont utilisées sont à l'épreuve des collisions, nous pouvons donc dire sans risque que l'accès aux éléments de ces collections est très rapide et ne nécessite pratiquement aucune force brute.

 
Vasiliy Sokolov:

Garder le tableau associatif aussi simple que possible

Un grand nombre d'algorithmes présentés dans Generic sont, d'une manière ou d'une autre, basés sur le tableau associatif ou le dictionnaire. C'est également l'un des deux algorithmes les plus utilisés. Je pense que je serais proche de la vérité si je disais que 90% de toutes les tâches de programmation sont couvertes par les tableaux et les dictionnaires. Avant de passer à la pratique, décrivons le travail du dictionnaire de la manière la plus claire et la plus simple possible, en simplifiant volontairement certains détails.

Nous allons montrer le dictionnaire sur un exemple très simple : une liste de mots réguliers. Supposons que nous n'ayons que quelques mots, qui commencent tous par des lettres différentes de l'alphabet :

L'alphabet anglais contient 26 caractères. Créons un tableau de chaînes de caractères, de taille 26 éléments :

Maintenant, si nous acceptons de stocker les mots dans des index correspondant à leur première lettre, nous obtiendrons un dictionnaire simple. Nous allons indexer à partir de zéro. Le mot "pomme" sera stocké dans notre dictionnaire à l'index 0, car le caractère "a" est la première lettre de l'alphabet, "chat" - à l'index 1, "chien" - à l'index 3, brouillard - occupera l'index 4, marche - index 24 et zéro - le dernier index 25.

Notez que les index 5 à 23 ne seront pas utilisés. C'est un gaspillage supplémentaire de mémoire, mais nous pouvons accéder instantanément, par exemple, au mot "walk", car nous savons que s'il existe, il est situé à l'index 24.

Écrivons notre premier dictionnaire vide :

Si nous y ajoutons le mot "pomme" et que nous le trouvons ensuite, l'opération de recherche pour accéder à ce mot sera instantanée. Parce que nous connaissons à l'avance l'index par lequel ce mot peut être trouvé. Il ne peut y avoir d'autres variantes d'index, il n'est donc pas nécessaire de parcourir toute la liste. C'est en gros la base de tous les dictionnaires.

Dans l'exemple suivant, nous allons l'améliorer afin de pouvoir stocker les mots qui commencent par la même lettre.

Cette solution est parfaite. Tout est aussi simple que possible. Uniquement des fonctions, des tableaux et une organisation correcte des données. C'est de ça que je parle.
123456789101112...38
Nouveau commentaire
Raison: