Bonjour ! Aujourd'hui, je veux vous parler des dictionnaires en Python, et notamment de leur — relativement — nouvelle propriété d'ordre. TL;DR: les considérations concernant les dictionnaires ordonnés tourne autour des performances. On oublie de mentionner que cela facilite le débogage, mais que ce...

Bonjour !

Aujourd'hui, je veux vous parler des dictionnaires en Python, et notamment de leur — relativement — nouvelle propriété d'ordre.

TL;DR: les considérations concernant les dictionnaires ordonnés tourne autour des performances. On oublie de mentionner que cela facilite le débogage, mais que cela peut aussi cacher un bogue dans l'implémentation d'un algorithme, raison pour laquelle j'ai écrit le fragment de code ci-dessous.

Un peu de contexte

Si l'on en croit ce thread StackOverFlow, les clefs d'un dictionnaire dans Python3 depuis sa version 3.6 sont de facto ordonnées dans l'implémentation CPython (dans l'ordre d'insertion), et Python3 dans sa version 3.7 standardise cet état de fait, ce qui veut dire que les autres implémentations (PyPy, Jython...) devront s'aligner afin de correctement implémenter le nouveau standard, pour assurer la compatibilité du code entre "interpréteurs". (Je mets le lien StackOverFlow parce qu'il en contient d'autres vers la liste de diffusion de courriel, etc.)

Si vous vous demandez ce qui a amené à cet état de fait, je vous recommande la vidéo suivante, par le curieux Raymond Hettinger.

Avec ça, vous aurez des éléments pour évaluer la pertinence des dictionnaires ordonnées en Python.

Notez, pour ceux qui n'ont pas regardé la documentation, que Python3 met à disposition un OrderedDict déjà disponible dans les versions antiques, antédiluviennes, je veux dire celles pré-3.4 (oui, je trolle, mais à peine).

Le problème

Voyons un peu le contexte des deux problèmes qui m'ont amené à écrire cet article.

Scénario 1

J'étais en train de déboguer un logiciel, appelons-le Verifikator, qui faisait des appels API afin de vérifier des données en bases. Il se trouve que les résultats de Verifikator étaient aléatoires. De temps en temps, il retournait les bons résultats, i.e. il indiquait que certaines données en base étaient invalides, et de temps en temps, Verifikator n'indiquait pas d'erreur, alors qu'on pouvait vérifier a la mano qu'il y avait effectivement une erreur en base. Pour faire simple, la raison pour laquelle Verifikator n'était pas déterministe, c'est qu'il dépendait de l'ordre d'un dictionnaire dont la donnée provenait de l'API de la base de données. Vous comprenez que j'exagère quand je dit que Verifikator n'était pas déterministe, il l'est heureusement, puisqu'il s'agit d'un système informatique, et qu'on néglige les rayons cosmiques et les bogues système.

Je me permet de rappeler à ceux d'entre vous qui s'étonnent de ce comportement erratique de Verifikator que j'étais en train de le déboguer (qui plus est, j'avais seulement participé à sa conception, pas à son implémentation).

Verifikator tourne en Python3.5, si l'on avait utilisé une version supérieure, on n'aurait pas eu ce problème, notamment, Verifikator aurait soit systématiquement planté, soit systématiquement fonctionné. Ç'eût été mieux afin de pouvoir localiser le bug par dichotomie, je vous avoue que mon état de santé mentale se dégradait à vu d'œil lorsque j'ai commencé à observer ce comportement aléatoire, en cherchant à localiser les lignes fautives par dichotomie.

Je reviens un instant sur cette histoire de dichotomie pour bien faire sentir à quel point c'est fatiguant. Imaginez un peu, vous essayez de déterminer un point A où le programme est dans un état valide et un point B dans lequel l'état est invalide, puis vous regardez un nouveau point C "au milieu", afin de savoir si ce point C est le nouveau point valide A' ou bien le nouveau point B' pour l'itération suivante. Le problème, c'est que parfois vous pensez que l'état du programme est valide à ce point C, mais que ce n'est pas vrai en général. Vous continuez donc à itérer entre C et B, alors que le problème se trouve entre A et C.

Vous comprenez pourquoi j'apprécie fortement le fait que les dictionnaires soient ordonnés pour le débogage.

Mais. Comme vous imaginez, il y a un mais. Parce qu'il n'y a pas que des avantages aux dictionnaires ordonnés. C'est le sujet du second scénario.

Scénario 2

Dans d'autres circonstances, j'ai déjà écrit — j'étais l'auteur du code cette fois-là, contrairement à Verifikator — un algorithme qui ne fonctionnait que si le dictionnaire sur lequel il tournait était ordonné. J'utilisais Python3.6 à l'époque, et par conscience professionnelle, j'ai compilé les versions 3.4 à 3.7 de Python afin de vérifier que les tests étaient corrects avec ces interpréteurs. Quelle ne fut pas ma surprise quand je m'aperçus que ce n'était point le cas. Ce n'était même pas le nouvel Python3.7 encore en bêta qui posait problème, mais les version 3.4 et 3.5. J'ai donc réécrit cet algorithme afin qu'il ne dépende plus de l'ordre du dictionnaire d'entrée (très simplement en construisant un OrderedDict à partir du dictionnaire et d'une liste correctement triée).

Conséquences

À l'époque, je n'avais pas rajouté de code pour tester les fonctions de service du second programme, je m'assurai qu'il fonctionnait avec les 4 versions mineures de Python3 pour lesquelles je développais le programme.

J'ai fait les choses différemment cette fois, puisque j'ai codé cette fonction, qui randomise les clefs d'un dictionnaire plat (fonction non récursive sur d'éventuels dictionnaires en valeurs du dictionnaire passé en argument).

import random as rnd
def shuffle_dict_keys(d: dict) -> dict:
    """shuffle the keys of a dictionary for testing purposes now that
    Python dictionaries are insert-ordered. Does not compute inplace.
    Does not work recursively.
    """
    res = {}
    l = list(d)
    rnd.shuffle(l)
    for k in l:
        res[k] = d[k]
    return res

J'avais en tête cette planche XKCD en écrivant ce code. Non pas que je préfère l'ancien comportement, mais que pouvoir y souscrire de manière optionnelle me permet d'avoir des tests de meilleure qualité, et qu'il a donc fallu queje trouve un contournement afin de retrouver l'ancien comportement dans les cas de tests.

Conclusion

De manière générale, je suis assez content que les dictionnaires soient ordonnés, mais je ne m'attendais pas à rencontrer de tels écueils, notamment puisque la majorité des conversations que j'avais lues sur le sujet s'attardaient sur les performances de cette nouvelle implémentation, et non sur ce genre de considérations.

Joyeux code !

Motius