TP 8

DUT Informatique 1 – 2014/2015
Programmation Python
Travaux Dirigés n o8
Listes, chaînes, dictionnaires : performances
La documentation en ligne de Python 3 se trouve ici : http://docs.python.org/3/. Consultez-la régulièrement si vous
avez des doutes sur une fonction ou une fonctionnalité.
Dans tout le TP, chaque fonction que vous écrivez doit posséder une docstring qui indique ce qu’elle fait en fonction des
paramètres donnés !
Au menu : l’objectif de ce TP est de comparer les performances de plusieurs méthodes utilisant des structures de données différentes (liste, chaînes, dictionnaire).
x Exercice 1. histogramme
Dans l’Exercice 3 du TP06, on a vu ce qu’était l’histogramme d’un texte : on construisait celui-ci sous la forme
d’une liste mixte formée par l’alternance [s0 ,o0 ,s1 ,o1 ,...,sk ,ok ] où les si sont les symboles (lettres) présents dans
la source (texte) et les oi sont leurs nombres d’occurrences (apparitions).(Q.2,3,4)
Cette représentation n’était ni pratique ni performante. Nous allons en voir d’autres.
1 Par liste de paires (listes) :
L’histogramme sera représenté par une liste HL de longueur N (nombre de symboles présents dans le
texte) de paires [si ,oi ]. Ainsi un élément HL[i] de l’histogramme sera directement une liste à 2 éléments :
[symbole,occurrences].
a Ecrire une fonction histoListApp(text) qui construit et renvoie, pour la source text, l’histogramme
HLA des symboles rangés dans l’ordre d’apparition.
b Ecrire une fonction histoListLex(text) qui renvoie l’histogramme HLL des symboles rangés dans l’ordre
alphabétique.
2 Par dictionnaire :
L’histogramme sera représenté par un dictionnaire HD de taille N dont les clefs sont les symboles
(lettres) et les valeurs sont les occurrences correspondantes. Pour un symbole s, on obtient directement
son occurrence avec H[s]
a Ecrire une fonction histoDico(text) qui construit et renvoie, pour la source text, l’histogramme HD
(dictionnaire).
b Vous remarquerez qu’un dictionnaire n’est pas une structure ordonnée (1) . Pour trier un dictionnaire
il faut le convertir en listes d’items (2) et trier ces listes : HDL = sorted(list(HD.items())).
La structure de l’objet HDL ainsi construit est exactement la même que celle de l’histogramme
lexicographique par listes HLL précédent.
3 Tests de performances :
On veut maintenant comparer les vitesses d’excution de ces méthodes pour construire un histogramme
lexicographique. Pour que les tests soient révélateurs, il faut travailler sur des sources volumineuses.
a Récupérez les textes disponibles dans le répertoire http://igm.univ-mlv.fr/~incerti/1415/DUT1/data/
(1). ATTENTION ! : selon les versions de python, les éléments du dictionnaire peuvent être rangés dans l’ordre d’appartition
ou dans un ordre apparemment aléatoire. Ne JAMAIS faire d’hypothèse sur l’ordre d’un dictionnaire !
(2). cf. documentation
1
b
Pour charger les N premiers caractères d’un fichier texte dans une chaîne, on peut utilser :
text=open(<PATH>,"r").read(N) où <PATH> est le chemin pour accéder au fichier (par exemple :
"../data/alice.txt").
c Comparez, pour des sources de plus en plus volumineuses, les temps de calcul pour :
i. l’utilisation de HLL=histoListLex(text),
ii. l’utilisation de HLA=histoListApp(text) suivie d’un tri sur HLA,
iii. l’utilisation de HD=histoDico(text) suivie d’un tri sur le dictionnaire HD (création de la liste HDL)
Vous détaillerez les temps de calculs intermédiares pour les tests (ii) et (iii).
Quelles conclusions en tirez-vous (expliquer les écarts de performance observés) ?
x Exercice 2. matrice des permutations
Une permutation d’ordre k sur un texte de longueur N consiste à "pousser" le texte vers la droite de k
positions, récupérer les symboles qui "sortent" et les réinsérer en tête de texte. Par exemple la permutation
d’ordre 6 sur la chaîne "petit papy poney " donne la chaîne "poney petit papy"
1 Dans cet exercice nous souhaitons construire ces permutations sous la forme de listes. La matrices des
permutations d’un texte de longueur N est donc simplement une matrice carrée NxN dont chaque ligne
L[i] est la permutation d’ordre i du texte (sous forme de liste).
Pour la chaîne "poney", on obtiendrait
perm=[[’p’,’o’,’n’,’e’,’y’],[’y’,’p’,’o’,’n’,’e’],[’e’,’y’,’p’,’o’,’n’],[’n’,’e’,’y’,’p’,’o’],[’o’,’n’,’e’,’y’,’p’]]
Là encore on veut comparer les performances de plusieurs méthodes. Ecrivez, commentez (i.e. expliquez)
et testez les performances des 4 méthodes proposées ci-dessous sur des entrées volumineuses (3) .
a def permutations1(text) :
c def permutations3(text) :
perm = []
for i in range(len(text)) :
perm = [list() for i in range(len(text))]
perm.append([])
for i in range(len(text)) :
for j in range(len(text)) :
perm[i][0:0]=list(text[-i:])
perm[i].append(text[(i+j)%l])
perm[i][i:i]=list(text[:-i])
return perm
return perm
#---------------------------------#---------------------------------
b def permutations2(text) :
d def permutations4(text) :
perm = [list() for i in range(len(text))] perm = [list() for i in range(len(text))]
p=perm[0]=list(text)
for i in range(len(text)) :
for i in range(1,len(text)) :
perm[i]=list(text[-i:]+text[:-i])
perm[i]=p[-i:]+p[:-i]
return perm
return perm
2 Supposons maintenant que l’on puisse se contenter de disposer des permutations directement sous la
forme de chaînes de caractères. On peut alors construire notre "matrice de permutations" sous la forme
d’une simple liste de chaînes.
Ecrivez une fonction (la plus performante possible) permutations5(text) qui produit en sortie la liste de
toutes les permutations sous forme de chaînes.
Pour la chaîne "poney", on obtiendrait cette fois perm=["poney","ypone","eypon","neypo","oneyp"]
Comparez l’efficacité de cette méthode par rapport aux 4 précédentes.
(3). Attention : si la taille du texte est trop importante (>50 000 car.), cela peut saturer la mémoire et produire une erreur
2

Download Report