DICTIONNAIRE OPTIMISE

Commentaire de tmcuh le 13/03/2008 10:23:02

Je viens de tester l'occupation mémoire, tu divise par 2 la taille de ton dico... impressionnant :)

Commentaire de Warny le 14/03/2008 07:36:06

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.

Commentaire de aokdiallo le 18/03/2008 01:52:37

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.

Commentaire de Dargos le 19/03/2008 19:10: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 ;)

Commentaire de aokdiallo le 20/03/2008 04:41:48

DARGOS tu peux me detailler un peu plus ce que tu souhaite faire avec les textes des applications ?

Amicalement

Commentaire de Dargos le 20/03/2008 21:40:19

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

Commentaire de qwerty0060 le 31/07/2009 13:11:52

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!!

Commentaire de Dargos le 29/08/2009 12:48:54

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 ;)