Nouvel épisode des codes fantastiques avec une histoire de clonage d’arbres en Python.
Pour créer un clone d’un objet en Python, la méthode standard est d’utiliser la fonction deepcopy disponible dans le module standard copy. Dans le cas qui m’intéresse, je dois cloner un objet issu de la désérialisation d’un objet au format JSON. Cela nous donne deux propriétés : l’objet est un arbre (il n’y a pas dans la structure de l’objet deux références sur le même objet), et il ne contient que des types de base (bool, int, str, float, dict, list). Essayons de voir si l’on peut exploiter ces propriétés pour faire une copie en profondeur rapide. Commençons par un petit exemple de référence :
On observe par ailleurs que la signature de copy.deepcopy est la suivante :
Le paramètre memo est un objet de type dictionnaire qui permet de stocker les correspondances entre objet de référence et clone, et d’ainsi gérer les références multiples. Dans notre cas, on peut éviter les interactions avec cet objet (pas de références multiples dans notre arbre), cela devrait nous éviter quelques indexations de tableau.
On peut aussi inspecter le code de deepcopy dans la bibliothèque Python :
La mécanique est assez générique : elle gère la méthode magique __deepcopy__, effectue un appel rapide aux fonctions copy._deepcopy_list ou copy._deepcopy_dict à travers le dictionnaire _deepcopy_dispatch... On peut s’inspirer de cette stratégie pour une implémentation simple et efficace (car utilisant peu d’appels de fonctions et faisant quelques hypothèses sur les types rencontrés) pour notre objet simplifié :
On notera qu’on ne clone pas les clés de dictionnaires : elles sont immuables par définition.
Pour pousser un peu plus loin l’intégration, on pourrait même encapsuler notre arbre dans une classe avec une méthode __deepcopy__ :-).
