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 :

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).

1002005001000500010000500001000001000000
list_common10.5826.8138.23530.69132105246012900005410000503400000
sorted_list_common21.8635.9775.11150.92804.671530754015370131800
set_common5.297.7612.6916.93147.75281.041170403029660

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…