Posté le 16/04/2018 18:17
. .
et à plus sur PC 
Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 340 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements
Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd
Citer : Posté le 18/04/2018 11:15 | #
J'ai compris le truc... j'ai essayé de faire une version en Basic: j'ai assigné à chaque variable de a à z lez valeurs de 1 à 26. Ensuite j'utilisé le fo ction Exp () pour dégager une valeur du mot saisi dans la recherche puis je fais comme avant, un test pour chaque résultat mais cette fois-ci uniquement avec un test de valeur. Je n'ai pas encore mis toute la base de données de la version 0.2 mais je pense grappiller un peu de vitesse. Pour connaître la valeur d'un mot pour l'ajouter a la base de données j'ai créé un autre programme qui te la donne. Tu en pense quoi..?
Ajouté le 18/04/2018 à 11:16 :
Bien sûr, je te le maj cet après midi ok
-Planétarium 2
Citer : Posté le 18/04/2018 11:31 | #
Voilà, il fallait utiliser les variables !
Cependant tu auras beaucoup de collisions parce que Exp() considère "ABC" comme un produit et le produit commute, donc tous les anagrammes auront la même valeur.
Si tu regardes l'algorithme djb2 dont j'ai parlé, c'est pas si différent :
- Tu commences avec un hash H = 5381
- Pour chaque lettre, tu récupères sa valeur de 1 à 26, C
- C+96→C (pour obtenir le codage ASCII en minuscules)
- H*33+C→H
Et à la fin, tu as un hash avec, si l'on en croit les descriptions qu'on peut trouver sur Internet, des propriétés intéressantes. Comme les mots dont on cherche les définitions sont courts, tu peux te permettre de faire une boucle pour ça. (Attention toutefois, la valeur de H peut exploser !)
Je rappelle que ce qui va être long c'est de chercher dans ton dico. Hasher n'est pas si long en comparaison. Surtout que plus tu as de collisions, plus tu dois faire du travail supplémentaire !
Si la valeur de H est trop grande avec 33 tu peux prendre un autre nombre et chercher expérimentalement ceux qui sont les plus efficaces.
Citer : Posté le 18/04/2018 11:40 | #
Donc si je te suis, le 33 c'est bien pour que l'on ait un max de valeurs differentes pour éviter les colisions.. c'est bien ça ? Ah et pour là valeur H, moi j'ai le r et il explose déjà avec un mot de 5 ou 6 lettres.. c'est pas grave. La calto c'est fait pour calculer non ?
-Planétarium 2
Citer : Posté le 18/04/2018 12:01 | #
Voilà. Pourquoi 33 marche est un épais mystère, par contre.
Le problème c'est que si H explose la calculatrice ne gardera en mémoire que les 14-15 chiffres significatifs donc tu augmentes les chances de collisions. Mais à la limite c'est pas grave. Le tout c'est de voir si ça marche bien pour *ton* dico.
Citer : Posté le 18/04/2018 12:07 | #
Ok. Apres, c'est juste le mot de la recherche qui subit une transformation. Je peu mettre une description aussi longue que je veut. Je pensais meme faire des images. Bemol, on a pas bcp de pixels en locate (21*7) mais je peut quand meme en trier qqc. Dis, quand j'affiche du texte avec les " " seulement et que ça sort de l'écran en hauteur. Ça défile très vite. Tu as un moyen pour ralentir ça.. ?
-Planétarium 2
Citer : Posté le 18/04/2018 12:18 | #
Tu peux séparer le texte en morceaux et mettre des boucles pour ralentir. Mais pas bien mieux - pour une fois que le Basic va sensiblement vite...
Citer : Posté le 18/04/2018 12:43 | #
Oui c'est vrai...
Ajouté le 18/04/2018 à 13:01 :
J'ai revu mon code, et je n'ai pas tout à fait repris l'algo djb2. J'ai juste multiplié le code du mot saisi par 33 vu qu'il fonctionne bien. Des que j'ai un peu plus de temps, je revois toute la base de données et je maj.
-Planétarium 2
Citer : Posté le 18/04/2018 13:19 | #
Tu ferais bien de relire deux-trois choses sur le hachage. Est-ce que multiplier par 33 va changer quelque chose aux collisions ? Est-ce que { 0, 1, 2... } et { 0, 33, 66... } ce serait pas la même chose avec juste plus de chiffres au fond ?
Quand je dis qu'on ne sait pas pourquoi 33 marche, ce n'est pas de la magie noire non plus. Multiplier par 33 ne va pas changer la donne parce que 33 est un nombre rose à étoiles vertes.
Citer : Posté le 18/04/2018 13:20 | #
Je vais gerdéla fonc de hachage comme je l'ai mise pour la premiere fois. Je pense que ça ira. J'ai ajouter pour la vitesse, des labels pour aller directement à la partie de la memoire du prog qui correspond aux definitions des mots commençant par la premiere lettre du mot recherché. Une recherche grossière par lettre.
Ajouté le 18/04/2018 à 13:23 :
PS: En plus les nombres générés sont déjà gros. La probabilité que je tombe sur deux fois le même est faible..
Ajouté le 18/04/2018 à 13:29 :
Oouuuu la, il y a gros débordement, tu avais raison...
Je te reprends...
-Planétarium 2
Citer : Posté le 18/04/2018 15:12 | #
Pas si faible que ça. Tente n'importe quels anagrammes, type "POULE" et "LOUPE".
Avoir des gros nombres ne suffit pas pour dire que la probabilité d'avoir deux fois le même est faible. Il faut aussi regarder comment ils sont répartis, et tu peux avoir de mauvaises surprises.
Maintenant, si tu pouvais (et tu ne peux pas parce que les hash seraient trop gros) mettre pour A-Z des nombres premiers tous distincts, tu pourrais prouver (c'est facile) que tous les anagrammes, mais seulement les anagrammes, produisent des collisions.
Citer : Posté le 18/04/2018 15:23 | #
Ah... ok. Je vais essayer d'eviter les anagrammes alors.. genre en leurs ajoutant un espace ou autre chose... finalement j'utilise une matrice pour éviter les débordements. Le matrices peuvent stocker combien de nombres apres la virgule ?
-Planétarium 2
Citer : Posté le 18/04/2018 16:38 | #
Tu n'as pas besoin d'éviter les anagrammes. Par contre, quand tu arrives sur un nombre pour lequel tu sais qu'il existe une collision, tu ressors StrCmp().
Les matrices stockent autant de chiffres que les variables habituelles. Elles te donnent juste un tableau.
Citer : Posté le 18/04/2018 16:54 | #
Voila, je l'ai maj. Je pensais ajouter les definitions des mots compliquées du site... c'est une idée...
-Planétarium 2
Citer : Posté le 18/04/2018 18:50 | #
Mais c'est très bien ça !! voilà une façon bien intelligente de gérer ton dico
Pour le hachage, utiliser Exp( est une très bonne solution, mais pas sur le mot en entier, à cause des anagrammes effectivement, et aussi à cause des trucs "D" = 4 et "BB" = 4
Par contre tu peux prendre chaque lettre de ton mot les unes après les autres, et faire ta fonction de hachage comme ça.
Je conseille d'ailleurs d'utiliser la fonction modulo pour pas dépasser une valeur, que tu definies toi même.
Autre point, à la fin tu vas avoir plein de condition If pour trouver la correspondance avec le bon mot. Tu peux découper avec d'autres conditions pour dégroissir.
If "ARGENT"
If "BETON"
If "BATEAU"
...
Tu découpes avec la première lettre du mot que tu cherches
If "AGILE"
If "ARGENT"
Fin if
If première lettre = "B"
If "BETON"
If "BATEAU"
Fin if
...
Avec peu d'exemples c'est pas flagrant, mais plus tu as de mots, plus c'est rentable
Après, pourquoi pas extrapoler avec la deuxième, puis troisième, ... lettre
PS : oublie pas mettre le mot que tape l'utilisateur en majuscule forcé avec la fonction qui va bien
Citer : Posté le 18/04/2018 18:53 | #
Avec peu d'exemple c'est pas flagrant, mais plus tu as de mots, plus c'est rentable
Il dit ça avec un petit air innocent, mais en fait si on néglige le temps que la calculatrice met à parcourir le code (sauter par-dessus les If pas vrais, etc), ça donne une structure de données qu'on appelle un radix tree (ou trie), et qui a plein de propriétés pétées.
Cette structure permet par exemple d'implémenter la méthode la plus rapide (puisque linéaire en le nombre de lettres) pour trier un ensemble de chaînes de caractères. Et elle te dit en temps linéaire sur le mot, indépendamment de la taille du dico, si le mot est dans le dico. Très pété.
Citer : Posté le 18/04/2018 19:00 | #
+1 pour 9*, au delà de 50 If à la suite, c'est vraiment intéressant de découper en un arbre. Disons que ça peut facilement faire gagner une grosse poignée de secondes suivant la taille du programme.
Et si vraiment c'est trop gros, parce que faut sauter par dessus de larges portions de code non exécuté, il faut découper en sous programmes.
Après 9* a découpé par lettres, mais tu peux découper par valeur de hash : les hashs de 0 à 10000, de 10000 à 50000, etc., à voir suivant tes valeurs et ton dictionnaire pour que les catégories soient à peu près égales en taille.
Citer : Posté le 18/04/2018 19:04 | #
Effectivement, j'ai dit avec la première lettre, mais ça s'adapte au hash
Citer : Posté le 18/04/2018 20:18 | #
Ok. Je pense rester comme je suis actuellement avec le découpage de la memoire par ordre alphabétique de première lettre en attendant d'avoir plus de mots en mémoire. Actuellement avec ces deux façons de rechercher les mots je multiplie environ par deux la vitesse de recherche. En tous cas merci. Je pense ajouter les définitions des mots compliqués presents sur le site. Histoire de faire une alternative au Casiopedia
-Planétarium 2
Citer : Posté le 18/04/2018 20:35 | #
D'ailleurs, à propos de Casiopedia
"BIBLE"⇒"Must have du bidouilleur"
Citer : Posté le 19/04/2018 13:25 | #
J'ai laissé de côté la version 0.3 de mon programme car il y avais trop de debordements avec la matrice et je l'ai refais en ne gardant que la recherche grossière par ordre alphabétique. Je lui ai ajouté un petit algo que je dit de "decoupage" pour que l'on puisse rechercher deux mot à la suite.. la vitesse est tjs la... je pense que c'plutôt pas mal.
Ajouté le 19/04/2018 à 17:21 :
Voila, j'ai déjà bien remplis le dico, et j'ai utilisé une petite astuce moi tout craché pour que vous ne quittiez pas le programme... je ne vous dirais pas laquelle..
Un peu plus serieusement, j'ai mis plusieurs mots en lien avec planete casio et le monde du programme, de la science etc
J'ai egalement mis la definition de plusieurs languages differents ainsi que de certaines bases numerales (binaires, hexa, etc)
Si vous voulez directement voir combien et lesquels j'ai mis, saissisez les mots clés "LANGUAGE DE PROGRAMMATION"
Enjoy
PS: j'ecris ce message et je maj le programme dans une ou deux minutes... il est 17h27..
Ajouté le 19/04/2018 à 17:44 :
Maj ! (dans l'entête du topic)
Ajouté le 19/04/2018 à 18:11 :
PS: J'ai créé une picture de presentation (cf le programme dans la categorie projets)
-Planétarium 2