Feedback sur programme C++Résolu

Question

Bonjour, J'ai programmé deux petits programmes. Le premier sert à écrire des lettres au hasard dans un fichier texte (seulement des lettres sans accents et minuscules dans ce cas-ci). Le second cherche dans le fichier texte résultant du premier programme des correspondances avec les mots d'un fichier dictionnaire. Dans le hasard produit par le premier programme, il est possible que des mots aient été formé. Le second programme cherche donc ces mots et les place dans un nouveau fichier texte. Mais voilà, je suis débutant, et je suis absolument certain que mon code est loin d'être optimal et pourrait être amélioré. J'aimerais donc avoir des commentaires sur ce que j'ai fait. (Je ne sais pas si j'ai le droit de demander cela ici, si non merci de me référer à un endroit où c'est permit) Premier programme : #include #include #include #include using namespace std; int main() { srand(time(0)); char un = 'a'; char deux = 'b'; char trois = 'c'; char quatre = 'd'; char cinq = 'e'; char six = 'f'; char sept = 'g'; char huit = 'h'; char neuf = 'i'; char dix = 'j'; char onze = 'k'; char douze = 'l'; char treize = 'm'; char quatorze = 'n'; char quinze = 'o'; char seize = 'p'; char dixSept = 'q'; char dixHuit = 'r'; char dixNeuf = 's'; char vingt = 't'; char vingEtUn = 'u'; char vingtDeux = 'v'; char vingtTrois = 'w'; char vingtQuatre = 'x'; char vingtCinq = 'y'; char vingtSix = 'z'; int chiffre; cout << "Getting ready..." << endl; ofstream file("file.txt", ios::out | ios::app); if (file) { while (1==1) { chiffre = (rand() % 25)+1; if (chiffre<=0 || chiffre>26) { cout << chiffre << " isn't meant to exist. Sorry for this." << endl; } if (chiffre==1) file << un; if (chiffre==2) file << deux; if (chiffre==3) file << trois; if (chiffre==4) file << quatre; if (chiffre==5) file << cinq; if (chiffre==6) file << six; if (chiffre==7) file << sept; if (chiffre==8) file << huit; if (chiffre==9) file << neuf; if (chiffre==10) file << dix; if (chiffre==11) file << onze; if (chiffre==12) file << douze; if (chiffre==13) file << treize; if (chiffre==14) file << quatorze; if (chiffre==15) file << quinze; if (chiffre==16) file << seize; if (chiffre==17) file << dixSept; if (chiffre==18) file << dixHuit; if (chiffre==19) file << dixNeuf; if (chiffre==20) file << vingt; if (chiffre==21) file << vingEtUn; if (chiffre==22) file << vingtDeux; if (chiffre==23) file << vingtTrois; if (chiffre==24) file << vingtQuatre; if (chiffre==25) file << vingtCinq; if (chiffre==26) file << vingtSix; } file.close(); } else cerr << "Hum, there's an error with the file. Please verify that you have enough disk space available." << endl; return 0; } Sur mon ordinateur, il permet d'écrire dans un fichier texte à environ 11 Mo par secondes. Second programme... #include #include #include #include using namespace std; int main() { ifstream file("file.txt"); ifstream dic("fr.dic"); if (!file && !dic) { cerr << "Neither \"dic.txt\" and \"file.txt\" exist. Please put them both in the same" << endl; cerr << "directory than the one you started this software or name them correctly." << endl; cout << "Press any key to continue..."; system("pause>nul"); return 0; } else if (!file) { cerr << "There's an error. Verify that the file \"file.txt\" exist. If it does, well damn." << endl; cout << "Press any key to continue..."; system("pause>nul"); return 0; } else if (!dic) { cerr << "There's an error with the dictionnary file. Please verify that it exist. Please" << endl; cout << "Press any key to continue..."; system("pause>nul"); return 0; } int wordMaxLenght; // Contient la valeur du nombre de lettres maximum d'un mot pour restreindre le temps de recherche string letters=""; // Variable contenant les lettres soutirées de file.txt string words=""; // Variable contenant les mots de fr.dic char transfertVariable; // Variable servant de pont entre les caractères soutirés de file.txt bool fin=false; // Contient true si la fin de "file.txt" est atteint int lettersSize; // Contient la taille de letters pour la comparer avec wordMaxLenght int startTime=0; // Contient l'heure de début du processus cout << "Define a maximum letter count for a word (the highest the slowest the process will be)" << endl; cout << ">"; cin >> wordMaxLenght; if (file) { startTime=time(NULL); // Même chose que plus haut cout << "Searching for words..." << endl; while (fin==false) { lettersSize=letters.size(); if (lettersSize==wordMaxLenght) { letters=""; file.seekg(-(wordMaxLenght-1), ios::cur); } file.get(transfertVariable); letters+=transfertVariable; ifstream dic("fr.dic"); // Une deuxième fois car la première est fermée if (dic) { bool fini=false; while(getline(dic, words) && fini!=true) { if (letters==words) { ofstream dic("words.txt", ios::app); dic << letters << " "; dic.close(); letters=""; fini=true; } } fini=false; } else { system("cls"); cerr << "There's an error with the dictionnary file. Please verify that it exist. Please" << endl; cout << "Press any key to continue..."; system("pause>nul"); return 0; } if (file.eof()==true) { fin=true; } else if (letters!=words) { file.seekg(0.5, ios::cur); // Pour avancer le curseur d'un caractère. À 1 le curseur avance de deux, donc .5 pour un caractère. } else cerr << "Well what the hell happened ? You're not supposed to see this. There's an error." << endl; } } else { system("cls"); cerr << "There's an error. Verify that the file \"file.txt\" exist. If it does, well damn." << endl; cout << "Press any key to continue..."; system("pause>nul"); return 0; } int endTime=(time(NULL)-startTime); // Contient la différence entre le temps de fin et de début pour donner combien de secondes le processus a prit à se compléter cout << "The process took " << endTime << " seconds to complete. Please check the generated file." << endl; cout << "Press any key to continue..."; system("pause>nul"); return 0; } Si une annotation plus rigoureuse serait utile, demandez et j'essayerai de la fournir. Désolé pour le "franglais" utilisé ici. Mauvaise habitude. Merci d'avoir lu, et aussi d'avance pour de l'aide, des commentaires, des corrections ou autres :) Cordialement, Alain2131

cptpingu · Answer

Bonjour. C'est bien ici qu'on peut poster des codes pour demander une "review". Donc ne t'inquiètes pas, c'est non seulement autorisé, mais aussi conseillé :). Pour tes codes, il y a effectivement de nombreuses pistes d'amélioration. Je vais supposer que tu utilises C++03 (c'est la version par défaut, même si je t'invite à utiliser la version la plus récente: C++11 qui ajoute de nombreuses choses). Conseils d'ordre général: - Évite les using namespace, c'est ultra crade, voir: http://0217021.free.fr/portfolio/axel.berardino/articles/bon-usage-using-namespace - Plutôt que srand/rand, on préférera utilisé les classes dans (uniquement en C++11). - Pour mesurer le temps, on peut utiliser les classes de (uniquement en C++11), ou alors cette classe pour C++03, compatible Windows et Linux: http://0217021.free.fr/portfolio/axel.berardino/articles/calculer-le-temps-execution - Quand on veut s'assurer qu'un code n'a pas de bug et qu'une routine fait obligatoirement ce que l'on veut, on utilise plutôt "assert" qu'un if + message "oupss désolé, ne devrait pas arriver". Cf premier code corrigé ci-dessous. - Un std::ostream est déjà un std::ostream + std::ios::out, donc l'option std::ios::out n'est pas nécessaire - Un std::ostream ou un std::istream ne nécessite pas de ".close()", car il ferme déjà le fichier à leur destruction (ce qui arrive en fin de scope). Pour vulgariser, la fermeture est automatique. Pour le premier programme: Plutôt que de faire des if dans tous les sens, il faut plutôt savoir qu'un caractère *est* un nombre. Par exemple: 'a' est équivalent à 97 dans la table ascii, 'b' à 98, etc... Pour aller de "a" à "z", on peut faire: for (char c = 'a'; c <= 'z'; ++c) std::cout << c << std::endl; ou encore for (char c = 97; c <= 122; ++c) std::cout << c << std::endl;. Donc quand tu fais ton "rand", si tu fais: rand() % 26 + 'a', alors tu es forcément entre 'a' et 'z'. Il ne te reste qu'à afficher ta lettre. Bien plus court que ta version :). Je ne suis pas fan des "while (true)", donc j'ai posé une limite que tu peux adapter (ou mieux, faire choisir à l'utilisateur). Ma proposition: #include #include #include #include #include const unsigned int LIMIT = 1500; int main() { srand(time(0)); std::cout << "Getting ready..." << std::endl; std::ofstream file("file.txt"); if (!file) { std::cerr << "Hum, there's an error with the file." << " Please verify that you have enough disk" << " space available." << std::endl; } unsigned int nb_char = 0; while (nb_char < LIMIT) { const char letter = rand() % 26 + 'a'; assert(letter >= 'a' && letter <= 'z'); file << letter; ++nb_char; } file << std::endl; return 0; } Pour le second programme, ouvrir ton fichier "dic" à chaque fois, c'est assez moyen. Le mieux, est de charger le dictionnaire dans une structure adaptée, afin de l'avoir en RAM directement. En théorie, un "trie tree" serait parfaitement adapté, mais il n'existe pas de base en C++. Un hash_set ferait aussi l'affaire (std::unordered_set), mais n'est disponible qu'à partir de C++11. Donc j'ai pris un std::set (qui est une collection garantissant qu'il n'y a pas de doublon), mais il faut savoir que ce n'est pas le plus adapté. Ensuite, il faut créer des fonctions pour éviter les répétitions et éviter les fonctions géantes qui font trop de choses. Un bon découpage de code, différencie un bon codeur d'un mauvais. Essaie de te forcer à bien découper ton code en petites fonctions. J'ai appliqué quelques petites optimisations supplémentaires, comme ne pas charger les mots du dictionnaire qui n'ont pas la taille souhaitée (moins de mots à vérifier). Quand il y a une erreur, ne renvoit pas 0 dans ton main. Le return du main représente le code d'erreur (0 voulant dire pas d'erreur). Ma proposition (je te laisse remettre un timer si tu le désires, je ne l'ai pas implémenté): #include #include #include #include #include void my_pause() { std::cout << "Press any key to continue... "; system("pause>nul"); } bool loadDictionary(const std::string& filename, std::set& set, unsigned int wordMaxLength) { std::ifstream file(filename.c_str()); if (!file) return false; std::string line; while (std::getline(file, line)) if (wordMaxLength == line.size()) // On ne met que les mots ayant la taille voulue. set.insert(line); return true; } bool read(std::istream& stream, unsigned int count, std::string& word) { std::vector result(count); // Because vector is guaranteed to be contiguous in C++03 stream.read(&result[0], count); word = std::string(&result[0], &result[count]); return stream; } bool printCorrespondingWord(const std::string& filename, const std::set& dic, unsigned int wordMaxLength) { std::ifstream file(filename.c_str()); if (!file) return false; unsigned int nb_found = 0; unsigned int current_pos = 0; std::string word; while (read(file, wordMaxLength, word)) { file.seekg(current_pos); if (dic.find(word) != dic.end()) { std::cout << "Find the word "" << word << ""! "; ++nb_found; } ++current_pos; } std::cout << "Found " << nb_found << " matching words!" << std::endl; return true; } int main() { std::set set; unsigned int wordMaxLength = 0; std::cout << "Define a maximum letter count for a word (the highest the slowest the process will be): "; std::cin >> wordMaxLength; if (!loadDictionary("fr.dic", set, wordMaxLength)) { std::cerr << "There's an error with the dictionnary file. Please verify that it exist. "; my_pause(); return 1; } if (!printCorrespondingWord("file.txt", set, wordMaxLength)) { std::cerr << "There's an error. Verify that the file "file.txt" exist. If it does, well damn. "; my_pause(); return 1; } return 0; } Améliorer votre expérience CodeS-SourceS avec ce plugin: http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

nagaD.scar · Answer

Salut ! Alors pour commencer, j'ai pas de remarque particulière en l'état, par contre quelques améliorations que tu peux importer: 1 - La sélection du caractère Tu t embêtes à avoir 26 variables pour tes caractères alors qu'existent déja=> la valeur hexa. Si tu cherche la table ascii tu remarquera que l alphabet minuscule commence à 97, ce qui implique que faire : int main(){ srand(time(0)); int chiffre; cout << "Getting ready..." << endl; ofstream file("file.txt", ios::out | ios::app); if (file) { while (1==1) { chiffre = (rand() % 25)+1; file << (char)(chiffre + 96); //96 car tu fais +1 }... revient au même que toi mais en plus simple. 2 - la recherche de mot. Là c est autre chose. Tu donnes un nombre maximum de caractères MAIS quand tu as lu le nombre de caractéres tu remets à vide ... du coup tu perds des combinaisons. Ici tu utilise un fichier de données, ce qui en soit est valable, mais dans le cas actuel tu sera limité car tu accède à ton fichier une seule fois en même temps. Ce que je te propose, et ca t'aidera dans ton apprentissage, c'est : 1 - Créer une classe "rechercheMot" (prends le nom qui te convient), qui contiendra une procédure de recherche et stockera le résultat. Par exemple : class rechercheMot { public: string sFileDico;//fichier qui contiendra ton dictionnaire de mot public string* sMotRes;//contiendra tous tes résultats //Constructeur rechercheMot(string tmpFileDic); //- - A toi de le faire, assigner le fichier renseigné à sFileDico + faire le new de ta liste //Méthode de recherche d'un mot //Info: le prefix est "th" car c'est une méthode qui sera appelée dans un thread void th_recherche( string mot ) ; //- - A toi de le faire, rechercher "mot" dans le fichier et l ajouter à la liste de résultats si tu trouve } Donc dans ton main, tu auras en premier la création de l objet de cette classe. ensuite tu parcourra le fichier généré avec la première app et tu appelera la méthode de recherche via un thread, ce qui permettra de faire des recherches en simultané. Et a la fin tu n aura plus qu'à afficher les résultats. Concernant la lecture en soit, pour ne rien perdre if faut : - une pile fifo (ta chaine qui contiendra tes caractères=> un nouveau caractère "poussera le plus ancien") - A chaque nouveau caractè, tester toutes les combinaisons. C'est a dire que si tu as un max lenght de 4 caractères, tu veux tester la chaine "ABCD" => il faut que tu test "A", puis "B","C" et "D", "AB","BC","CD","ABC" et "BCD". Bien que tu tests bien l ensemble des combinaisons (au début j avais cru que non mais je m etais trompé), cette methode t'évitera le va et vient du curseur dans ton fichier. (utilise "letters.substr(1)" ) Pour aller plus loin, tu parras ensuite faire un index de ton fichier pour accélérer la recherche (par exemple le prmier mot qui commence par "T" est à la ligne x, etc.) naga

nagaD.scar · Answer

Le temps que j ecrives tu avais répondu =P par contre pour cette partie: Pour le second programme, ouvrir ton fichier "dic" à chaque fois, c'est assez moyen. Le mieux, est de charger le dictionnaire dans une structure adaptée, afin de l'avoir en RAM directement. Dans le cas d un dictionnaire de données, je ne suis pas trop d accord car il peu vite être très lourd, je serai plutot d'avis d'indexer que charger en mémoire mais bon =p

cptpingu · Answer

Dans le cas d un dictionnaire de données, je ne suis pas trop d accord car il peu vite être très lourd, je serai plutot d'avis d'indexer que charger en mémoire mais bon =p
Je t'assure que c'est la meilleure méthode :). Ton fichier a beau être gros, passé une certaine taille, si tu ne le mets pas en RAM, ça sera tellement lent que tu n'as aucune chance d'avoir une réponse. L'indexation sur un fichier voudrait dire que tu réaccèdes au fichier, ce qui est ultra lent (ce n'est pas tout à fait vrai à cause du buffer de std::istream, mais tu finiras quand même pas "taper" dans le fichier, donc appels systèmes coûteux + accès au fichier qui l'est tout autant).
Enfin, ce n'est pas parce que tu mets en mémoire un fichier, que tu mets toute la taille de celui-ci dedans ! Si tu fais un "trie tree" (https://en.wikipedia.org/wiki/Trie, mais on utilise généralement la version compacte de celui-ci, appelée radix tree: https://en.wikipedia.org/wiki/Radix_tree), un dictionnaire même gigantesque, ne prendra que très peu de place. Ça dépend de ta structure de données.

Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

nagaD.scar · Answer

Vis a vis de l indexation j'étais plutot dans l indée de gestion de curseur pour accéder directement à un emplacement (pas de chargement, une lecture directe sur le disque donc pas de lenteur issue de la taille du fichier). 
Je ne connaissais pas le nom de ces algo, bien que le principe oui, donc merci pour l 'info =P 
Ensuite c'est vrai que dans ma tête un dictionnaire de données fera facilement 20Go, ce qui n est pas vrai ici car on ne va rechercher que des suites de caractères existantes (je crois que dans la langue francaise on dépasse pas les 100 000 mots donc bon c'est pas un gros fichier =p)

cptpingu · Answer

Vis a vis de l indexation j'étais plutot dans l indée de gestion de curseur pour accéder directement à un emplacement (pas de chargement, une lecture directe sur le disque donc pas de lenteur issue de la taille du fichier).

J'avais compris l'idée, mais c'est justement un accès disque qui coûte ultra cher !

Pour info, pour bien te rendre compte de ce que ça coûte:

Latency Comparison Numbers--------------------------L1 cache reference 0.5 nsBranch mispredict 5 nsL2 cache reference 7 ns (14x L1 cache)Mutex lock/unlock 25 nsMain memory reference 100 ns (20x L2 cache, 200x L1 cache)Compress 1K bytes with Zippy 3,000 nsSend 1K bytes over 1 Gbps network 10,000 nsRead 4K randomly from SSD 150,000 nsRead 1 MB sequentially from memory 250,000 nsRound trip within same datacenter 500,000 nsRead 1 MB sequentially from SSD 1,000,000 ns (4X memory)Disk seek 10,000,000 ns 10,000 us (20x datacenter roundtrip)Read 1 MB sequentially from disk 20,000,000 ns (80x memory, 20X SSD)Send packet CA->Netherlands->CA 150,000,000 ns
En gros, entre l'accès RAM (0.25 ms par Mo) et l'accès disque (20 ms par Mo) tu as un facteur de plus de 80 (et "seulement" 4 si tu as du SSD).
Et en plus, je ne compte pas la dedans l'appel système utilisé, qui coûte plus cher qu'une fonction "normale".

Imagine maintenant la différence de performance, entre ta version indexée sur le disque et une version indexée en RAM (pour comparer ce qui est comparable, on imagine que les deux algos sont identiques). Tu auras un facteur de 80, ce qui est loin d'être négligeable.


Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

nagaD.scar · Answer

Ah oui oui je suis d'accord sur le fait que la vitesse de l un à l autre n'a rien a voir, par contre je ne connaissais pas le ratio réel (je le pensais un peu moins important par contre).

Je serai curieux de voir la ram nécessaire en utilisant ta méthode ...

 pour 100 000 mots, si on prend 4 lettres par mots et qu'on charge directement en ram on tourne autour des 350/400 mo. 

Bon ensuite arbitrairement je vais dire que sur les 400 000 caractères (100 000 mots donc) on peut réduire de moitié le nombre de caractéres stockés en mémoire (suffix communs etc.) donc en gros on vas demander 200mo de ressources à notre mémoire, ce qui n'est pas grand chose aujourd’hui.
Je vais essayer de prendre un peu de temps pour trouver de quoi faire des stats, c'est plutôt intéressant je trouves ^^.

nagaD.scar · Answer

Ah au temps pour moi y a beaucoup plus de mots en fait : http://www.pallier.org/ressources/dicofr/liste.de.mots.francais.frgut.txt


(mais la on a toutes les déclinaisons donc bon) .. si j ai le temps je les traiterai pour me faire une idée et je redirai ^^

cptpingu · Answer

Si on ne considère pas les "overhead", 100 000 mots de 4 lettres, ça donne 400 000 chars. 1 char c'est 1 octet. On aura donc besoin de 400 000 octets, soit... 400 Ko :).

nagaD.scar · Answer

ah p***** je suis a l ouest aujourd'hui xD j'ai sauté le kilo x]  (rien a voir avec une ex =p)
j ai remarqué aussi (c est en fait super logique mais ce ne m est pas venu de suite a l esprit) que plus la quantité est grande, plus il y a de suffixes communs et du coup on se retrouve avec un graph de conso qui tends vers une limite. J'ai pas eu le temps de me faire mon algo, mais je le ferai =p

Alain2131 · Answer

Bonjour, En premier lieu, je m'excuse de la réponse tardive. Les devoirs, le travail et le collège demandent du temps :) J'aimerais (et je vais) vous remercier, nagashima et cptpingu, pour vos réponses et votre temps alloué à les construire ^^ Donc merci =P Revenons au sujet initial. Pour la version du C++ que j'utilise, je dois bien avouer que je ne sais pas vraiment ce que j'utilise. Je suis débutant, et les connaissances que j'ai acquis proviennent du site de tutoriels Le Site du Zér0, nouvellement devenu OpenClassrooms (je n'ai lu que les premières parties <.<). Donc je me promène plus ou moins, disons "à l'aveugle" sur le sentier de l'apprentissage. Cette question peut paraître idiote, mais comment utilisons-nous une version ou l'autre du C++ ? On ne fait qu'utiliser d'autres fonctions ? Pour ce qui est des espaces de noms, j'en prends bonne note, et je modifierai cela. Si je comprends bien, un "assert" fait ce que je fais, mais en mieux, dans le sens où il écrit un message pré-enregistré en cas d'erreur et termine le programme automatiquement ? std::ios::out -> comprit. .close() -> comprit. Pour l'utilisation de l'ASCII -> comprit. Pour ce qui est du second programme maintenant... Bonne idée pour les fonctions. Cela évitera beaucoup de répétitions pour la même chose. @nagashima Mettre le fichier dictionnaire dans une variable string, n'est-ce pas déconseillé ? Ou alors j'ai mal vu ? Donc, tu proposes qu'en premier lieu je charge le fichier contenant les caractères dans un string et le fichier dictionnaire dans un autre string et qu'ensuite je fasse les tests ? Suivant ces indications, je produirai une nouvelle version que je posterai ici. Malheureusement, puisque les devoirs s'accumulent, je n'ai pas le temps de travailler là-dessus pour les jours qui suivent. Dès que possible, je vais mettre une version, je l'espère "améliorée", dans ce post. Merci beaucoup à vous deux :) Cordialement, Alain2131.

cptpingu · Answer

Bonjour Alain.

Pas de souci pour la réponse tardive. Sache qu'il n'y a pas de "temps limite" pour répondre. Pour apprendre le C++, je te déconseille fortement le tutorial mis sur le site du zéro. Il est complètement dépassé :(. La plupart des membres de ce site le critique d'ailleurs vivement. A tel point, que l'un d'entre eux a décidé d'écrire son propre tutoriel C++ que je recommande: http://guillaume.belz.free.fr/doku.php?id=programmez_avec_le_langage_c

Si tu n'as pas touché aux options de compilation, tu dois être en C++03 (le standard) qui date de... 2003 :p. La dernière version stable en date est le C++11 (de 2011, donc). Sous Linux, avec gcc, on ajoute un -std=C++11, sous Windows, ça va dépendre de ton compilateur. Je t'invite à vérifier la documentation de celui-ci sur internet (c'est généralement aisé de trouver comment le configurer).

Pour les assert, tu as bien compris. C'est effectivement cela.

cptpingu · Answer

@nagashima: Finalement, j'ai fait le bench, et en ai profité pour implémenter un radix. Je l'ai posté ici:
http://codes-sources.commentcamarche.net/source/101351-completion-de-texte-via-un-radix-tree 

La conclusion est:
  - Pour optimiser la taille prise en ram: une simple vecteur trié est très efficace.
  - Pour optimiser la vitesse: Un hash set.
  - Le radix est plutôt correct pour cette tâche (dire si un mot est présent ou non), mais ce n'est pas sa spécialité (ce serait plutôt de donner tous les mots préfixés par un autre rapidement). La mémoire prise est proche d'un simple vecteur, mais la recherche est plus rapide qu'une recherche dichotomique dans un tableau. En revanche, le hash set reste loin devant en terme de vitesse (mais potentiellement aussi en terme de consommation mémoire).

nagaD.scar · Answer

Je viens de voir c'est plutot intéressant ^^ Bon du coup ca ne sert a rien que je le fasse (mais je le ferai quand même MUHAHAHA), ce qui serai pas mal c'est de tester avec 2 ou 3 autres fichiers a chaque fois plus lourd et voir si on pourrai pas établir une formule (du coup un graph par mode de recherche pour déterminer le plus intéressant en fonction de la taille du dico). En tout cas merci ^^

nagaD.scar · Answer

@Alain2131
@nagashima Mettre le fichier dictionnaire dans une variable string, n'est-ce pas déconseillé ? Ou alors j'ai mal vu ? 

C'était un peu le point que l on discutait avec cpt: moi j'étais pas pour mais finalement vu la taille à traiter ca ne pause aucuns soucis (pour dev sur nos plateformes actuelles, si ton programme "mange" 500 Mo de ram aujourd’hui ca ne pose pas de problème. 
Par rapport au post de cpt, je dirai que le chargement en mémoire sera plus interessant dans ton cas (je pense que ca change si on s attaque a des dico réellement conséquents ... mais a vérifier -> ce qui serai sympas c'est d avoir les différentes techniques en place, et en fonction de la taille du fichier, ta recherche sera par lecture directe ou par chargement en mémoire, par exemple).

cptpingu · Answer

@Alain2131:
@nagashima Mettre le fichier dictionnaire dans une variable string, n'est-ce pas déconseillé ? Ou alors j'ai mal vu ?

À vrai dire, ni moi, ni Nagashima n'avons parlé de mettre un fichier texte dans une seule std::string. Et je te déconseille de le faire. On met ses données dans des structures qui s'y prêtent bien (par exemple mettre chacun des mots lus dans le fichier dans un tableau de std::string).

Nous débattions sur deux points:
 - Quelle serait la structure de données la plus adaptée pour une recherche rapide, et qui prendrait peu de place en mémoire ?
 - Est-ce envisageable d'avoir ces données sur disque plutôt qu'en RAM ?

@nagashima: Si on veut vraiment avoir un algo (pas trop lent) avec des data sur disque, on peut partir sur un BTree (attention ce n'est pas un arbre binaire, mais un arbre auto-équilibré, comme les AVL, https://en.wikipedia.org/wiki/B-tree). Cet arbre général dont les éléments internes à un noeud sont limités à une certaine taille, est trié. Il a la particularité d'avoir une "hauteur" optimisée, et donc on limite le nombre d'accès aux noeuds. Si chaque noeud est un accès fichier (parce que l'on mettrait le tableau d'éléments interne à un noeud dans un fichier), alors le nombre d'accès disque serait en moyenne de "log(taille du tableau)". Ce ne serait pas la structure la plus rapide, mais en limitant au maximum le nombre d'accès disque, on pourrait gérer des données gigantesques avec un coût acceptable.
C'est ce qu'utilise MySQL, si je ne m'abuse.

Il s'avère que j'ai déjà implémenté ce type d'arbre (insertion mais pas suppression, la suppression est assez "hard" à gérer et il me restait pas mal de bugs dessus). Peut être que je le publierais aussi un jour :p.


Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

nagaD.scar · Answer

juste, je relève le type string ... c'est vrai que dans ma tête je suis de suite partis sur des liste type string, du coup je te rejoins =p

Oui le btree représente bien ce dont a quoi je pensais (j ai un manque cruel de l'existant ... mauvaises habitudes du c sur microcontroleur, on a tendance à tout créer à la main ^^) => des points d entrée qui pointent vers d'autres, etc. 
La limite de hauteur en soit est acceptable, car on pourrai aisément se limiter à ( je le dis au hazard) 10 caractères "de base" pour le dispatch ( je penses que le nombre de possibilitées restantes seraient tellement restreintes que le temps de parcours "final" serai négligeable ... on pourrai aussi faire par syllabe je penses)) ... enfin bref on est en dev donc des solutions c est pas ce qui manque ! =D 



Sinon je sais pas si je vais avoir le temps de tester pour le moment, plein de taff en ce moment .. (et je t avoues qu'après 8/9h de code quand je rentre, je préfère faire autre chose =p). En tout cas le sujet est plutôt intéressant .. et je serai aussi curieux de voir les vitesse en ssd (bon on pourrai le calculer en théorie mais bon^^).

Feedback sur programme C++

17 réponses

Votre réponse

Discussions similaires