Embed Size (px)
Citation preview
Conception et implémentation de logiciels (avec des exemples de B.
Kernighan et R. Pike « La programmation en pratique »)
Vladimir Makarenkov(Université du Québec à Montréal)
2
Introduction
• La conception est l’activité qui permet de rattacher les spécifications au codage et au débogage.
• La conception est un problème vicieux.
• La conception de structures de données est le point crucial dans le processus de création d’un programme.
• La conception sous entend l’élaboration d’une solution conceptuelle satisfaisant aux besoins plutôt que la mise en œuvre de la solution.
3
La conception
• Est un processus sans rigueur.
• Est une affaire de négociation et de priorité.
• Suppose des restrictions.
• N’est pas déterministe.
• Est un processus heuristique.
• Est une science nouvelle.
4
Caractéristiques d’une bonne conception
• Complexité minimale• Facilité de maintenance• Couplage modéré• Extensibilité• Réutilisabilité• Haut niveau de fan-in• Niveau de fan-out faible ou moyen• Portabilité• Dépouillement• Stratification• Technique standard
5
Les techniques de conception
• L’itération
• Diviser pour conquérir
• Les approches :
– ascendante : partir du simple vers le complexe;
– descendante : partir du complexe vers le simple.
• Le prototypage expérimental
• La conception collaborative
6
Problème
• Générer du texte aléatoire se lisant bien.
• En émettant des lettres ou des mots aléatoires, le résultat n’aura aucun sens.
• Pour obtenir de meilleurs résultats, il faut utiliser un modèle statistique mieux structuré :
– fréquence d’apparition de phrases entières;
– où trouver ce genre de statistiques?
7
Problème
• Prendre un gros texte et l’étudier en détail.
• On peut utiliser tout texte et générer à partir de ce modèle un texte aléatoire possédant des statistiques similaires à l’original.
• Entrée/Sortie.
• Algorithme de la chaîne de Markov.
8
Algorithme de la chaîne de Markov
• Entrée: une séquence de phrases qui se chevauche.
• L’algorithme divise chaque phrase en deux parties :– Un préfixe composé de plusieurs mots.– Un suffixe d’un seul mot qui suit le préfixe.
• Il émet des phrases en sortie en sélectionnant aléatoirement le suffixe qui suit le préfixe conformément aux statistiques.
9
Algorithme de la chaîne de Markov (2)
• Des phrases de trois mots fonctionnent bien.
• Un préfixe de deux mots est employé pour sélectionner le suffixe :
Initialiser les variables w1 et w2 avec les 2 premiers mots.
Imprimer w1 et w2
Boucle:Sélectionner aléatoirement w3, l’un des successeurs du préfixe w1w2
dans le texte.
Imprimer w3.
Remplacer w1 et w2 par w2 et w3.Répéter la boucle.
10
Algorithme de la chaîne de Markov (3)
• Exemple: Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious. (end).
Préfixes Suffixes qui suiventShow your
your flowcharts
flowcharts and
flowcharts will
your tables
will be
be mystified.
be obvious.
flowcharts tables
and will
conceal
be
and and
mystified. obvious.
Show
(end)
11
Algorithme de la chaîne de Markov (4)
• L’algorithme commencera par imprimer Show your pour choisir aléatoirement soit flowcharts soit tables.
• S’il sélectionne tables, le mot suivant sera and.
• Se poursuit jusqu’à ce que suffisamment de sorties aient été générées ou que la marque (end) devienne suffixe.
12
Choix d’une structure de données
• Combien d’entrées voulons nous traiter ?
• A quelle vitesse le programme devrait s’exécuter ?
• L’algorithme doit voir toutes les entrées avant de commencer à générer la sortie.
• Il faut stocker la totalité des entrées sous une forme quelconque.
13
Choix de structure de données
• Première possibilité.
• Lire les entrées et les stocker sous forme d’une longue chaîne de caractères.
• Pour faciliter la décomposition des entrées en mot, nous pouvons stocker les mots sous forme de tableaux de pointeurs de mots.
• Problème: cela signifie qu’il faut balayer 100 000 mots en entrée pour générer chaque mot.
14
Choix de structure de données (2)
• Seconde possibilité.
• Stocker les mots uniques en entrée.
• Stocker en même temps les endroits où ces mots apparaissent dans le texte.– Permet de faciliter la localisation des mots qui
suivent.
• Possibilité d’employer une table de hachage.
• Il faut pouvoir rapidement localiser tous les suffixes.
15
Choix de structure de données (3)
• Besoin d’une structure de données qui représente mieux un préfixe et les suffixes associés.
• Le programme comportera deux passages :– un passage en entrée pour construire la structure de données
représentant les locutions;– un passage en sortie qui se sert de la structure de données pour
générer la sortie aléatoire.
• Lors des deux passages il faudra rechercher un préfixe rapidement :– dans celui d’entrée pour mettre à jour ses suffixes;– dans celui de sortie pour sélectionner aléatoirement un des suffixes
possibles.
• Cela suggère une table de hachage dont les clés sont des préfixes et les valeurs sont les suffixes correspondants.
16
Choix de structure de données (4)
• Nous prendrons un préfixe de deux mots.
• Le nombre de mots du préfixe ne doit pas affecter la construction.
• Le programme doit pouvoir manipuler toutes les longueurs de préfixe.
• État : Le préfixe et l’ensemble de tous ses suffixes possibles.
• Que se passe-t-il si une locution apparaît deux fois « je veux lire »?– Représenter cela en plaçant 2 fois « lire » dans la liste des
suffixes correspondant;– ou une seule fois avec un compteur associé défini à 2.– La première représentation est plus facile car ajouter un suffixe
ne nécessite pas de vérifier d’abord s’il y est.
17
Choix de structure de données (5)
• Il faut choisir comment représenter les mots.
• Stocker sous forme de chaîne de caractères individuelles.– Mais cela exige de nombreuses répétitions car certains mots
apparaissent plusieurs fois dans un texte.
• Utiliser une seconde table de hachage de mots uniques. Cela accélérerait également le hachage des préfixes.– Possibilité de comparer des pointeurs au lieu de caractères
individuels.– Les chaînes de caractères uniques possèdent des adresses
uniques.
18
Construction de la structure de données en C
• Définir des constantesenum {
NPREF = 2, /* nombre de mots pour le préfixe */
NHASH = 4093, /* taille de la table de hachage état */
MAXGEN = 10000 /* maximum de mot générés */
};
• Le préfixe peut être stocké sous forme d’un tableau de mots.
• Les éléments de la table de hachage seront représentés sous forme d’un type de données State, en associant la liste de suffixes au préfixe.
19
Structure de données en Ctypedef struct State State;typedef struct Suffix Suffix;
struct State { /* préfixe + liste de suffixes */char *pref[NPREF]; /* mots préfixes */Suffix *suf; /* liste de suffixes */State *next; /* le suivant dans la table de hachage */
};
struct Suffix { /* liste des suffixes */char *word; /* suffixe */Suffix *next; /* le suivant dans la liste des suffixes */
};
State *statetab[NHASH]; /* table de hachage d’états */
20
La structure de données
pref[0]
pref[1]
suf
next
pref[0]
pref[1]
suf
next
“Show”
“your”
word
next
“flowcharts”
word
next
“tables”
un State:
un State:
un Suffix:un Suffix:
statetab:
21
Nécessité d’une fonction de hachage
/* hash: calcule la valeur de hachage pour le tableau de chaînes de caractères NPREF */
enum {MULTIPLIER = 31};unsigned int hash (char *s[NPREF]){
unsigned int h;unsigned char *p;int i;h = 0;for (i = 0; i < NPREF; i++)
for (p = (unsigned char *) s[i]; *p != ‘\0’; p++)h = MULIPLIER * h + *p;
return h % NHASH;}
22
Nécessité d’une fonction de recherche/* lookup: recherche le préfixe; le crée si nécessaire *//* retourne le pointeur s’il est présent ou créé; NULL sinon *//* la création ne fait pas de strdup ainsi les chaînes ne changeront pas par la suite */State * lookup (char *prefix[NPREF], int create){
int i, h;State *sp;h = hash(prefix);for (sp = statetab[h]; sp != NULL; sp = sp->next) { for (i = 0; i < NPREF; i++) if (strcmp(prefix[i], sp->prefix[i]) != 0)
break; if (i == NPREF) /* il est trouvé */ return sp;}if ( create) { sp = (State *) malloc(sizeof(State)); for (i = 0; i < NPREF; i++) sp->pref[i] = prefix[i]; sp->suf = NULL; sp->next = statetab[h]; statetab[h] = sp;
} return sp;}
23
La fonction de recherche
• Elle n’effectue aucune copie des chaînes entrantes lorsqu’elle crée un nouvel état.
• Stocke des pointeurs dans sp->pref[].
• Les fonctions utilisant lookup doivent garantir que les données ne seront pas écrasées.
24
Construction de la table de hachage/* build: lit l’entrée, construit la table des préfixes */
void build (char *prefix[NPREF], FILE *f)
{
char buf[100], fmt[10];
/*crée une chaîne de caractères formatée; les %s pourraient dépasser la capacité de buf */
sprintf(fmt,”%%%ds”,sizeof(buf) - 1);
while (fscanf(f,fmt, buf) != EOF)
add(prefix, estrdup(buf));
}
25
La fonction de construction• L’appel particulier à sprintf contourne un
problème irritant se posant avec fscanf:– fscanf avec le format % lira le mot suivant délimité par
une espace;– donc le mot peut être très long (inhabituel).
• Solution: créer dynamiquement la chaîne de caractères nécessaires à sprintf.
• La fonction passe prefix et une copie du mot en entrée à add qui ajoute une nouvelle entrée à la table de hachage.
26
La fonction add
/* add: ajoute un mot à la liste suffix, met à jour prefix */void add (char *prefix[NPREF], char *suffix){
State *sp;sp = lookup(prefix,1); /* créer si pas trouvé */addsuffix(sp, suffix);/* mettre à jour prefix */memmove(prefix, prefix + 1, (NPREF - 1) * sizeof(prefix[0]));prefix[NPREF-1] = suffix;
}
27
La fonction add (2)• L’appel à memmove est une expression idiomatique pour effectuer
des suppressions dans un tableau.
• Déplace la mémoire pour laisser la place pour un nouveau mot.
• Utilise la méthode addsuffix.
/* addsuffix: ajoute un nouveau suffix à l’état courant. suffix ne doit pas changer. */void addsuffix (State *sp, char *suffix){
Suffix *suf;suf = (Suffix *) emalloc(sizeof(Suffix));suf->word = suffix;suf->next = sp->suf;sp->suf = suf;
}
28
Note
• add: exécute la tâche générale consistant à ajouter un suffixe à un préfixe.
• addsuffix: traite l’action spécifique de l’implémentation consistant à ajouter un mot à une liste de suffixes.
• Le détail d’implémentation d’addsuffix peut changer. Donc c’est nécessaire d’en faire une fonction à part, bien qu’elle ne soit appelée qu’une seule fois.
29
Générer des données en sortie
• Avec un préfixe donné, on sélectionne l’un de ses suffixes au hasard, on l’imprime, puis on avance le préfixe.
• Il faut connaître la manière de démarrer et arrêter l’algorithme :– démarrer avec les mots du premier préfixe;– utiliser un marqueur de fin.
• On peut rajouter un mot dont on est sûr qu’il n’apparaîtra dans aucune entrée (NONWORD).char NONWORD[] = “\n”; /* ne peut apparaître comme un mot réel */build(prefix,stdin);add(prefix,NONWORD);
30
La fonction generate/* generate: produit la sortie, un mot par ligne */void generate(int nwords){
State *sp;Suffix *suf;char *prefix[NPREF], *w;int i, nmatch;for (i = 0; i < NPREF; i++) /* réinitialise le préfixe initial */
prefix[i] = NONWORD;for (i = 0; i < nwords; i++) { sp = lookup(prefix, 0); nmatch = 0; for (suf = sp->suf; suf != NULL; suf = suf->next) if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
w = suf->word; if (strcmp(w, NONWORD) == 0) break; printf(“%s\n”,w); memmove(prefix, prefix+1, (NPREF-1) * sizeof(prefix[0])); prefix[NPREF-1] = w;}
}
31
• Produit un mot par ligne de sortie.
• Avec l’emploi des chaînes de caractères NONWORD initiale et finale, generate commence et se termine correctement.
• Permet de sélectionner un élément au hasard lorsque nous ne connaissons pas le nombre total d’éléments.
• La variable nmatch fait le décompte du nombre de correspondance au fur et à mesure de la lecture de la liste.
• Les premières valeurs de Suffix seront les premiers mots du document.
La fonction generate (2)
32
Programme principal
/* markov main: génération de texte aléatoire avec une chaîne de Markov */
int main (void){
int i, nwords = MAXGEN;char *prefix[NPREF]; /* préfixe d’entrée courant */for (i=0; i < NPREF; i++) /* définition du préfixe initial */ prefix[i] = NONWORD;build(prefix, stdin);add(prefix, NONWORD);generate(nwords);return 0;
}
33
Implémentation en C
• Donne au programmeur un contrôle complet sur l’implémentation.
• Les programmes tendent à être rapides.
• Le programmeur C doit faire le gros du travail :
– allocation et libération de la mémoire;
– création des tables de hachage et des listes chaînées…
34
Implémentation en JAVA• Java est un langage orienté objet.
• Il incite à faire particulièrement attention aux interfaces et composantes du programme.
• Il possède une bibliothèque plus riche que celle de C :– un objet Vector qui fournit un tableau dynamique pour tout type
d’objets;– la classe Hashtable qui permet de stocker et d’extraire des
valeurs d’un type particulier à l’aide d’une clé;– etc.
• Dans notre exemple, les vecteurs de chaînes de caractères constituent le choix idéal pour gérer les préfixes et les suffixes.
35
Implémentation en JAVA (2)• Il n’est pas nécessaire d’expliciter le type State car
Hashtable relie implicitement les préfixes au suffixes.
• La classe Hashtable fournit :– une méthode de mise en place pour stocker une paire
de valeur de clé;– une méthode de récupération pour extraire la valeur
d’une clé.
Hashtable h = new Hashtable();
h.put(key, value);
Sometype v = (Sometype) h.get(key);
36
Implémentation en JAVA (3)
• Notre implémentation contient 3 classes :
– Prefix: pour gérer les mots du préfixe;
– Chain: qui lit les données en entrée, construit la table de hachage et génère la sortie;
– Markov: qui représente l’interface publique contenant le main.
37
Classe Markov (en Java)
class Markov {static final int MAXGEN = 10000;
//maximum de mots généréspublic static void main(String [] args) throws IOException{
Chain chain = new Chain();int nwords = MAXGEN;
chain.build(System.in);chain.generate(nwords);
}}…
38
Classe Chain - variables
class Chain {static final int NPREF = 2; // taille de préfixestatic final String NONWORD = "\n";
// mot qui ne peut apparaîtreHashtable statetab = new Hashtable();
// clé = Prefix, valeur = Vector suffixePrefix prefix = new Prefix(NPREF,NONWORD);
// préfixe initialRandom rand = new Random();…
39
Classe Chain – build (suite)
// build: construit la table des State à partir de l’entréevoid build(InputStream in) throws IOException{
StreamTokenizer st = new StreamTokenizer(in);st.resetSyntax(); // annule les règles par défautst.wordChars(0, Character.MAX_VALUE);
// parcourir tous les caractèresst.whitespace(0, ‘ ’); // exclure les caractères jusqu’à l’espacewhile (st.nextToken() != st.TT_EOF)
add(st.sval);add(NONWORD);
}…
40
Classe Chain – add (suite 2)
// add: ajoute le mot à la liste des suffixes// Met à jour le préfixevoid add(String word){
Vector suf = (Vector) statetab.get(prefix);if (suf == null) { suf = new Vector();
statetab.put(new Prefix(prefix),suf);}suf.addElement(word);prefix.pref.removeElementAt(0);prefix.pref.addElement(word);
}
41
Classe Chain – generate (fin)
// generate : génère les mots en sortievoid generate(int nwords){
prefix = new Prefix(NPREF, NONWORD);for (int i = 0; i < nwords; i++) {
Vector v = (Vector) statetab.get(prefix); int r = Math.abs(rand.nextInt()) % v.size(); String suf = (String) v.elementAt(r); if (suf.equals(NONWORD)) break; System.out.println(suf); prefix.pref.removeElementAt(0); prefix.pref.addElement(suf);
}}
} // fin de la classe Chain
42
Classe Prefix – variables et constructeursclass Prefix {
public static final int MULTIPLIER = 31; // pour hashCodepublic Vector pref; // mots adjacents de NPREFS à partir de l’entrée
// Constructeur de Prefix: duplique les préfixes existantsPrefix(Prefix p){ pref = (Vector) p.pref.clone();}
// Constructeur de prefix: n copies de strPrefix(int n, String str){ pref = new Vector(); for (int i = 0; i < n; i++) pref.addElement(str);}…
43
Classe Prefix – hashCode (suite)
// hashCode: génère le hachage à partir de tous les mots préfixes
public int hashCode(){
int h = 0;for (int i = 0; i < pref.size(); i++) h = MULTIPLIER * h + pref.elementAt(i).hashCode();return h;
}
44
Classe Prefix – equals (fin)
// equals: compare deux préfixes pour les mots identiques.
public boolean equals(Object o){
Prefix p = (Prefix) o;for (int i = 0; i < pref.size(); i++)
if (!pref.elementAt(i).equals(p.pref.elementAt(i))) return false;
return true;}
} // fin de la classe Prefix
45
Implémentation Java
• Programme plus concis que en C.
• Java propose une meilleure séparation des fonctionnalités.
• Java fournit des outils qui facilitent l’implémentation de certaines fonctions (ex : Vector).
• Pour utiliser Hashtable, nous avons toujours besoin d’écrire les méthodes hashCode et equals.
46
Implémentation C++
• Le programme écrit en C est également un programme C++.
• Un usage approprié de C++ consiste à définir des classes pour les objets du programme.
• Il est possible d’utiliser la bibliothèque standard STL (Standard Template Library).
• Le standard ISO du C++ inclut la STL.
47
Implémentation C++ - STL• La STL fournit:
– des conteneurs tels que: des vecteurs, des listes, des ensembles;
– une famille d’algorithmes fondamentaux de recherche, de tri, d’insertion et de suppression.
• Elle fonctionne en employant les patrons (template).
• Les conteneurs sont exprimés sous forme de patrons C++ qui sont instanciés pour des types de données spécifiques :– vector <int>, vector <string>
– deque <int>, deque <string>
– map <int, vector <string> >
48
Implémentation C++ - Main• Les déclarations:
typedef deque<string> Prefix;map<Prefix, vector<string> > statetab; // prefixe ->suffixes
• L’utilisation de cette structure s’avère plus pratique que celle du C ou même du Java, parce qu’il n’est pas nécessaire de fournir une fonction hash ou equals.
// main : génération de texte aléatoire avec une chaîne de Markovint main(void){
int nwords = MAXGEN;Prefix prefix; // préfixe d’entrée courant
for (int i = 0; i < NPREF; i++) // initialisation du préfixe add(prefix,NONWORD);
build(prefix,cin);add(prefix,NONWORD);generate(nwords);return 0;
}
49
Implémentation C++ - build et add// build: lit les mots en entrée, construit la table des étatsvoid build(Prefix& prefix,istream& in){
string buf;while (in >> buf)
add(prefix, buf);}
// add: ajoute un mot à la liste des suffixes, met à jour le préfixevoid add(Prefix& prefix, const string& s){
if (prefix.size() ==NPREF) { statetab[prefix].push_back(s); prefix.pop_front();}prefic.push_back(s);
}// statetab[prefix]: effectue une opération de recherche
50
Implémentation C++ - generate// generate: produit une sortie, un mot par lignevoid generate(int nwords){
Prefix prefix;int i;for (i = 0; i < NPREF; i++) // réinitialise le préfixe initial add(prefix, NONWORD);for (i = 0; i < nwords; i++) { vector<string>& suf = statetab[prefix]; const string& w = suf[rand() % suf.size()]; if (w == NONWORD) break; cout << w << "\n"; prefix.pop_front(); // avance prefix.push_back(w);}
}
// Cette version est plus compact que le code C mais il y a un prix à payer// au niveau de la vitesse d’exécution.
51
Performances• Comparaison des différentes implémentations
pour un texte comprenant :– 42685 mots;– 5238 mots distincts;– 22482 préfixes;– suffisamment de répétitions de phrases pour qu’une
liste de suffixes possède plus de 400 mots.
• Le livre des psaumes de la King James Bible.
• Les versions C et C++ ont été compilées avec des compilateurs optimisés, tandis que l’exécution Java dispose de compilateurs de type just-in-time.
52
Performances (suite)250 Mhz R100000
Mips (sec)
400 Mhz
Pentium II (sec)
Ligne de code
source
C 0,36 0,30 150
Java 4,9 9,2 105
C++/STL/deque 2,6 11,2 70
C++/STL/List 1,7 1,5 70
Awk 2,2 2,1 20
Perl 1,8 1,0 18
• Problème avec deque sous Windows.
53
Performance• Les langages de haut niveau donnent des programmes
plus lents que ceux de bas niveau.
• Des bibliothèques standards comme la STL C++ ou les tableaux associatifs peuvent conduire à du code plus compact et du temps de développement plus court.
• Comment estimer la perte de contrôle et le volume du programme lorsque le code fourni par le système devient important ?
• Au fur et à mesure que les outils deviennent compliqués, ils deviennent moins compréhensibles et plus difficiles à maîtriser.
54
Leçons• Lorsque tout fonctionne, les environnements de
programmation riches en ressources (Java, C++ -STL) peuvent être productifs, mais lorsqu’ils échouent, les possibilités de recours sont faibles.
• Il est important de choisir des algorithmes et des structures de données simples.
• Il ne faut pas reconstruire la roue.
• Il est difficile de concevoir complètement un programme et de l’implémenter par la suite :
– Utiliser des processus itératifs.
