DICTIONNAIRE OPTIMISE
tmcuh
Messages postés
458
Date d'inscription
dimanche 22 décembre 2002
Statut
Membre
Dernière intervention
18 avril 2009
-
13 mars 2008 à 10:14
gael07ol Messages postés 1 Date d'inscription dimanche 24 novembre 2013 Statut Membre Dernière intervention 24 novembre 2013 - 24 nov. 2013 à 10:27
gael07ol Messages postés 1 Date d'inscription dimanche 24 novembre 2013 Statut Membre Dernière intervention 24 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.
https://codes-sources.commentcamarche.net/source/46038-dictionnaire-optimise
https://codes-sources.commentcamarche.net/source/46038-dictionnaire-optimise
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