tmcuh
Messages postés458Date d'inscriptiondimanche 22 décembre 2002StatutMembreDernière intervention18 avril 2009
-
13 mars 2008 à 10:14
gael07ol
Messages postés1Date d'inscriptiondimanche 24 novembre 2013StatutMembreDernière intervention24 novembre 2013
-
24 nov. 2013 à 10:27
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
gael07ol
Messages postés1Date d'inscriptiondimanche 24 novembre 2013StatutMembreDernière intervention24 novembre 2013 24 nov. 2013 à 10:27
Bonjour,
je cherche pour un jeu de type scrabble/anagrammes, comment trouver toutes les combinaisons possibles avec un nombre donné de lettres.
Pour l'instant, j'ai implementé une fonction qui ouvre un fichier texte contenant 311513 mots, chaque mot est lue l'un après l'autre et la fonction vérifie si ce mot peut être formé avec les lettres tirées précédement.
Cela fonctionne bien mais c'est lent (30 secondes sur un core I5 avec un SSD).
Je souhaiterais adapter cette fonction en utilisant le dictionnaire optimise : comment parcourir/lister tous les mots avec le dico optimisé ?
Cordialement.
tresorunikin13
Messages postés10Date d'inscriptionlundi 24 novembre 2008StatutMembreDernière intervention26 octobre 2010 29 août 2009 à 16:47
oui:! merci...
Mais estt-ce je me déroute? je préfère que si l'utilisateur insère un mot, dès qu'il l'indique verbe, qu'il puisse directement insérer les mots relatifs aux conjuguaisons à tous les temps possibles, de à ce verbe. Exemple, si l'user insère le verbe 'manger', au moment où il est verbe, mon programme insère automatiquement les mots mangeais, mangerai etc grace aux méthodes appropriées. mais je me demande si en utilisant des classes adjectifs, adverbes, cela ralentirai l'application.
cs_Dargos
Messages postés13Date d'inscriptionmardi 18 avril 2006StatutMembreDernière intervention27 mars 2008 29 août 2009 à 12:48
je pense qu'il faudrait déja créer une enum : public enum eWordType { Adjective, Verb, ... }
ensuite créer une propriété dans la classe Noeud : public eWordTpe? NodeType;
nullable pour que les noeud intermédiaires nepossedent pas de valeur mais que les noeuds finaux la possedent.
de plus il faudrait modifier les methodes d'insertion de mots pour qu'ils prennent en compte cette nouvelle valeur.
et pourquoi pas accélérer la recherche avec cette valeur...
d'ailleurs, les noeuds intermediaires devraient peutetre avoir une valeur combinée de l'enum contenant l'enssemble des sous-valeurs pour accélérer la recherche. mais à ce moment la, ca ralentirait l'insertion et modification. donc au choix ;)
tresorunikin13
Messages postés10Date d'inscriptionlundi 24 novembre 2008StatutMembreDernière intervention26 octobre 2010 23 août 2009 à 05:24
heu bien bon,merci à vs. je trouve ce que je fais ici...
Voilà je voudrais un peu savoir comment pouvez vous faire en sorte que les mots soient classés, genre adjectif ou verbe ou nom. C'est à dire que je suis en train de réaliser un dictionnaire pareille mais je permets à l'utilisateur de préciser si le nouveau mot qu'il insère est un adjectif ou un verbe, un nom ect... comment aborderiez-vous ceci? un peu tard mais je vous crois connecté à ce sujet!
qwerty0060
Messages postés2Date d'inscriptionmercredi 19 mars 2003StatutMembreDernière intervention31 juillet 2009 31 juil. 2009 à 13:11
j'oubliais de preciser que si le mot existait deja alors on reiterais simplement sans rien faire, j'arrive avec cette methode a ajouter 250.000 mots en 2,6sec ce qui est puissant avec le language de flash qui n'est pas optimize!!
qwerty0060
Messages postés2Date d'inscriptionmercredi 19 mars 2003StatutMembreDernière intervention31 juillet 2009 31 juil. 2009 à 13:09
Hello, j'ai implemente ta class en action script pour un projet personnel, et je trouve que ta methode ajouter_mot peut etre aussi optimise:
public function addWord(w:String):void {
var node:Node = _root;
var lgt:int = w.length;
for(var i:int = 0; i<lgt; i++){
var sub_node:Node = node.next[w.charAt(i)];
if(!sub_node) sub_node = new Node(w.charAt(i));
node = sub_node;
}
sub_node = new Node('\0');
}
en fait l'algorithme est simple:
on cherche le si caractere existe dans le noeud suivant, si celui-ci est nul (cf. if(!sub_node)) on creer un nouveau noeud avec comme lettre le caractere, on reitere, jusqu'a la fin du mot, ou on ajoute '\0'
cs_Dargos
Messages postés13Date d'inscriptionmardi 18 avril 2006StatutMembreDernière intervention27 mars 2008 20 mars 2008 à 21:40
exactement tmcuh.
en fait, quand on parle de dictionaire, c'est surtout avoir des paires clef/valeur (sinon on va plutot parler de liste).
donc à priori, il faudrait juste ajouter une valeur de type string sur les noeuds '\0'.
quand on va ajouter un mot, on l'ajoutera avec sa valeur : la methode ajouter_mot prendra donc 2 strings en parametre.
ensuite, vu de l'exterieur, on ne devrait pas avoir acces à la mecanique interne de la classe, mais n'avoir que 3 ou 4 methodes publiques comme ajouter, enlever, vider, charger_depuis_fichier. en particulier, on de devrait pas accéder à cette List<Noeud> particulierement dans la signature des methodes.
ensuite, dans le dictionaire, on va le plus souvent demander la valeur d'un mot, et une seule fois loader le dico complet. ce qui serait idéal serait d'avoir une public method qui renvoie une string valeur à partir d'une string clef.pour finir,
pour ca, il va falloir trouver quelle forme donner au fichier, vu qu'on rajoute des valeurs aux clefs : un xml, autres ?
Tmcuh, je suis bien d'accord avec toi pour dire qu'en vitesse acces, c'est surement la methode la plus efficace !
sinon, je vais encore coser un peu la chose :
peux tu predire ce qu'il va se passer si 2 threads ajoutent le meme mot au meme moment ?
si tu comptes laisser la methode ajouter_mot publique, il va surement falloir penser à la synchronisation des threads ! je te laisse y reflechir, mais tu peux te renseigner sur la classe ReaderWriterLock ;)
G33kemenT, Dargos
tmcuh
Messages postés458Date d'inscriptiondimanche 22 décembre 2002StatutMembreDernière intervention18 avril 2009 20 mars 2008 à 12:59
Dargos parle d'une gestion multi-langue, c'est à dire qu'on charge à tout moment des données (via xml ou autre) et par la suite on fera par exemple lors d'une question utilisateur MessageBox.Show(mondictionnaireFR.getMessage("LA_CLE")) ... Avec quelques lignes dans le dictionnaire le besoin ne se fait pas sentir de devoir "optimiser", mais pour les grosses applications commercial, le besoin risque de se faire sentir. C'est donc juste une adaptation de ce que tu as déjà codé, mais pour une gestion multi-langue ta technique est surrement la meilleur.
Tmcuh
aokdiallo
Messages postés9Date d'inscriptionjeudi 24 juin 2004StatutMembreDernière intervention20 mars 2008 20 mars 2008 à 04:41
DARGOS tu peux me detailler un peu plus ce que tu souhaite faire avec les textes des applications ?
Amicalement
aokdiallo
Messages postés9Date d'inscriptionjeudi 24 juin 2004StatutMembreDernière intervention20 mars 2008 20 mars 2008 à 04:37
salut DARGOS c'est vrai moi aussi je me disais c'est pas joli joli pour ajouter_mot mais je voulais juste prevenir l'utilisateur de l'existance d'un mot quand il essaye de l'ajouter une nouvelle fois.
mais bon le fait de supprimer le test existe_mot corrige cela (c'est juste qu'on aura plus d'avertissement en ajoutant un mot deja existant.)
cs_Dargos
Messages postés13Date d'inscriptionmardi 18 avril 2006StatutMembreDernière intervention27 mars 2008 19 mars 2008 à 19:10
simple et efficace, j'aime bien :)
par contre, pour etre pointilleux, je dirais que la methode "ajouter_mot" a un probleme :
cette methode est recursive, et elle appelle à chaque fois la methode "existe_mot" recursive aussi. en modifiant de tres peu et en utilisant de preference la methode "est_dans_liste", ca serait surement plus efficace.
ensuite, je ne suis pas tres concerné pas les mots croisés, mais j'utilise souvent des dictionnary pour faire des traductions des textes de l'application. vu ce que tu viens de faire, j'imagine que tu vas proposer une bonne idée ;)
cs_Warny
Messages postés473Date d'inscriptionmercredi 7 août 2002StatutMembreDernière intervention10 juin 2015 18 mars 2008 à 08:18
Pour le dico, le temps d'accès n'est pas O(1), c'est juste que tu ne vois pas la plomberie.
Si tu utilises un hashtable qui est le plus rapide, il faut quand même calculer la position à partir des éléments qui le constitue, ce qui donne une complexité en... O(n) avec n la taille du mot.
La méthode de oakdiallo est bien la plus efficace possible.
aokdiallo
Messages postés9Date d'inscriptionjeudi 24 juin 2004StatutMembreDernière intervention20 mars 2008 18 mars 2008 à 01:52
Salut Jimleouf
en fait le probleme que je me suis posé c'est de trouver un compromis entre la taille en memoire du dictionnaire et le temps d'acces.
Je suppose que pour l'acces en O(1) on aurais tous simplement pu recopier tous les mots du dictionnaire dans un Dictionary avec comme key le même mot ce qui serait enorme en taille memoire mais efficace en temps d'acces.
Mais bon si tu as une meilleure implementation (taille + temps d'acces )à me proposer ce serait avec plaisir que je l'etudierai.
Amicalement.
jimleouf
Messages postés1Date d'inscriptionsamedi 8 novembre 2003StatutMembreDernière intervention17 mars 2008 17 mars 2008 à 23:21
Bonjour AokDiallo,
ton idée du dictionnaire inspirée des graphes est très bonnes, mais le principal avantage d'un dictionnaire est l'accès en temps constant O(1), alors que la recherche dans ton cas sera en O(n) avec n la taille d'un mot.
Amicalement
cs_Warny
Messages postés473Date d'inscriptionmercredi 7 août 2002StatutMembreDernière intervention10 juin 2015 14 mars 2008 à 07:36
Y a pas que la taille comme avantage...
Quand tu rajoutes un mot dans le dico, il est forcement classé par ordre alphabétique. Et la complexité maximum du classement est égale au nombre de lettre du mot multiplié par le nombre de lettres dans l'alphabet.
aokdiallo
Messages postés9Date d'inscriptionjeudi 24 juin 2004StatutMembreDernière intervention20 mars 2008 13 mars 2008 à 16:23
Salut TMUCH et merci pour le test.
tmcuh
Messages postés458Date d'inscriptiondimanche 22 décembre 2002StatutMembreDernière intervention18 avril 2009 13 mars 2008 à 10:23
Je viens de tester l'occupation mémoire, tu divise par 2 la taille de ton dico... impressionnant :)
tmcuh
Messages postés458Date d'inscriptiondimanche 22 décembre 2002StatutMembreDernière intervention18 avril 2009 13 mars 2008 à 10:14
Code très très intéressant. Bien commenté, sauf qu'il ne s'adresse pas aux débutant mais aux initiés.
Une seule question : tu permet de renvoyé la "mémoire" utilisé par la ressource, mais ça n'exprime que la quantité, pas la place "effective". Car tu met en avant le fait que ton processus soit moins gourmand en ressource mémoire, faut-il encore le prouver :)
24 nov. 2013 à 10:27
je cherche pour un jeu de type scrabble/anagrammes, comment trouver toutes les combinaisons possibles avec un nombre donné de lettres.
Pour l'instant, j'ai implementé une fonction qui ouvre un fichier texte contenant 311513 mots, chaque mot est lue l'un après l'autre et la fonction vérifie si ce mot peut être formé avec les lettres tirées précédement.
Cela fonctionne bien mais c'est lent (30 secondes sur un core I5 avec un SSD).
Je souhaiterais adapter cette fonction en utilisant le dictionnaire optimise : comment parcourir/lister tous les mots avec le dico optimisé ?
Cordialement.
29 août 2009 à 16:47
Mais estt-ce je me déroute? je préfère que si l'utilisateur insère un mot, dès qu'il l'indique verbe, qu'il puisse directement insérer les mots relatifs aux conjuguaisons à tous les temps possibles, de à ce verbe. Exemple, si l'user insère le verbe 'manger', au moment où il est verbe, mon programme insère automatiquement les mots mangeais, mangerai etc grace aux méthodes appropriées. mais je me demande si en utilisant des classes adjectifs, adverbes, cela ralentirai l'application.
29 août 2009 à 12:48
ensuite créer une propriété dans la classe Noeud : public eWordTpe? NodeType;
nullable pour que les noeud intermédiaires nepossedent pas de valeur mais que les noeuds finaux la possedent.
de plus il faudrait modifier les methodes d'insertion de mots pour qu'ils prennent en compte cette nouvelle valeur.
et pourquoi pas accélérer la recherche avec cette valeur...
d'ailleurs, les noeuds intermediaires devraient peutetre avoir une valeur combinée de l'enum contenant l'enssemble des sous-valeurs pour accélérer la recherche. mais à ce moment la, ca ralentirait l'insertion et modification. donc au choix ;)
23 août 2009 à 05:24
Voilà je voudrais un peu savoir comment pouvez vous faire en sorte que les mots soient classés, genre adjectif ou verbe ou nom. C'est à dire que je suis en train de réaliser un dictionnaire pareille mais je permets à l'utilisateur de préciser si le nouveau mot qu'il insère est un adjectif ou un verbe, un nom ect... comment aborderiez-vous ceci? un peu tard mais je vous crois connecté à ce sujet!
31 juil. 2009 à 13:11
31 juil. 2009 à 13:09
public function addWord(w:String):void {
var node:Node = _root;
var lgt:int = w.length;
for(var i:int = 0; i<lgt; i++){
var sub_node:Node = node.next[w.charAt(i)];
if(!sub_node) sub_node = new Node(w.charAt(i));
node = sub_node;
}
sub_node = new Node('\0');
}
en fait l'algorithme est simple:
on cherche le si caractere existe dans le noeud suivant, si celui-ci est nul (cf. if(!sub_node)) on creer un nouveau noeud avec comme lettre le caractere, on reitere, jusqu'a la fin du mot, ou on ajoute '\0'
20 mars 2008 à 21:40
en fait, quand on parle de dictionaire, c'est surtout avoir des paires clef/valeur (sinon on va plutot parler de liste).
donc à priori, il faudrait juste ajouter une valeur de type string sur les noeuds '\0'.
quand on va ajouter un mot, on l'ajoutera avec sa valeur : la methode ajouter_mot prendra donc 2 strings en parametre.
ensuite, vu de l'exterieur, on ne devrait pas avoir acces à la mecanique interne de la classe, mais n'avoir que 3 ou 4 methodes publiques comme ajouter, enlever, vider, charger_depuis_fichier. en particulier, on de devrait pas accéder à cette List<Noeud> particulierement dans la signature des methodes.
ensuite, dans le dictionaire, on va le plus souvent demander la valeur d'un mot, et une seule fois loader le dico complet. ce qui serait idéal serait d'avoir une public method qui renvoie une string valeur à partir d'une string clef.pour finir,
pour ca, il va falloir trouver quelle forme donner au fichier, vu qu'on rajoute des valeurs aux clefs : un xml, autres ?
Tmcuh, je suis bien d'accord avec toi pour dire qu'en vitesse acces, c'est surement la methode la plus efficace !
sinon, je vais encore coser un peu la chose :
peux tu predire ce qu'il va se passer si 2 threads ajoutent le meme mot au meme moment ?
si tu comptes laisser la methode ajouter_mot publique, il va surement falloir penser à la synchronisation des threads ! je te laisse y reflechir, mais tu peux te renseigner sur la classe ReaderWriterLock ;)
G33kemenT, Dargos
20 mars 2008 à 12:59
Tmcuh
20 mars 2008 à 04:41
Amicalement
20 mars 2008 à 04:37
mais bon le fait de supprimer le test existe_mot corrige cela (c'est juste qu'on aura plus d'avertissement en ajoutant un mot deja existant.)
19 mars 2008 à 19:10
par contre, pour etre pointilleux, je dirais que la methode "ajouter_mot" a un probleme :
cette methode est recursive, et elle appelle à chaque fois la methode "existe_mot" recursive aussi. en modifiant de tres peu et en utilisant de preference la methode "est_dans_liste", ca serait surement plus efficace.
ensuite, je ne suis pas tres concerné pas les mots croisés, mais j'utilise souvent des dictionnary pour faire des traductions des textes de l'application. vu ce que tu viens de faire, j'imagine que tu vas proposer une bonne idée ;)
18 mars 2008 à 08:18
Si tu utilises un hashtable qui est le plus rapide, il faut quand même calculer la position à partir des éléments qui le constitue, ce qui donne une complexité en... O(n) avec n la taille du mot.
La méthode de oakdiallo est bien la plus efficace possible.
18 mars 2008 à 01:52
en fait le probleme que je me suis posé c'est de trouver un compromis entre la taille en memoire du dictionnaire et le temps d'acces.
Je suppose que pour l'acces en O(1) on aurais tous simplement pu recopier tous les mots du dictionnaire dans un Dictionary avec comme key le même mot ce qui serait enorme en taille memoire mais efficace en temps d'acces.
Mais bon si tu as une meilleure implementation (taille + temps d'acces )à me proposer ce serait avec plaisir que je l'etudierai.
Amicalement.
17 mars 2008 à 23:21
ton idée du dictionnaire inspirée des graphes est très bonnes, mais le principal avantage d'un dictionnaire est l'accès en temps constant O(1), alors que la recherche dans ton cas sera en O(n) avec n la taille d'un mot.
Amicalement
14 mars 2008 à 07:36
Quand tu rajoutes un mot dans le dico, il est forcement classé par ordre alphabétique. Et la complexité maximum du classement est égale au nombre de lettre du mot multiplié par le nombre de lettres dans l'alphabet.
13 mars 2008 à 16:23
13 mars 2008 à 10:23
13 mars 2008 à 10:14
Une seule question : tu permet de renvoyé la "mémoire" utilisé par la ressource, mais ça n'exprime que la quantité, pas la place "effective". Car tu met en avant le fait que ton processus soit moins gourmand en ressource mémoire, faut-il encore le prouver :)
Amicalement,
Tmcuh