« Mes progs de l'IUP »
Ici on devait lire le contenu d'un fichier qui contenait des
bigrammes et les mettre dans une liste chainée.
Voir plus bas pour plus d'infos.
.__ . .
[__) _ _.|_ _ ._. _.|_ _
| \(/,(_.[ )(/,[ (_.[ )(/,...
_ _
| |__ (_) __ _ _ __ __ _ _ __ ___ _ __ ___ ___
| '_ \| |/ _` | '__/ _` | '_ ` _ \| '_ ` _ \ / _ \
| |_) | | (_| | | | (_| | | | | | | | | | | | __/
|_.__/|_|\__, |_| \__,_|_| |_| |_|_| |_| |_|\___|
|___/
Version 21.03.03
* Listing :
Makefile
arbre.cpp
arbre.h
bigramme.cpp
bigramme.h
liste.cpp
liste.h
main.cpp
* Contenu des fichiers :
==> _Makefile_ :
Contient le code pour compiler le projet. Il suffit de taper 'make' pour lancer la compilation.
Compilateur par defaut 'aCC' qui peut etre modifie (par la variable CC du Makefile).
==> _arbre.cpp_ :
Contient les fonctions pour la classe Arbre utilisees pour la methode 4.
==> _arbre.h_ :
Contient la declaration de la classe Arbre.
==> _bigramme.cpp_ :
Contient les fonctions pour la classe Bigramme. On y retrouve les fonctions principales utilisees dans le projet.
==> _bigramme.h_ :
Contient la declaration de la classe Bigramme.
==> _liste.cpp_ :
Contient les fonctions pour la classe Liste utilisees pour la methode 1.
==> _liste.h_ :
Contient la declaration de la classe Liste.
==> _main.cpp_ :
Programme principal, contient la fonction main du projet.
* Prerequis :
Une fois la compilation effectuee, 'make' va creer un fichier executable appelle 'bigramme'.
Afin que le projet soit plus portable, nous avons integre la prise en compte de parametres dans l'appel de 'bigramme'.
Syntaxe : ./bigramme [-o] [fichier_model [fichier_test]]
L'option -o enclenche l'appel de bigramme avec l'utilisation des fichiers par defaut donnes en TP.
(En l'occurence /ETD/IUP1/public/TP_RECHERCHE/data.model pour le fichier_model et /ETD/IUP1/public/TP_RECHERCHE/data.test pour data.test)
On peut egalement specifier le fichier_model en premier parametre, et eventuellement le fichier_test en deuxieme parametre.
'bigramme' propose la recherche d'un bigramme rentre par l'utilisateur ou alors de plusieurs pris a partir d'un fichier (fichier_test).
Une fois 'bigramme' lance, le menu est le suivant :
Methodes proposees :
1. Recherche sequentielle dans une liste chainee
2. Recherche sequentielle dans un tableau trie
3. Recherche dichotomique dans un tableau trie
4. Recherche par Arbre Binaire de Recherche non equilibres
5. Rechercher a partir du 2eme fichier
Quelle methode voulez-vous employer ?
Le choix compris entre 1 et 4 va demander a l'utilisateur de rentrer un bigramme, celui-ci sera ensuite recherche dans le fichier_model
rentre en parametre ou dans le fichier /ETD/IUP1/public/TP_RECHERCHE/data.model si l'option -o a ete demandee.
Le choix 5 permet de faire la recherche de tous les bigrammes situes dans le fichier_test rentre en parametre ou le fichier par defaut (option -o).
Typiquement pour le TP il faut utiliser le choix 5 puis choisir la methode souhaitee (de 1 a 4).
* Traitement du sujet :
La premiere methode (liste chainee) fut assez simple a traiter. Nous avons utilise une structure speciale (Maillon) comme information
de chaque maillon de la liste. La recherche s'effectuant sequentiellement, fut simple a mettre en place.
Pour les methodes 2 et 3 (recherche sequentielle dans un tableau trie et recherche dichotomique dans un tableau trie), le probleme
s'est pose de devoir d'abord trier le tableau. Pour cela nous avons tout d'abord tester le tri bulle. Ce tri etant plutot long
(en moyenne plus de 30 secondes), nous nous sommes reportes sur l'utilisation du tri rapide propose par une fonction C (qsort()).
Typiquement, le tri utilise par qsort() est appele "tri de Hoare" ou "tri par segmentation" ou "tri des bijoutiers" ou encore "tri rapide".
C'est certainement l’algorithme de tri interne le plus efficace. Le principe de ce tri est d’ordonner le vecteur T(0)..T(n) en cherchant
dans celui-ci une cle pivot autour de laquelle reorganiser ses elements. Ils nous auraient ete possible de faire nous même cet algorithme,
mais autant utiliser les fonctions deja presentes ! Ce tri ne prend qu'une seconde.
Nous avons cree une structure speciale (Information) qui forme le contenu de chaque case du tableau.
Une fois le tri du tableau effectue, la methode 2 ne demandait qu'une recherche sequentielle donc simple.
La methode 3 demandait une recherche dichotomique. Pour celle-ci nous avons repris l'algorithme etudie au premier semestre et adapte a la
structure qui compose le tableau.
Pour la methode 4 (arbre) nous avons repris les fonctions utilisees en TD, et nous avons fait les modifications necessaires pour que la
structure Noeud ne contienne plus de 'int' comme donnee mais la structure 'Information'. Il a fallu ensuite savoir comment nous allions
traiter la comparaison entre deux Informations.
Tres simplement nous avons :
Si (mot1 et mot2 donnes en parametre) = (mot1 et mot2 presents dans le Noeud) alors (retourner la probabilite)
Si (mot1 donne en parametre) > (mot1 present dans le Noeud) alors (aller vers le fils droit du Noeud)
Si (mot1 donne en parametre) < (mot1 present dans le Noeud) alors (aller vers le fils gauche du Noeud)
Si (mot1 donne en parametre) = (mot1 present dans le Noeud) alors (comparer mot2 sur le meme principe)
* Discussion :
==> `Prerequis` :
Les tests d'evaluation en temps sont effectues en plein apres-midi sur Casimir ...
==> `Methode 1` _Liste Chainee_ :
Temps de stockage : 1 seconde
Temps de recherche : 5 mn 7 s
Temps CPU total : 4 mn 47 s
Place memoire totale : 512016 octets
Nombre operations : 2104692890
Valeur theorique : 32000 * 200000 = 6 400 000 000 (pire des cas)
Points positifs : C'est une methode simple a mettre en place.
Points negatifs : Methode longue et laborieuse dans la recherche.
Elle utilise enormement d'opÅrations fondamentales.
==> `Methode 2` _Tableau trie (recherche sequentielle)_ :
Temps de stockage : < 1 seconde
Temps de recherche : 5 mn 15 s
Temps CPU total : 5 mn 2 s
Place memoire totale : 384012 octets
Nombre operations : 2104759691
Valeur theorique : 32000 * 200000 = 6 400 000 000 (pire des cas)
Points positifs : Methode simple a mettre en place.
Peu d'espace memoire.
Points negatifs : Le tri du tableau demande des operations supplementaires.
La recherche est longue et laborieuse.
==> `Methode 3` _Tableau trie (recherche dichotomique)_ :
Temps de stockage : < 1 seconde
Temps de recherche : 1 seconde
Temps CPU : 1 seconde
Place memoire totale : 384012 octets
Nombre operations : 2995240
Valeur theorique : log2 (32000) * 200000 = 2993156
Points positifs : L'algorithme de la dichotomie est tres connu donc assez simple a mettre en place.
Temps de recherche extremement rapide !
Espace memoire faible et peu d'operations fondamentales.
Points negatifs :
==> `Methode 4` _Arbre_ :
Temps de stockage : 10 secondes
Temps de recherche : 12 secondes
Temps CPU total : 11 secondes
Place memoire totale : 384012 octets
Nombre operations : 54875666
Valeur theorique : 32000 * 200000 = 6 400 000 000 (pire des cas)
Points positifs : methode intermediaire dans la duree du traitement, la memoire et le nombre d'operations.
Points negatifs : initialisation du modele assez long.
* Conclusion :
La methode 3 est la plus rapide et la plus legere mais pose le probleme que l'on doit connaitre la taille du fichier. De plus
le tableau doit etre prealablement trie.
![[ICO]](/icons/blank.gif){kind=icon}
![[PARENTDIR]](/icons/back.gif){kind=icon}
![[TXT]](/icons/text.gif){kind=icon}
![[ ]](/icons/unknown.gif){kind=icon}