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

Nouveau commentaire
 
Vasiliy Sokolov:

Il arrive que des mots différents commencent par la même lettre de l'alphabet. Si nous mettons "pomme" 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" :

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).. C'est exactement ce qui se passe dans les dictionnaires réels et les fonctions qui y sont utilisées sont à l'épreuve des collisions. Nous pouvons donc affirmer que l'accès aux éléments de ces collections est très rapide et ne nécessite pratiquement aucune recherche.

Je vais essayer d'apporter ma solution à cet exemple. Sans pointeurs. Un peu plus tard.
 

J'ai récemment lu un livre sur le sujet. Il s'agit de"Rattraper les algorithmes". Tout est très clairement exposé, avec des exemples.

 
Vasiliy Sokolov:

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

Veuillez le rédiger de manière succincte, sans en-tête ni entité inutile.

Par exemple, ce

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}

pourrait être écrit de manière beaucoup plus claire.

bool Contains(string word)
{
   return words[word[0]-'a'] != NULL;
}


Et encore ce code peut fonctionner différemment pour MT4/5 parce que dans MT4 le tableau est initialisé avec des valeurs NULL, et dans MT5 il peut être trash.

 
fxsaber:

Veuillez écrire de manière succincte, sans le fatras de chapeaux et d'entités superflues.

...


Catégoriquement CONTRE ! Le code doit de préférence être écrit en entier. Regardez tous les codes MQ - il y a des "caps" partout. C'est la norme.


fxsaber:

...

Et pourtant, ce code pour MT4/5 peut fonctionner différemment parce que dans MT4 le tableau est initialisé avec des valeurs NULL, et dans MT5 il peut être nul.


Qu'est-ce que cela a à voir avec l'ancien terminal ? Si vous êtes paresseux et que vous utilisez encore l'ancien, c'est votre propre problème. La communauté ne devrait pas ralentir à cause de tels fainéants.

 
Vladimir Karputov:

Regardez tous les codes MQ - il y a des "caps" partout. C'est la norme.

Fuck la norme, l'essentiel est important ici, pas le style qui prend 50% du code.

 
fxsaber:

Au diable la norme, c'est l'essentiel qui compte, pas le style qui occupe 50% du code.


La tâche principale du forum est l'EDUCATION. Le code doit donc être étendu et clair et se rapprocher le plus possible de la norme.

 
Vasiliy Sokolov:

C'est exactement ce qui se passe dans les dictionnaires réels ; les fonctions qui y sont utilisées sont résistantes aux collisions, de sorte que nous pouvons affirmer que l'accès aux éléments de ces collections est très rapide et presque sans dépassement.

En d'autres termes, pour chaque tâche, il est nécessaire de trouver un juste milieu entre la taille du dictionnaire (RAM) et la complexité de la fonction de hachage (CPU).

 
Vladimir Karputov:

L'objectif principal du forum est d'éduquer. Par conséquent, le code doit être étendu et compris

ça suffit.

aussi proche de la norme que possible.

Vous pouvez insérer vos propres en-têtes. A100 a publié des centaines de rapports dans le SD sans capuchon - c'est la norme ! Parce que c'est l'essence qui compte, pas les guirlandes.

 
Il existe une solution. Cependant, pour préserver temporairement l'intrigue, je voudrais poster l'exécutable ici. En outre, des personnes compétentes compareront les performances de ma solution et de la solution fournie par l'auteur ci-dessus. Je me demande lequel fonctionne le plus vite.
Dossiers :
Dictionary.ex5  10 kb
 
ReTeg Konow:
Il existe une solution. Cependant, pour maintenir temporairement l'intrigue en vie, j'aimerais publier l'extrait ici. En outre, des personnes compétentes compareront les performances de ma solution et de la solution fournie par l'auteur ci-dessus. Je me demande lequel fonctionne le plus vite.
Vous devez exécuter l'exécutable. Un champ de saisie apparaît. Ensuite, vous pouvez taper différents mots. S'il y a une correspondance, l'imprimante vous informe que le mot se trouve dans le dictionnaire. S'il n'y a pas de mot, vous serez informé que le mot a été ajouté au dictionnaire.
12345678910111213...38
Nouveau commentaire