Pensez en Python

Comment maîtriser la science de l'informatique


précédentsommairesuivant

13. Étude de cas : le choix des structures de données

Jusqu'ici, vous avez appris à employer les structures de données standard de Python, et vous avez vu certains des algorithmes qui les utilisent. Si vous souhaitez en savoir plus sur des algorithmes, il pourrait être le bon moment pour lire l'annexe BAnalyse des algorithmes. Mais il n'est pas indispensable de la lire avant de poursuivre ; vous pouvez la lire quand vous voulez.

Ce chapitre présente une étude de cas avec des exercices qui vous permettent de réfléchir au choix des structures de données et de vous entraîner à les utiliser.

13-1. Analyse de la fréquence des mots

Comme d'habitude, vous devriez au moins essayer de résoudre les exercices avant de lire mes solutions.

Exercice 1

Écrivez un programme qui lit un fichier, divise chaque ligne en mots, enlève les espaces et la ponctuation, remplace les lettres accentuées par leurs équivalentes sans accent et convertit les lettres en majuscules.

Indice : le module string fournit une chaîne de caractères nommée whitespace , qui contient l'espace, la tabulation, le passage à la ligne, etc., et punctuation qui contient les caractères de ponctuation. Voyons si nous pouvons faire Python jurer :

 
Sélectionnez
>>> import string
>>> string.punctuation
'!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~'

Vous pouvez aussi envisager d'utiliser les méthodes de chaînes de caractères strip , replace et translate . Cette dernière méthode permet de convertir des lettres en d'autres autant de fois que nécessaire. Par exemple, pour remplacer les lettres minuscules accentuées dans une liste hétéroclite de mots :

 
Sélectionnez
>>> table_traduction = str.maketrans('àâéèêëïîôùûç', 'aaeeeeiiouuc')
>>> "Leçon; mène; à; été; où; paraître.".translate(table_traduction)
'Lecon; mene; a; ete; ou; paraitre.'

L'objet de cet exercice est de trouver un moyen de normaliser les données en entrée pour faciliter leur traitement par la suite. Notre liste de mots de référence est en lettres capitales et sans accents, nous adaptons le texte que nous utilisons en entrée.

Exercice 2

Allez sur la page des livres en français du projet Gutenberg ( http://www.gutenberg.org/browse/languages/fr ) et téléchargez votre livre favori libre de droits en format texte brut.

Remarque : certains livres en français peuvent poser des problèmes d'encodage de certains caractères accentués ou de ponctuation, peut-être parfois en raison d'une typographie inhabituelle ou fantaisiste. Nous n'avons pas rencontré ce genre de problème avec Germinal (1885), d'Émile Zola, que nous utiliserons plus loin. Vous éviterez peut-être des difficultés en choisissant le même titre (NdT).

Modifiez votre programme de l'exercice précédent pour lire le livre que vous avez téléchargé, omettre les informations de l'en-tête du début du fichier (et le verbiage juridique en anglais à la fin du livre, le cas échéant), et traiter le reste des mots comme précédemment.

Ensuite, modifiez le programme pour compter le nombre total de mots dans le livre et le nombre de fois que chaque mot est utilisé.

Affichez le nombre de mots différents utilisés dans le livre. Comparez des livres différents par des auteurs différents, écrits à des époques différentes. Quel auteur utilise le vocabulaire le plus vaste ?

Exercice 3

Modifiez le programme de l'exercice précédent pour imprimer les 20 mots les plus fréquemment utilisés dans le livre.

Exercice 4

Modifiez le programme précédent pour lire le fichier mots.txt et ensuite afficher tous les mots du livre qui ne sont pas dans la liste de mots. Combien d'entre eux contiennent des fautes de frappe ? Combien d'entre eux sont des mots communs, qui devraient se trouver sur la liste de mots, et combien d'entre eux sont vraiment obscurs ?

13-2. Nombres aléatoires

S'ils reçoivent les mêmes données en entrée, la plupart des programmes informatiques génèrent à chaque fois les mêmes résultats, donc ils sont censés être déterministes. Le déterminisme est généralement une bonne chose, puisque nous nous attendons à ce que le même calcul donne le même résultat. Pour certaines applications, cependant, nous voulons que l'ordinateur soit imprévisible. Les jeux sont un exemple évident, mais il y en a d'autres.

Rendre un programme vraiment non déterministe se révèle être difficile, mais il existe des façons de le faire au moins paraître non déterministe. L'une d'elles est d'utiliser des algorithmes qui génèrent des nombres pseudoaléatoires. Les nombres pseudoaléatoires ne sont pas vraiment aléatoires, car ils sont générés par un calcul déterministe, mais il est presque impossible de les distinguer des nombres aléatoires uniquement en les regardant.

Le module random fournit des fonctions qui génèrent des nombres pseudoaléatoires (que j'appellerai tout simplement « aléatoires » à partir de maintenant).

La fonction random renvoie un nombre en virgule flottante aléatoire compris entre 0.0 et 1.0 (y compris 0.0, mais pas 1.0). Chaque fois que vous appelez random, vous obtenez le nombre suivant d'une longue série. Pour voir un exemple, exécutez cette boucle :

 
Sélectionnez
import random

for i in range(10):
    x = random.random()
    print(x)

La fonction randint prend en paramètres une limite basse et une limite haute et renvoie un nombre entier compris entre les deux (limites comprises).

 
Sélectionnez
>>> random.randint(5, 10)
5
>>> random.randint(5, 10)
9

Pour choisir de façon aléatoire un élément d'une séquence, vous pouvez utiliser choice :

 
Sélectionnez
>>> t = [1, 2, 3]
>>> random.choice(t)
2
>>> random.choice(t)
3

Le module random fournit également des fonctions pour générer des valeurs aléatoires de distributions continues comme les distributions de Gauss, exponentielle, gamma, et quelques autres.

Exercice 5

Écrivez une fonction nommée choose_from_hist , qui prend un histogramme tel que défini dans la section 11.2Un dictionnaire comme une collection de compteurs et renvoie une valeur aléatoire de l'histogramme, choisie avec une probabilité proportionnelle à la fréquence. Par exemple, pour cet histogramme :

 
Sélectionnez
>>> t = ['a', 'a', 'b']
>>> hist = histogramme(t)
>>> hist
{'a': 2, 'b': 1}

votre fonction devrait retourner 'a' avec une probabilité de 2/3 et 'b' avec une probabilité de 1/3.

13-3. Histogramme de mots

Vous devriez essayer de résoudre les exercices précédents avant de poursuivre. Vous pouvez télécharger ma solution à l'adresse analyze_book1.py. Vous aurez besoin également de emma.txt ou plutôt du fichier texte du livre en français que vous aurez choisi.

Nous avons dû modifier légèrement les exercices pour la traduction française. Du coup, le programme proposé ci-dessus ne correspond pas exactement au libellé des exercices. Vous devrez certainement faire quelques adaptations pour que cela fonctionne comme prévu. En particulier, comme la liste mots.txt contient des mots en capitales et sans accents, il faut légèrement adapter le traitement des lignes du livre choisi. Voici notre version adaptée de la fonction process_line :

 
Sélectionnez
def process_line(line, hist):
    line = line.replace('-', ' ')
    line = line.replace("'", ' ')
    strippables = string.punctuation + string.whitespace

    for word in line.split():
        translation_table = {192: 97, 194: 97, 199: 99, 200: 101, 201: 101, 202: 101, 203: 101, 206: 105, 207: 105, 212: 111, 217: 117, 219: 117, 224: 97, 226: 97, 231: 99, 232: 101, 233: 101, 234: 101, 235: 101, 238: 105, 239: 105, 244: 111, 249: 117, 251: 117} 
        word = word.strip(strippables)
        word = word.translate(translation_table)
        word = word.upper()

        # mise à jour de l'histogramme
        hist[word] = hist.get(word, 0) + 1


Quelques adaptations supplémentaires seront peut-être nécessaires, mais vous devriez être largement en mesure de les faire à ce stade de votre lecture de ce livre. (NdT)

Voici un programme qui lit un fichier et construit un histogramme des mots présents dans le fichier :

 
Sélectionnez
import string

def process_file(nom_fichier):
    hist = dict()
    fp = open(nom_fichier)
    for ligne in fp:
        process_line(ligne, hist)
    return hist

def process_line(ligne, hist):
    ligne = ligne.replace('-', ' ')
    
    for mot in ligne.split():
        mot = mot.strip(string.punctuation + string.whitespace)
        mot = mot.upper()
        hist[mot] = hist.get(mot, 0) + 1

hist = process_file('germinal.txt')

Ce programme lit le fichier germinal.txt, qui contient le texte du roman Germinal d'Émile Zola.

process_file parcourt les lignes du fichier dans une boucle, en les passant une par une à process_line. L'histogramme hist est utilisé comme un accumulateur.

process_line utilise la méthode de chaîne de caractères replace pour remplacer les tirets par des espaces avant d'utiliser split pour diviser la ligne en une liste de chaînes de caractères. Elle parcourt la liste des mots et utilise strip et lower pour enlever les signes de ponctuation et convertir les lettres en capitales. (Dire que les chaînes de caractères sont « converties » représente un raccourci linguistique ; souvenez-vous qu'elles sont immuables, donc des méthodes comme strip et lower renvoient de nouvelles chaînes.)

Enfin, process_line met à jour l'histogramme en créant un nouvel élément ou en incrémentant un élément existant.

Pour compter le nombre total de mots dans le fichier, nous pouvons additionner les fréquences reprises dans l'histogramme :

 
Sélectionnez
def total_mots(hist):
    return sum(hist.values())

Le nombre de mots différents est tout simplement le nombre d'éléments dans le dictionnaire :

 
Sélectionnez
def different_mots(hist):
    return len(hist)

Voici un code pour afficher les résultats :

 
Sélectionnez
print('Nombre total de mots :', total_mots(hist))
print('Nombre de mots différents :', different_mots(hist))

Et le résultat :

 
Sélectionnez
Nombre total de mots : 177195
Nombre de mots différents : 13421

13-4. Les mots les plus fréquents

Pour trouver les mots les plus fréquents, nous pouvons faire une liste de tuples, où chaque tuple contient un mot et sa fréquence, et la trier.

La fonction suivante prend un histogramme et renvoie une liste de tuples mot-fréquence :

 
Sélectionnez
def les_plus_frequents(hist):
    t = []
    for key, value in hist.items():
        t.append((value, key))

    t.sort(reverse=True)
    return t

Dans chaque tuple, la fréquence apparaît en premier, si bien que la liste résultante est triée par fréquence. Voici une boucle qui affiche les dix mots les plus fréquents :

 
Sélectionnez
t = les_plus_frequents(hist)
print('Les mots les plus fréquents sont :')
for freq, mot in t[:10]:
    print(mot, freq, sep='\t')

Je l'utilise l'argument mot-clé sep pour indiquer à print d'utiliser comme « séparateur » un caractère de tabulation plutôt qu'un espace, afin que la deuxième colonne soit alignée. Voici les résultats obtenus avec le roman Germinal :

 
Sélectionnez
Les mots les plus fréquents sont :

DE       7254
LA       6090
LES      3975
LE       3937
IL       3828
A        3272
ET       3172
L        2635
UN       2509
DES      2467
D        2434
UNE      2166
EN       2008
SE       1721
S        1646
ELLE     1613
QUE      1549
QU       1497
DU       1411
ETAIT    1363

Ce code peut être simplifié en utilisant le paramètre key de la fonction sort. Si vous êtes curieux, vous pouvez lire à ce sujet sur https://wiki.python.org/moin/HowTo/Sorting.

13-5. Paramètres optionnels

Nous avons vu des fonctions et des méthodes internes qui prennent des arguments optionnels. Il est aussi possible d'écrire des fonctions définies par le programmeur qui prennent des arguments optionnels. Par exemple, voici une fonction qui affiche les mots les plus fréquents d'un histogramme :

 
Sélectionnez
def afficher_les_plus_frequents(hist, num=10):
    t = les_plus_frequents(hist)
    print('Les mots les plus fréquents sont :')
    for freq, mot in t[:num]:
        print(mot, freq, sep='\t')

Le premier paramètre est requis ; le second est optionnel. La valeur par défaut de num est 10.

Si vous fournissez un seul argument :

 
Sélectionnez
afficher_les_plus_frequents(hist)

num prend la valeur par défaut. Si vous fournissez deux arguments :

 
Sélectionnez
afficher_les_plus_frequents(hist, 20)

num prendra la valeur de l'argument. Autrement dit, l'argument optionnel remplace la valeur par défaut.

Si une fonction a en même temps des paramètres obligatoires et des paramètres optionnels, tous les paramètres requis doivent venir en premier, suivis par ceux qui sont optionnels.

13-6. Soustraction de dictionnaire

Trouver les mots du livre qui ne sont pas dans la liste de mots mots.txt est un problème que vous pourriez identifier comme une soustraction d'ensembles ; autrement dit, nous voulons trouver tous les mots d'un ensemble (les mots dans le livre) qui ne sont pas dans l'autre (les mots dans la liste).

soustraire prend les dictionnaires d1 et d2 et renvoie un nouveau dictionnaire qui contient toutes les clés de d1 qui ne sont pas en d2. Comme nous ne nous soucions pas vraiment des valeurs, nous les initialisons toutes à None.

 
Sélectionnez
def soustraire(d1, d2):
    resultat = dict()
    for clef in d1:
        if clef not in d2:
            resultat[clef] = None
    return resultat

Pour trouver les mots présents dans le livre et pas dans words.txt, nous pouvons utiliser process_file afin de créer un histogramme pour words.text, puis effectuer la soustraction :

 
Sélectionnez
mots = process_file('mots.txt')
diff = soustraire(hist, mots)

print('Mots dans le livre qui ne sont pas dans la liste des mots :')
for mot in diff:
    print(mot, end=' ')

Voici quelques-uns des résultats pour le roman Germinal de Zola :

 
Sélectionnez
Mots dans le livre qui ne sont pas dans la liste des mots :
HERSCHEUR DEFIAT ENFANTERAIT PERFECTIONNEMENTS VANDERHAGHEN FLANQUERAI BOISAIENT MOUQUE FUTAINE LIGNARDS VINSSENT DEROUILLAIENT RAGAILLARDISSAIT

Certains de ces mots sont des noms propres (Vanderhaghen ou Mouque). D'autres (comme perfectionnements ou ragaillardissait) ne figurent pas dans la liste mots.txt parce qu'elle ne contient pas de mots d'une longueur supérieure à 15 lettres (longueur maximale d'un mot au Scrabble). D'autres ne figurent pas dans la liste parce que celle-ci ne contient apparemment pas les verbes conjugués à l'imparfait du subjonctif (défiât, vinssent). Certains sont des termes techniques (herscheur), régionaux ou d'usage peu courant (futaine). Mais quelques-uns sont des mots courants (enfanterait, boisaient, flanquerai) qui mériteraient vraiment de figurer dans la liste !

Exercice 6

Python fournit une structure de données appelée ensemble ( set ) qui offre de nombreuses opérations courantes sur des ensembles. Vous pouvez lire à leur sujet dans la section  19.5Les ensembles (sets) , ou en lire la documentation à l'adresse http://docs.python.org/3/library/stdtypes.html#types-set .

Écrivez un programme qui utilise la soustraction des ensembles pour trouver les mots du livre qui ne sont pas dans la liste de mots. Solution : analyze_book2.py.

13-7. Mots aléatoires

Pour choisir un mot de l'histogramme de façon aléatoire, l'algorithme le plus simple consiste à construire une liste avec plusieurs copies de chaque mot, en fonction de la fréquence observée, puis choisir dans la liste :

 
Sélectionnez
def random_word(h):
    t = []
    for mot, freq in h.items():
        t.extend([mot] * freq)

    return random.choice(t)

L'expression [mot] * freq crée une liste de freq copies de la chaîne de caractères mot. La méthode extend est similaire à append, sauf que l'argument est une séquence.

Cet algorithme fonctionne, mais il n'est pas très efficace ; chaque fois que vous choisissez un mot au hasard, il reconstruit la liste, qui est aussi grande que le livre original. Une amélioration évidente est de construire la liste une seule fois, puis faire des sélections multiples, mais la liste est néanmoins grande.

Une autre possibilité :

  1. Utilisez keys pour obtenir une liste des mots dans le livre.
  2. Créez une liste qui contient la somme cumulée des fréquences des mots (voir l'exercice 2 du chapitre 10). Le dernier élément de cette liste est le nombre total de mots dans le livre, n.
  3. Choisissez un nombre aléatoire de 1 à n. Utilisez une recherche dichotomique (voir l'exercice 10 du chapitre 10) pour trouver l'indice où le nombre aléatoire serait inséré dans la somme cumulée.
  4. Utilisez l'indice pour trouver le mot correspondant dans la liste de mots.

Exercice 7

Écrivez un programme qui utilise cet algorithme pour choisir de façon aléatoire un mot du livre. Solution : analyze_book3.py.

13-8. Analyse de Markov

Si vous choisissez au hasard des mots du livre, vous pouvez vous faire une idée sur le vocabulaire employé, mais vous n'obtiendrez probablement pas une phrase :

 
Sélectionnez
DEPUIS INVITES INQUIETANTE LUI VOUS LUI PASSE IL PAR MALHEUREUSEMENT

Une série de mots au hasard a rarement du sens, car il n'y a aucune relation entre les mots successifs. Par exemple, dans une vraie phrase, vous vous attendez qu'un article comme « une » ou « un » soit suivi par un adjectif ou un nom, et probablement pas par un verbe ou un adverbe.

Une façon de mesurer ces types de relations est l'analyse de Markov, qui caractérise, pour une séquence donnée de mots, la probabilité des mots qui pourraient suivre. Par exemple, le chapitre deux du livre Le Petit Prince (1943), d'Antoine de Saint-Exupéry, commence ainsi :

Le premier soir je me suis donc endormi sur le sable à mille milles de toute terre habitée. J'étais bien plus isolé qu'un naufragé sur un radeau au milieu de l'Océan. Alors vous imaginez ma surprise, au lever du jour, quand une drôle de petite voix m'a réveillé. Elle disait :
- S'il vous plaît... dessine-moi un mouton !
- Hein !
- Dessine-moi un mouton...
J'ai sauté sur mes pieds comme si j'avais été frappé par la foudre. J'ai bien frotté mes yeux. J'ai bien regardé. Et j'ai vu un petit bonhomme tout à fait extraordinaire qui me considérait gravement. [...]
Je regardai donc cette apparition avec des yeux tout ronds d'étonnement. N'oubliez pas que je me trouvais à mille milles de toute région habitée. Or mon petit bonhomme ne me semblait ni égaré, ni mort de fatigue, ni mort de faim, ni mort de soif, ni mort de peur. Il n'avait en rien l'apparence d'un enfant perdu au milieu du désert, à mille milles de toute région habitée. Quand je réussis enfin à parler, je lui dis :
- Mais... qu'est-ce que tu fais là ?
Et il me répéta alors, tout doucement, comme une chose très sérieuse :
- S'il vous plaît... dessine-moi un mouton...
Quand le mystère est trop impressionnant, on n'ose pas désobéir. Aussi absurde que cela me semblât à mille milles de tous les endroits habités et en danger de mort, je sortis de ma poche une feuille de papier et un stylographe. Mais je me rappelai alors que j'avais surtout étudié la géographie, l'histoire, le calcul et la grammaire et je dis au petit bonhomme (avec un peu de mauvaise humeur) que je ne savais pas dessiner. Il me répondit :
- Ça ne fait rien. Dessine-moi un mouton.
Comme je n'avais jamais dessiné un mouton je refis, pour lui, l'un des deux seuls dessins dont j'étais capable. Celui du boa fermé. Et je fus stupéfait d'entendre le petit bonhomme me répondre :
- Non ! Non ! Je ne veux pas d'un éléphant dans un boa. Un boa c'est très dangereux, et un éléphant c'est très encombrant. Chez moi c'est tout petit. J'ai besoin d'un mouton. Dessine-moi un mouton.

Dans ce texte, le mot « dessine » est toujours suivi par « moi », et l'expression « dessine-moi » toujours suivie par l'expression « un mouton ». Le mot « éléphant » est généralement suivi par « dans un boa », ou une fois par l'expression « c'est très encombrant ». Le mot « mille » est toujours suivi du mot « milles ». Et ainsi de suite.

Le résultat de l'analyse de Markov est une correspondance entre chaque préfixe (comme « éléphant ») et tous les suffixes possibles (comme « dans un boa » et « c'est très encombrant »).

Étant donné cette correspondance, vous pouvez générer un texte aléatoire en commençant par un préfixe quelconque et en choisissant au hasard parmi les suffixes possibles. Ensuite, vous pouvez combiner la fin du préfixe et le nouveau suffixe pour former le préfixe suivant, et recommencer.

Par exemple, si vous commencez avec le préfixe « Dessine-moi », alors les mots suivants doivent être « un mouton »

Dans cet exemple, la longueur du préfixe est deux, mais vous pouvez faire une analyse de Markov avec une longueur quelconque du préfixe et du suffixe. Le résultat sera sans doute très différent selon les longueurs choisies.

Exercice 8

Analyse de Markov :

  1. Écrivez un programme qui lit un texte à partir d'un fichier et effectue une analyse de Markov. Le résultat devra être un dictionnaire qui établit des correspondances entre chaque préfixe et une collection de suffixes possibles. La collection peut être une liste, un tuple ou un dictionnaire ; c'est à vous de faire le choix approprié. Vous pouvez tester votre programme avec une longueur du préfixe de deux, mais vous devriez écrire le programme d'une manière qui facilitera l'essai d'autres longueurs.
  2. Ajoutez au programme précédent une fonction pour générer du texte aléatoire basé sur l'analyse de Markov. Voici un exemple du roman Germinal avec une longueur de préfixe de 2 :

    Une seule chose lui causait un malaise, parce qu'il avait vu sa baïonnette tordue comme une tombe. L'injustice devenait trop grande, il cita les usines qui fermaient, les ouvriers entraient dans la maturité superbe de la caisse de prévoyance l'inquiétait, devenait une menace d'éboulement et d'inondation, la fosse voisine.

    Pour cet exemple, j'ai gardé la ponctuation attachée aux mots. Le résultat est presque syntaxiquement correct, mais pas tout à fait. Sémantiquement, il a un certain sens, mais pas tout à fait.
    Que se passe-t-il si vous augmentez la longueur du préfixe ? Est-ce que le texte aléatoire a plus de sens ?
  3. Une fois que votre programme fonctionne, vous pourriez vouloir essayer un mélange : si vous combinez du texte à partir de deux ou plusieurs livres, le texte aléatoire que vous générez mélangera le vocabulaire et les phrases des sources de façons intéressantes.

Référence : cette étude de cas est basée sur un exemple tiré de La pratique de la programmation par Kernighan et Pike, Addison-Wesley, 1999.

Vous devriez essayer cet exercice avant de poursuivre ; ensuite, vous pouvez télécharger ma solution sur markov.py.

13-9. Structures de données

L'utilisation de l'analyse de Markov pour générer du texte aléatoire est amusante, mais cet exercice a également une raison : le choix des structures de données. Dans votre solution pour les exercices précédents, vous deviez choisir :

  • la façon de représenter les préfixes ;
  • la façon de représenter la collection de suffixes possibles ;
  • la façon de représenter la correspondance de chaque préfixe à la collection de suffixes possibles.

Le dernier choix est facile : un dictionnaire est le choix évident pour faire correspondre des clés à des valeurs.

Pour les préfixes, les options les plus évidentes sont une chaîne de caractères, une liste de chaînes de caractères ou un tuple de chaînes de caractères.

Pour les suffixes, une option est une liste ; l'autre est un histogramme (dictionnaire).

Comment choisir ? La première étape est de réfléchir aux opérations que vous devrez mettre en œuvre pour chaque structure de données. Pour les préfixes, nous devons être en mesure de supprimer des mots du début et les ajouter à la fin. Par exemple, si le préfixe actuel est « dessine-moi un », et le mot suivant est « mouton », vous devez être en mesure de former le préfixe suivant, « un mouton ».

Votre premier choix serait peut-être une liste, car il est facile d'y ajouter et supprimer des éléments, mais nous devons également être en mesure d'utiliser les préfixes comme clés d'un dictionnaire, donc cela exclut les listes. Avec des tuples, vous ne pouvez pas ajouter ou supprimer, mais vous pouvez utiliser l'opérateur d'addition pour former un nouveau tuple :

 
Sélectionnez
def shift(prefixe, mot):
    return prefixe[1:] + (mot,)

shift prend un tuple de mots, prefixe, et une chaîne de caractères, mot, et forme un nouveau tuple, qui contient tous les mots de prefixe sauf le premier et mot ajouté à la fin.

Pour la collection de suffixes, les opérations que nous devons effectuer comprennent l'ajout d'un nouveau suffixe (ou l'incrémentation de la fréquence d'un suffixe existant) et le choix d'un suffixe aléatoire.

L'ajout d'un nouveau suffixe est tout aussi facile par l'implémentation d'une liste ou d'un histogramme. Le choix d'un élément aléatoire d'une liste est facile ; le choix d'un élément d'un histogramme est plus difficile à faire efficacement (voir l'exercice 7 plus haut).

Jusqu'à présent, nous avons parlé surtout de la facilité d'implémentation, mais il y a d'autres facteurs à considérer dans le choix des structures de données. L'un est la durée d'exécution. Parfois, il existe une raison théorique pour s'attendre qu'une structure de données soit plus rapide que les autres ; par exemple, j'ai mentionné que l'opérateur in est plus rapide pour les dictionnaires que pour les listes, du moins lorsque le nombre d'éléments est grand.

Mais souvent, vous ne savez pas à l'avance quelle mise en œuvre sera la plus rapide. Une option consiste à mettre en œuvre les deux et voir quelle est la meilleure. Cette approche est appelée test de performance, banc d'essai ou benchmark. Une autre option pratique est de choisir la structure de données la plus facile à mettre en œuvre, et vérifier ensuite si elle est assez rapide pour l'application visée. Si oui, il n'y a pas besoin d'aller chercher plus loin. Sinon, il existe des outils comme le module profile, qui peut identifier les endroits les plus chronophages dans un programme.

L'autre facteur à prendre en considération est l'espace mémoire. Par exemple, l'utilisation d'un histogramme pour la collection des suffixes pourrait nécessiter moins d'espace parce que vous devez stocker chaque mot une seule fois, quel que soit le nombre de fois où il apparaît dans le texte. Dans certains cas, économiser l'espace peut aussi rendre plus rapide l'exécution de votre programme, et à l'autre extrême, celui-ci pourrait ne pas s'exécuter du tout s'il manque de mémoire. Mais pour de nombreuses applications, l'espace mémoire est une considération secondaire après la durée d'exécution.

Une dernière réflexion : dans cette discussion, j'ai sous-entendu qu'il fallait utiliser une seule structure de données tant pour l'analyse que pour la génération. Mais comme ce sont des phases distinctes, il serait également possible d'utiliser une structure pour l'analyse et ensuite la convertir en une autre structure pour la génération. Cela en vaut la peine si le gain de temps lors de la génération est supérieur au temps passé à effectuer la conversion.

13-10. Débogage

Lorsque vous déboguez un programme, et surtout si vous travaillez sur un bogue coriace, voici cinq choses à essayer :

  • lire : examinez votre code, relisez-le et vérifiez qu'il dit ce que vous vouliez dire ;
  • exécuter : expérimentez en apportant des changements et en exécutant différentes versions. Souvent, si vous affichez la bonne chose au bon endroit dans le programme, le problème devient évident, mais parfois vous avez à construire des échafaudages ;
  • ruminer : prenez le temps de réfléchir ! De quel genre d'erreur s'agit-il : de syntaxe, d'exécution, ou sémantique ? Quelles informations les messages d'erreur ou la sortie du programme vous offrent-ils ? Quel genre d'erreur peut provoquer le problème que vous rencontrez ? Qu'est-ce que vous avez modifié récemment, avant que le problème soit apparu ?
  • méthode du canard en plastique : si vous expliquez le problème à quelqu'un d'autre, vous trouverez parfois la réponse avant d'avoir fini de poser la question. Souvent, vous n'avez pas besoin d'une autre personne ; vous pourriez parler à un canard de baignoire en plastique. Et cela est à l'origine de la stratégie bien connue appelée méthode du canard en plastique. Je ne l'invente pas ; voir https://fr.wikipedia.org/wiki/M%C3%A9thode_du_canard_en_plastique ;
  • revenir en arrière : à un certain moment, la meilleure chose à faire peut être de reculer, de défaire les changements récents, jusqu'au moment où vous vous retrouvez avec un programme qui fonctionne et que vous comprenez. Ensuite, vous pouvez commencer à reconstruire.

Les programmeurs débutants restent parfois bloqués sur l'une de ces activités et oublient les autres. Chaque activité a son propre mode de défaillance.

Par exemple, la lecture de votre code peut aider si le problème est une faute de frappe ou un mot pour un autre, mais pas si le problème est un malentendu conceptuel. Si vous ne comprenez pas ce que fait votre programme, vous pouvez le lire 100 fois et ne jamais voir l'erreur, parce que l'erreur est dans votre tête.

Tester des bouts de code peut aider, surtout si ce sont des petits bouts de code simples. Mais si vous expérimentez des changements sans penser à relire votre code, vous pouvez tomber dans un syndrome que j'appellerais « la programmation errante aléatoire », qui consiste à faire des changements aléatoires jusqu'à ce que le programme fasse ce que vous voulez. Inutile de dire que ce genre de méthode peut prendre beaucoup de temps.

Vous devez prendre le temps de réfléchir. Le débogage est comme une science expérimentale. Vous devez avoir au moins une hypothèse sur la nature du problème. S'il existe deux ou plusieurs possibilités, essayez d'imaginer un test qui permettrait d'éliminer l'une d'elles.

Mais même les meilleures techniques de débogage échoueront s'il y a trop d'erreurs, ou si le code que vous essayez de corriger est trop grand et complexe. Parfois, la meilleure option est de battre en retraite, de simplifier le programme jusqu'au moment où vous arrivez à quelque chose qui fonctionne et que vous comprenez.

Les programmeurs débutants sont souvent réticents à reculer parce qu'ils ne supportent pas l'idée de supprimer une ligne de code (même si elle est erronée). Si cela vous aide à vous sentir mieux, faites une copie votre programme dans un autre fichier avant de commencer l'élagage. Ensuite, vous pourrez rajouter les morceaux un par un.

Trouver un bogue coriace nécessite relecture, exécution, rumination, et parfois du recul. Si vous vous retrouvez coincé sur l'une de ces activités, essayez les autres.

13-11. Glossaire

  • déterministe : relatif à un programme qui fait la même chose à chaque exécution, avec les mêmes données en entrée.
  • pseudoaléatoire : relatif à une suite de nombres qui semble être aléatoire, mais est générée par un programme déterministe.
  • valeur par défaut : la valeur donnée à un paramètre optionnel si aucun argument n'est fourni.
  • remplacer : le remplacement d'une valeur par défaut par un argument.
  • test de performances : le processus permettant de choisir une structure de données en mettant en œuvre différentes solutions possibles et en les testant sur un échantillon de données en entrée.
  • méthode du canard en plastique : débogage en expliquant votre problème à un objet inanimé tel qu'un canard en plastique. Formuler le problème peut vous aider à le résoudre, même si le canard ne connaît pas Python.

13-12. Exercices

Exercice 9

Le « rang » d'un mot est sa position dans une liste de mots classés par fréquence : le mot le plus commun est de rang 1, le deuxième le plus courant est de rang 2, etc.

La loi de Zipf décrit une relation entre les rangs et les fréquences des mots dans les langues naturelles (https://fr.wikipedia.org/wiki/Loi_de_Zipf). Plus précisément, elle prévoit que la fréquence, f, du mot de rang r est :

kitxmlcodelatexdvpf = c\ r^{-s}finkitxmlcodelatexdvp

s et c sont des paramètres qui dépendent de la langue et du texte. Si vous prenez le logarithme des deux côtés de cette équation, vous obtenez :

kitxmlcodelatexdvp\log{f} = \log{c} - s\log{r}finkitxmlcodelatexdvp

Donc, si vous tracez log f en fonction de log r, vous devriez obtenir une ligne droite de pente -s et intersectant l'axe des ordonnées en log c.

Écrivez un programme qui lit un texte à partir d'un fichier, mesure la fréquence des mots, et affiche une ligne pour chaque mot, en ordre décroissant de fréquence, avec log f et log r. Utilisez le programme graphique de votre choix pour tracer les résultats et vérifier s'ils forment une ligne droite. Pouvez-vous estimer la valeur de s ?

Solution : zipf.py. Pour exécuter ma solution, vous avez besoin du module de traçage matplotlib. Si vous avez installé Anaconda, vous avez déjà matplotlib ; sinon il se peut que vous deviez l'installer.


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Licence Creative Commons
Le contenu de cet article est rédigé par Allen B. Downey et est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 non transposé.
Les logos Developpez.com, en-tête, pied de page, css, et look & feel de l'article sont Copyright © 2016 Developpez.com.