Blog // Exirel.me

Subtile compréhension de listes

Par Florian Strzelecki - 23:59 - 04.11.2014

Tags : Python, Documentation, Programmation, list-comprehension, generator expression

Si vous faites du python, un jour ou l'autre, vous tomberez sur ce genre de structure :

new_list = [int(x) for x in list_of_string_values]

Il s'agit de l'expression très connue appelée list-comprehension. Puissante et pratique, elle permet d'améliorer la lisibilité (dans certains cas), et offre quelques outils intéressants pour réduire la complexité des algorithmes.

Mais connaissez-vous les generator-expression ? Et les set et dict comprehension ?

Bon, tout n'est pas toujours disponible dans toutes les versions de python. Alors je vous préviens, moi, je parle de Python 3.4, version que j'utilise désormais au quotidien. La plupart des exemples et concepts peuvent être transposés, d'une façon ou d'une autre, en Python 2.7.

Generator

Les compréhensions de listes, c'est encore relativement simple : vous voulez une liste, vous l'avez ! Cependant, ce n'est pas toujours très optimisé :

>>> product_ids = [int(product_id) for product_id in raw_identifiers]
>>> for product_id in product_ids:
...     print('I have a product identifier: %d' % product_id)

Dans cet exemple ultra-simpliste (et dont les opérations n'ont pas beaucoup d'intérêts), il y a deux fois trop d'itérations que nécessaire. Mettons qu'il y ait 10 éléments dans la liste raw_identifiers : il y a alors 10 premières itérations pour construire la liste des identifiants transformés en entier (via int), puis 10 autres pour afficher ces informations.

C'est un cas où il vaut mieux utiliser une "generator-expression" :

>>> product_ids = (int(product_id) for product_id in raw_identifiers)
>>> for product_id in product_ids:
...     print('I have a product identifier: %d' % product_id)

Cette fois, il n'y aura que 10 itérations au total !

Regardez plutôt le résultat de type( ... ) dans chaque cas :

>>> type([int(x) for x in raw_id])
<class 'list'>
>>> type(int(x) for x in raw_id)
<class 'generator'>

C'est exactement le même principe qu'avec la fonction range (anciennement xrange) : au lieu de créer une liste, une "generator-expression" crée un générateur, qui n'est pas évalué jusqu'au moment de l'itération.

Attention aux limites

Il y a cependant quelques limitations :

>>> g = (int(x) for x in raw_id)
>>> g
<generator object <genexpr> at 0x7f27827ceb40>
>>> list(g)
[0, 1, 2]
>>> list(g)
[]

Comme il s'agit d'un générateur, il n'est possible d'itérer qu'une seule fois dessus. Cela implique aussi d'autres petites subtilités avec l'usage d'opération in :

>>> g = (int(x) for x in raw_id)
>>> 1 in g
True
>>> 2 in g
True

Jusque là "tout va bien". Mais que se passe-t-il si la comparaison n'est pas faite dans le même ordre ?

>>> g = (int(x) for x in raw_id)
>>> 2 in g
True
>>> 1 in g
False

Le résultat est alors bien différent !

Et enfin, un générateur ne peut pas fournir sa taille :

>>> g = (int(x) for x in raw_id)
>>> len(g)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: object of type 'generator' has no len()

Une "generator expression" ne devrait être utilisée que pour une seule et unique itération. Si vous avez besoin de plusieurs itérations, transformez la avec un simple list(generator).

dict.keys() et dict.items()

Un changement majeur entre Python 2.7 et Python 3.4, c'est la disparition des méthodes dict.iteritems et dict.iterkeys, dont le principe majeur était de retourner non pas des listes, mais des générateurs. En python 3.4, ce sont les fonctions d'origines dict.items et dict.keys qui récupèrent ce comportement, avec quelques différences :

>>> type(d.items())
<class 'dict_items'>
>>> type(d.keys())
<class 'dict_keys'>

Ce sont donc des instances de dict_items et de dict_keys qui sont retournées, et non pas de simple generator comme dans les exemples précédents.

Ce comportement permet des choses plus intéressantes :

>>> keys =  {'a': 1, 'b': 2}.keys()
>>> list(keys)
['a', 'b']
>>> list(keys)
['a', 'b']

Si vous vous rappelez de l'exemple avec les générateurs : une seule itération était possible, car le générateur ne pouvait être consommé qu'une seule fois. Ce n'est pas le cas avec un dict_keys, qui permet d'ailleurs de vérifier la présence d'une clé dans cette liste sans causer d'effets de bords.

Mutabilité et optimisation

Il y a un "soucis" avec les dictionnaires : ce sont des objets mutables. Ils peuvent donc être modifiés. Par exemple pour retirer une clé, il suffit de faire del product_ids[product_id] pour retirer la clé product_id du dictionnaire product_ids.

Certes, c'est très pratique, mais cela peut mener à quelques pièges avec l'usage des dict_keys et dict_items. Voyez plutôt :

>>> for key in d.keys():
...     del d[key]
... 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

Dans ce cas, vous devez transformer le résultat de d.keys en liste :

>>> for key in list(d.keys()):
...     del d[key]
>>> d
{}

Bon, mais c'est gentil les exemples simplistes, mais en général il y a des conditions pour supprimer les clés d'un dictionnaire. Sinon, autant faire un d = {} et le tour est joué. Ce qui se traduit, la première fois, par ceci :

>>> for key in list(d.keys()):
...     if key != 'a':
...         del d[key]
>>> d
{'a': 1}

Oui je sais, la condition est ultra-simpliste. Mais c'est pour l'exemple. Je suis sûr que vous trouverez des cas beaucoup plus complexes à traiter.

C'est bien, mais pas très optimisé : si le dictionnaire contient 50 éléments, il y aura 50 itérations, fois deux ! Et oui, 50 itérations pour créer la liste de clé, puis 50 itérations suivantes pour traiter le contenu de cette liste.

Il est possible de réduire ce nombre, en utilisant... une compréhension de liste !

>>> for key in [k for k in d.keys() if k != 'a']:
...     del d[key]
>>> d
{'a': 1}

La magie ici, c'est que le filtre réduit le nombre d'itération après la création de la liste : 50 itérations pour créer la liste, qui donne une liste réduite à 49 éléments, et donc, 49 itérations.

Maintenant, imaginez la même chose avec :

Dans le premier cas, il y aurait eu 10 000 * 2 = 20 000 itérations au total. Dans le second cas, on tombe à 10 000 + 2000 = 12 000 itérations, soit 8 000 de moins !

La même chose, mais sans mutabilité

J'ai une nette préférence pour l'usage d'objets non-mutables lorsque je n'ai pas spécifiquement besoin de la mutabilité. De manière générale, moins je dois traiter avec, mieux je me porte.

L'avantage de la classe dict de Python, c'est qu'il est possible de construire un dictionnaire assez facilement, comme ceci :

>>> dict((key, value) for key, value in another_dict.items() if condition(key, value))
{'valid_key': 'valid_value'}

C'est un usage assez classique d'une generator-expression avec une condition et le type dict. Cependant, vous pouvez aller un peu plus loin :

>>> {key : value for key, value in another_dict.items() if condition(key, value)}
{'valid_key': 'valid_value'}

Il s'agit d'une "dict-comprehension" : elle utilise le même mécanisme que la compréhension de liste, mais génère un dictionnaire.

Dans les deux cas, il est possible de créer un nouveau dictionnaire, sans avoir besoin de modifier le précédent - et ce, sans aucune différence au niveau du nombre d'itérations.

Pensez-y, la prochaine fois !