1 – Contexte
Suite à mon premier article parlant des techniques d’optimisation, j’avais volontairement omis les conteneurs associatifs qui méritent un article spécifique : en effet, ils sont extrêmement utiles et utilisés. Connaitre leurs qualités et leurs limites permet d’éviter les principaux pièges. Nous parlerons des deux principaux conteneurs associatifs : les dictionnaires et les ensembles. Leur usage est très pratique et Python en a intégré des versions dans les types de base (dict et set) et en propose des versions spécifiques dans les modules
2 – Dictionnaires
Un dictionnaire est un conteneur qui permet d’associer une valeur à une clé. La clé est unique au sein du dictionnaire dict de Python. Et la clé doit être obligatoirement un type hashable (les listes sont donc interdites)…
2.1 – Accès en lecture/écriture
Partons d’un exemple : créons une application dont le but est de compter les mots utilisés dans un fichier texte et comparons des stratégies de remplissage de dictionnaires… Nous utiliserons la fonction time.perf_counter() pour mesurer le coût d’exécution des différentes méthodes (elle retourne une fraction de secondes en utilisant un compteur de performances système).
Afin de pouvoir tester différentes méthodes, nous isolerons dans une fonction ‘update’ la mise à jour du compteur dans le dictionnaire.
2.1.1 – La méthode boy-scout
Elle consiste à d’abord tester l’existence de la clé avant de mettre à jour la valeur :
def update1( d, word ):
s = perf_counter()
if word in d:
d[ word ] += 1
else:
d[ word ] = 1
return perf_counter() - s
La fonction retourne le temps consommé par la mise à jour du compteur.
2.1.2 – La gestion par exception
L’accès à un dictionnaire avec une clé qui n’existe pas déclenche une exception KeyError. On peut remplacer le test d’existence par un accès avec une gestion de l’exception :
def update2( d, word ):
s = perf_counter()
try:
d[ word ] += 1
except KeyError:
d[ word ] = 1
return perf_counter() - s
2.1.3 – La méthode ‘dict.get’
dict propose une fonction get. Celle-ci permet de récupérer une valeur à partir d’une clé et une valeur par défaut. Si la clé n’est pas présente dans le dictionnaire, on retourne la valeur par défaut.
def update3( d, dget, word ):
s = perf_counter()
d[ word ] = dget( word, 0) + 1
return perf_counter() - s
On passe comme argument dget qui est d.get afin d’avoir un accès plus performant…
2.1.4 – collections.defaultdict
Le module collections propose des conteneurs supplémentaires et notamment le defaultdict… Celui-ci s’initialise avec le type de la valeur. Quand on accède à une clé, si celle-ci n’existe pas une entrée est créé avec la valeur par défaut du type (0 pour un entier, une liste vide pour un liste, etc..).
def update4( d, word ):
s = perf_counter()
d[ word ] += 1
return perf_counter() - s
2.1.5 – Fonction de comptage des mots
La fonction prend en entrée le chemin d’accès au fichier à lire et le nombre de fois qu’elle doit le lire. La fonction retourne le nombre de clés mises à jour, la taille du dictionnaire ainsi que le temps de référence (la méthode boy-scout) et ensuite les ratios des temps comparés.
def load( filename, n ):
d1, d2, d3 = {}, {}, {}
dget = d3.get
d4 = defaultdict(int)
t1, t2, t3, t4 = 0., 0., 0., 0.
nb = 0
for i in range( n ):
with open( filename, 'r' ) as file:
for line in file:
# to remove leading/trailing blank char and convert the string
# to lower
line = line.strip().lower()
# replace special characters by space to separate the words
for c in "\t.,;:!?\'\"()[]&{}<>`":
line = line.replace( c, ' ' )
# split in words and count them
words = line.split()
for word in words:
t1 += update1( d1, word )
t2 += update2( d2, word )
t3 += update3( d3, dget, word )
t4 += update4( d4, word )
nb += 1
return ( nb, len(d1), t1, 1., t2/t1, t3/t1, t4/t1 )
2.1.6 – Les premiers résultats
Nous allons utiliser un fichier texte (COPYING3-gcc-tdm.txt) qui nous servira de référence. Et nous allons effectuer une série de mesures en comptant plusieurs le fichier :
for n in ( 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000 ):
print( load( "COPYING3-gcc-tdm.txt", n ) )
Nous obtenons comme résultat :
Je suis d’accord avec vous, le résultat n’est pas forcément très exploitable sous cette forme…
Mais grâce aux ratios, nous pouvons vérifier une tendance : la méthode boy-scout qui semblait pourtant logique et relever d’une bonne méthode de développement est globalement la plus mauvaise en termes de performance.
La gestion par exception est globalement meilleure sauf dans le cas où on a 5668 mises à jour contre 1034 clés : il semble que le nombre d’exceptions levées à un impact sur les performances plus il y en a plus elles se dégradent. Cette méthode est meilleure que la méthode boy-scout dès lors que l’on a peu de clés non-présentes dans le dictionnaire.
La méthode qui utilise la fonction dict.get avec une valeur par défaut est légèrement meilleure que la méthode boy-scout mais de peu ; et bien plus mauvaise que la méthode de gestion par exception. Dans le cas d’une utilisation peu fréquente (en termes d’occurrences) elle est préférable car elle a le mérite de la compacité et elle améliore la lisibilité du code.
Le conteneur collections.defaultdict présente clairement les meilleures performances : de 13% à 23% plus performante que la méthode boy-scout et près de 5% plus performante que la gestion par exception. Cette méthode présente donc un grand intérêt technique pour améliorer les performances de vos programmes : c’est un conteneur qui gagne à être connu.
2.2 – Cas pratique de lecture de fichier Wavefront (.obj)
Partons du principe que nous souhaitons faire une petite application qui affiche des modèles 3D dans une fenêtre. Les modèles seront lus dans un fichier au format Wavefront (.obj) : c’est un fichier texte qui contient des informations géométriques (pour plus d’informations, voir https://en.wikipedia.org/wiki/Wavefront_.obj_file ). Nous allons nous concentrer sur un sous-ensemble du format qui nous permettra de lire des nœuds et des triangles en 3D… La syntaxe du fichier est relativement simple :
- Une ligne de commentaire commence par #
- v x y z : désigne un noeud de coordonnées (x,y,z) en 3D (vertex en CAO)
- vt u v : désigne une coordonnée de texture
- vn x y z : désigne un vecteur normal en un point
- f v1/vt1/vn1 v2/vt2/vn2 v3/vt3/vn3 : définit une face triangulaire composée des 3 nœuds désignés par leur indices (v1, v2 et v3), leur coordonnée de textures et les normales aux points
Les indices correspondent au numéro de définition du nœud (commande ‘v’) en démarrant à 1. Si l’indice est négatif on accède aux nœuds à partir du dernier inséré (index -1)… - l id1 id2 … idn : définit une ligne brisé reliant tous les points dont les indices sont fournit
Voici un exemple de fichier :
# cube.obj # v 0.0 0.0 0.0 v 0.0 0.0 1.0 v 0.0 1.0 0.0 v 0.0 1.0 1.0 v 1.0 0.0 0.0 v 1.0 0.0 1.0 v 1.0 1.0 0.0 v 1.0 1.0 1.0 vt 0.25 0.0 vt 0.5 0.0 vt 0 0.25 vt 0.25 0.25 vt 0.5 0.25 vt 0.75 0.25 vt 0.0 0.5 vt 0.25 0.5 vt 0.5 0.5 vt 0.75 0.5 vt 0.25 0.75 vt 0.5 0.75 vt 0.25 1.0 vt 0.5 1.0 vn 0.0 0.0 1.0 vn 0.0 0.0 -1.0 vn 0.0 1.0 0.0 vn 0.0 -1.0 0.0 vn 1.0 0.0 0.0 vn -1.0 0.0 0.0 f 1/11/2 7/14/2 5/12/2 f 1/11/2 3/13/2 7/14/2 f 1/7/6 4/4/6 3/3/6 f 1/7/6 2/8/6 4/4/6 f 3/1/3 8/5/3 7/2/3 f 3/1/3 4/4/3 8/5/3 f 5/10/5 7/6/5 8/5/5 f 5/10/5 8/5/5 6/9/5 f 1/11/4 5/12/4 6/9/4 f 1/11/4 6/9/4 2/8/4 f 2/8/1 6/9/1 8/5/1 f 2/8/1 8/5/1 4/4/1
2.2.1 – Lecture du fichier
L’objectif va consister à nous concentrer sur la méthode de lecture et voir comment repenser notre façon de coder pour améliorer la lisibilité et l’efficacité du code. En effet les développeurs qui viennent à Python le font avec leur connaissance de langages et techniques précédemment apprises ; et ce faisant, nous reproduisons des façons de faire qui ne sont pas forcément les plus adaptées en Python ☹.
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 23 23:19:53 2018
@author: Philippe BOULANGER
"""
def load( filename ):
# local variables
nodes = []
textures = []
normals = []
faces = []
lignes = []
# get the real index of a vertices
def index_vector( id, vector ):
if id == "": return -1
id = int( id )
if id < 0:
return len( vector ) - id
else:
return id - 1
# specific loaders
def add_vertex( coord ):
nodes.append( coord )
def add_texture( coord ):
textures.append( coord )
def add_normal( coord ):
normals.append( coord )
def add_line( points ):
lignes.append( coord )
def add_face( nodes ):
entry = []
for e in nodes:
data = e.split( '/' )
l = len( data )
if l == 1:
entry.append( ( index_vector( e, nodes ) ) )
elif l == 3:
entry.append( ( index_vector( data[0], nodes ),
index_vector( data[1], textures ),
index_vector( data[2], normals ) ) )
else:
raise "problem"
faces.append( entry )
# read files
with open( filename, "r" ) as file:
for line in file:
# replace blank char by spaces
for c in "\t\r\n":
line = line.replace( c, ' ' )
# remove comments
pos = line.find( '#' )
if 0 <= pos:
line = line[ :pos ]
# remove spaces at beginning and at end
line = line.strip()
if 0 == len( line ): continue
# replace multiple spaces by one space
while 0 <= line.find( ' ' ):
line = line.replace( ' ', ' ' )
# treat the commands
columns = line.split( ' ' )
if columns[ 0 ] == 'vt':
add_texture( [ float(x) for x in columns[ 1: ] ] )
elif columns[ 0 ] == 'vn':
add_normal( [ float(x) for x in columns[ 1: ] ] )
elif columns[ 0 ] == 'l':
add_line( [ index_vector( x, nodes ) for x in columns[ 1: ] ] )
elif columns[ 0 ] == 'f':
add_face( columns[ 1: ] )
elif columns[ 0 ] == 'v':
add_vertex( [ float(x) for x in columns[ 1: ] ] )
# finalize
return ( nodes, textures, normals, faces, lignes )
nodes, textures, normals, faces, lignes = load( "cube.obj" )
En exécutant ce code via le profiler, on obtient le résultat suivant :
2.2.2 – Comment optimiser ?
Les « if … elif … else » ne sont pas très efficaces, on évite de les enchainer trop dans les langages comme le C. Python propose 2 outils qui peuvent nous aider dans le cas présent : les dictionnaires et les fonctions lambda…
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 23 23:19:53 2018
@author: Philippe BOULANGER
"""
def load( filename ):
# local variables
nodes = []
textures = []
normals = []
faces = []
lignes = []
# get the real index of a vertices
def index_vector( id, vector ):
if id == "": return -1
id = int( id )
if id < 0:
return len( vector ) - id
else:
return id - 1
# specific loaders
def add_face( nodes ):
entry = []
for e in nodes:
data = e.split( '/' )
l = len( data )
if l == 1:
entry.append( ( index_vector( e, nodes ) ) )
elif l == 3:
entry.append( ( index_vector( data[0], nodes ),
index_vector( data[1], textures ),
index_vector( data[2], normals ) ) )
else:
raise "problem"
faces.append( entry )
# map
convert = { 'v' : lambda coord: nodes.append( [ float(x) for x in coord ] ),
'vt' : lambda coord: textures.append( [ float(x) for x in coord ] ),
'vn' : lambda coord: normals.append( [ float(x) for x in coord ] ),
'f' : add_face,
'l' : lambda coord: lignes.append( [ index_vector( x, nodes ) for x in coord ] ) }
# read files
with open( filename, "r" ) as file:
for line in file:
# replace blank char by spaces
for c in "\t\r\n":
line = line.replace( c, ' ' )
# remove comments
pos = line.find( '#' )
if 0 <= pos:
line = line[ :pos ]
# remove spaces at beginning and at end
line = line.strip()
if 0 == len( line ): continue
# replace multiple spaces by one space
while 0 <= line.find( ' ' ):
line = line.replace( ' ', ' ' )
# treat the commands
columns = line.split( ' ' )
convert[ columns[0] ]( columns[ 1: ] )
# finalize
return ( nodes, textures, normals, faces, lignes )
nodes, textures, normals, faces, lignes = load( "cube.obj" )
Via le profileur, nous obtenons le résultat suivant :
Le gain semble faible mais cela est plus lié à la petite taille du fichier. Plus on aura de commandes dans le fichier obj plus l’écart se creusera car la recherche dans le dictionnaire se fait en o(1) alors que l’on exécutera toutes les comparaisons jusqu’à trouver la bonne commande…
L’important à retenir est qu’un dictionnaire couplé à des fonctions lambda est la bonne solution pour remplacer des if en cascade ou un switch… En Python, if faut penser fonctionnel !
3 – Les ensembles
Les ensembles sont comme des dictionnaires où il n’y aurait que des clés. Les contraintes associées sont les mêmes que pour les dictionnaires. L’un des intérêts est de garantir l’unicité des éléments au sein de l’ensemble.
3.1 – Elimination des doublons dans une liste
Testons différentes façons d’éliminer les doublons d’une liste. L’objectif est d’obtenir une liste en sortie.
3.1.1 – En utilisant un tableau
Le tableau/liste est le conteneur le plus simple et celui qui vient en premier à l’esprit. Il dispose d’un opérateur d’appartenance ‘in’.
def f1(seq):
# order preserving
checked = []
for e in seq:
if e not in checked:
checked.append(e)
return checked
def f2(seq):
# order preserving
checked = []
fct = checked.append
[ fct( e ) for e in seq if e not in checked ]
return checked
3.1.2 – En utilisant un dictionnaire
Le dictionnaire est le second conteneur le plus utilisé et bien souvent il vient en premier dès que l’on cherche une unicité des clés.
def f3(seq):
# not order preserving
s = { x : 1 for x in seq }
return list( s.keys() )
def f4(seq):
# Not order preserving
keys = {}
for e in seq:
keys[e] = 1
return list( keys.keys() )
3.1.3 – En utilisant un set
Bien que n’arrivant pas en premier dans l’esprit du développeur le set Python présente une API riche et simple d’utilisation :
def f5(seq): # Not order preserving return list(set(seq))
Le set s’initialise avec n’importe quelle séquence et nous pouvons le transformer en liste via l’appel à list.
3.1.4 – Exécution en concurrence
Pour tester le temps, nous allons utiliser la fonction perf_counter que nous avions déjà utiliser :
ref = [ 9, 1, 9, 2, 8, 2, 7, 2, 8, 3, 7, 4, 6, 5, 6, 6, 6, 6 ]
for i, f in enumerate( [ f1, f2, f3, f4, f5 ] ):
start = perf_counter()
res = f( ref )
end = perf_counter() - start
print( "f%d" % ( i + 1 ), "> time=", end, "s", " >> res=", res )
Nous utilisons un tableau ‘ref’ qui contient les éléments à traiter. L’exécution nous permet de capturer l’affichage suivant :
Il nous reste à compare cela avec le résultat du profileur :
Dans les 2 types de mesures la fonction f5 (qui utilise le set) reste la méthode la plus performante : elle est donc celle à préférer dès lors que l’on souhaite éviter les doublons !
3.2 – Gérer les opérations ensemblistes
Il existe de nombreux cas où on a besoin de calculer l’union, l’intersection ou les différences entre 2 listes. Par exemple dans une résolution de problèmes par satisfaction de contraintes, les opérations d’élimination dans une liste de tous les éléments d’une autre liste ou le calcul des éléments communs des 2 listes sont répétées en grand nombre de fois.
3.2.1 – Extraire les éléments communs à 2 listes
C’est une opération simple. Nous allons travailler sur 2 listes non triées afin de comparer les performances. Et nous allons opposer des listes aux opérations sur les ‘set’.
Première étape, nous allons utiliser la fonction ‘in’ sur les listes. Dans ce cadre, nous penserons à systématiquement traiter la liste la plus courte afin de diminuer le nombre de tests.
def list_common( l1, l2 ):
if len( l2 ) < len( l1 ):
l1, l2 = l2, l1
return [ x for x in l1 if x in l2 ]
Seconde étape, nous allons travailler sur des listes triées :
def sorted_list_common( l1, l2 ):
l1.sort()
l2.sort()
if len( l2 ) < len( l1 ):
l1, l2 = l2, l1
result = []
j = 0
for x in l1:
for i in range( j, len( l2 ) ):
y = l2[ i ]
if x == y:
result.append( x )
j = i + 1
break
elif x < y:
break
return result
Dernière étape, nous travaillons sur les sets :
def set_common( l1, l2 ):
return list( set( l1 ) & set( l2 ) )
Afin de tester les performances relatives des différentes méthodes, nous allons travailler sur des listes générées selon un algorithme connu avec des valeurs communes et disjointes. Utiliser des listes générées par range avec un pas qui est nombre premier permet d’arriver à une situation intéressante dès lors que l’on inverse l’ordre de base :
n = 5000 l1 = list( reversed( range( 0, n + 1, 3 ) ) ) l2 = list( reversed( range( 0, n + 1, 5 ) ) ) a = list_common( l1, l2 ) b = set_common( l1, l2 ) c = sorted_list_common( l1, l2 )
et nous allons faire varier ‘n’ en utilisant le profiler pour obtenir des temps d’exécutions de chaque fonction (en micro-secondes).
| 100 | 200 | 500 | 1000 | 5000 | 10000 | 50000 | 100000 | 1000000 | |
| list_common | 10.58 | 26.8 | 138.23 | 530.69 | 13210 | 52460 | 1290000 | 5410000 | 503400000 |
| sorted_list_common | 21.86 | 35.97 | 75.11 | 150.92 | 804.67 | 1530 | 7540 | 15370 | 131800 |
| set_common | 5.29 | 7.76 | 12.69 | 16.93 | 147.75 | 281.04 | 1170 | 4030 | 29660 |
Voici des courbes des logarithmes en base 10 des temps :
Dans tous les cas la fonction qui utilise les ensembles est bien plus performante que les autres et on se rend bien compte que plus n augmente plus les écarts de performances augmentent…
3.2.2 – Les autres fonctions ensemblistes
Il y a différentes opérations ensemblistes disponibles avec les ‘set’ Python. On peut les appeler soit via une fonction soit par des opérateurs :
- union(*others) ou set1|set2|…|setn
union de tous les ensembles set1 à setn. - intersect(*others) ou set1&set2&…&setn
retourne en ensemble contenant toutes les valeurs communes de tous les ensembles - difference(*others) ou set1-set2-…-setn
retourne un ensemble contenant tous les élements du 1er ensemble qui n’appartiennent à aucun des autres - symmetric_difference(*others) ou set1^set2^…^setn
retourne un ensemble contenant tous les élements qui ne sont que dans un seul ensemble
La fonction intersect correspond à notre test sur les éléments communs. Ces fonctions restent plus performantes que ce que nous pourrions écrire nous-même en Python.
4 – Conclusion
Les conteneurs associatifs sont un des outils les plus utiles en Python. Leurs performances sont des atouts à ne pas négliger pour réussir à écrire des algorithmes efficaces qui tiennent face à une augmentation de la volumétrie. Très souvent je suis amené à m’en servir…
