Exercice de style : tableau de fréquences en Python

Ce billet est l’édition Python du billet sur les tableaux de fréquences en Java avec les streams vu comme un exercice de style.

Les exemples de ce billet ont été testés avec la version 3.12 de Python.

La problématique

On a une séquence d’éléments qui peuvent se répéter, on souhaite avoir pour chaque élément sa fréquence, c’est-à-dire le nombre de fois que cet élément apparaît dans la séquence. Par exemple pour la séquence d’élément a, b, c, d, a, d, a, je souhaite obtenir l'information que l'élément a apparaît 3 fois, les éléments b et c apparaissent 1 fois et l'élément d apparaît 2 fois.

Tableau de fréquences est traduit en anglais (notamment dans les exemples de code) par “frequencies map”.

Une solution impérative

Une manière classique de résoudre ce problème en Python et dans d’autres langages est de parcourir la séquence d’éléments et de compter leurs occurrences. Nous allons stocker au fur et à mesure le résultat dans un dictionnaire, avec bien sûr la nécessité de vérifier si l’élément si trouve déjà ou pas. Ci-après une proposition d’implémentation de la fonction en Python.

def frequencies_map_with_for_from(elements):
    frequencies_map = {}
    for element in elements:
        if element in frequencies_map.keys():
            frequencies_map[element] = frequencies_map[element] + 1
        else:
            frequencies_map[element] = 1
    return frequencies_map

>>> def frequencies_map_with_for_from(elements):
...     frequencies_map = {}
...     for element in elements:
...         if element in frequencies_map.keys():
...             frequencies_map[element] = frequencies_map[element] + 1
...         else:
...             frequencies_map[element] = 1
...     return frequencies_map
...
>>> frequencies_map_with_for_from(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"])
{'a': 3, 'b': 2, 'c': 1, 'd': 4}

Rien d‘extraordinaire : une boucle for pour parcourir les éléments de la liste et à l'intérieur de cette boucle une alternative if-else pour remplir le dictionnaire. On peut avoir comme tests associés ce qui suit (note : j’utilise pytest dans les exemples de code de ce billet).

from frequencies_map import frequencies_map_with_for_from

class TestFrequenciesMapWithFor:
    def test_empty_list(self):
        assert frequencies_map_with_for_from([]) == {}

    def test_single_element_list(self):
        assert frequencies_map_with_for_from(["a"]) == {"a": 1}

    def test_several_identical_elements_list(self):
        assert frequencies_map_with_for_from(["a", "a", "a"]) == {"a": 3}

    def test_several_different_elements_list_sorted(self):
        assert frequencies_map_with_for_from(["a", "a", "a", "b", "b", "c", "d", "d", "d", "d"]) == {"a": 3, "b": 2, "c": 1, "d": 4}

    def test_several_different_elements_list_unsorted(self):
        assert frequencies_map_with_for_from(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]) == {"a": 3, "b": 2, "c": 1, "d": 4}

Détour par itertools

Python permet d’utiliser tant un style impératif qu’un style plus fonctionnel. Dans l’excellente petite introduction à la programmation fonctionnelle en Python David Mertz indique que le module itertools de la bibliothèque standard de Python regorge de fonctions pour faciliter la manipulation des itérateurs et des itérables, et ainsi réaliser des boucles dans un style plus fonctionnel.

Cependant avant d’en venir au fait, un détour dans le détour, pour parler des itérables et des itérateurs.

Itérables et itérateurs

Un itérable en Python est une abstraction représentant une séquence d’éléments capable de retourner un élément à la fois. A partir d’un itérable, on peut créer un itérateur qui est cette fois-ci l’abstraction de l’itération elle-même : un itérateur représente un flux de données avec lequel on peut interagir avec une méthode spécifique pour obtenir l’élément suivant de ce flux. L’ itérateur est une vue ou un curseur qui permet de parcourir un itérable sous-jacent.

Itérables, rassemblement !

Après un peu de recherche dans les fonctions mises à disposition dans le module itertools, je suis tombé sur la fonction groupby qui me semblait pouvoir être exploitée pour résoudre cette problématique.

groupby prend en entrée un itérable et un paramètre optionnel qui correspond à une fonction keydont l'objet est de générer une clé pour chaque élément. Si cette fonction n'est pas spécifiée ou si sa valeur est None, par défaut c'est une fonction identité renvoyant l'élément sans le modifier. Parfait, nous n'avons pas besoin de plus. Faisons un essai dans l'interpréteur.

>>> from itertools import groupby
>>> groupby(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"])
<itertools.groupby object at 0x00000256A268C280>

Le résultat n’est pas celui que j’attendais mais à la réflexion c’est normal : <itertools.groupby object at 0x00000256A268C280>

En effet, Python m’affiche l’adresse de l’objet qui est un itérateur, il ne sait pas me l’afficher directement, il faudrait que je le transforme en liste d’abord. Ok, on va faire ça.

>>> from itertools import groupby
>>> list(groupby(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]))
[('a', <itertools._grouper object at 0x00000256A27C68C0>), ('b', <itertools._grouper object at 0x00000256A27C6830>), ('c', <itertools._grouper object at 0x00000256A27C6800>), ('a', <itertools._grouper object at 0x00000256A27C67D0>), ('d', <itertools._grouper object at 0x00000256A27C67A0>), ('a', <itertools._grouper object at 0x00000256A27C6770>), ('d', <itertools._grouper object at 0x00000256A27C6740>), ('b', <itertools._grouper object at 0x00000256A27C6710>), ('d', <itertools._grouper object at 0x00000256A27C66E0>)]

C’est mieux mais ce n’est toujours pas le résultat final attendu. Même si ce n’est pas très lisible, je sens qu’il y a un problème. Pas grave, dans un premier temps améliorons l’affichage. Déjà on peut voir que l’itérateur retourné est un itérateur sur un tuple comportant la clé et un itérateur. Mettons à profit la méthode map avec une lambda pour améliorer ce qu'on voit. La lambda via la fonction map permet de transformer en liste le deuxième élément de chaque tuple de la séquence retournée par groupby.

>>> from itertools import groupby
>>> list(map(lambda t: (t[0], list(t[1])), groupby(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"])))
[('a', ['a']), ('b', ['b']), ('c', ['c']), ('a', ['a']), ('d', ['d']), ('a', ['a']), ('d', ['d']), ('b', ['b']), ('d', ['d', 'd'])]

Bon, déjà c’est un peu mieux mais ce n’est pas toujours pas ce dont on a besoin. En lisant plus attentivement la documentation de groupby on peut lire que l'opération groupby :

[…] génère un nouveau groupe à chaque fois que la valeur de la fonction key change (ce pourquoi il est souvent nécessaire d’avoir trié les données selon la même fonction de clé). Ce comportement est différent de celui de GROUP BY de SQL qui agrège les éléments sans prendre compte de leur ordre d’entrée.

Ok, cela explique pourquoi nous avons ce résultat [('a', ['a']), ('b', ['b']), ('c', ['c']), ('a', ['a']), ('d', ['d']), ('a', ['a']), ('d', ['d']), ('b', ['b']), ('d', ['d', 'd'])] : pour les 2 derniers d qui se suivent, ils ont bien été regroupés mais sinon à chaque changement de valeur de la clé, un nouveau groupe a été créé. Bon, il faut donc trier la séquence avant d'utiliser groupby. Ok, trions notre séquence (avec sorted) et recommençons.

>>> from itertools import groupby
>>> list(map(lambda t: (t[0], list(t[1])), groupby(sorted(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]))))
[('a', ['a', 'a', 'a']), ('b', ['b', 'b']), ('c', ['c']), ('d', ['d', 'd', 'd', 'd'])]

Cette fois-ci cela nous donne quelque chose que nous allons pouvoir exploiter : [('a', ['a', 'a', 'a']), ('b', ['b', 'b']), ('c', ['c']), ('d', ['d', 'd', 'd', 'd'])]

Nous allons juste faire une petite retouche : plutôt que d’avoir un tuple avec l’élément et la liste de ces occurrences, ce qui nous intéresse c’est l’élément et le nombre de ces occurrences. Nous allons légèrement modifier la lambda à cette fin.

>>> from itertools import groupby
>>> list(map(lambda t: (t[0], len(list(t[1]))), groupby(sorted(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]))))
[('a', 3), ('b', 2), ('c', 1), ('d', 4)]

Parfait, c’est ce dont nous avons besoin, il faut juste transformer ce résultat en dictionnaire : [('a', 3), ('b', 2), ('c', 1), ('d', 4)].

En Python, si on crée un dictionnaire à partir d’une liste de tuples à 2 éléments, cela crée directement un dictionnaire dont les clés sont le premier élément du tuple et la valeur le second élément du tuple. C’est donc juste une petite modification sur l’expression précédente.

>>> from itertools import groupby
>>> dict(map(lambda t: (t[0], len(list(t[1]))), groupby(sorted(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]))))
{'a': 3, 'b': 2, 'c': 1, 'd': 4}

C’est exactement ce qu’on souhaite : {'a': 3, 'b': 2, 'c': 1, 'd': 4}.

Cela nous donne la fonction suivante avec les tests associés :

from itertools import groupby


def frequencies_map_with_map_and_groupby_from(elements):
    return dict(map(lambda t: (t[0], len(list(t[1]))), groupby(sorted(elements))))

from frequencies_map import frequencies_map_with_map_and_groupby_from


class TestFrequenciesMapWithMapAndGroupBy:
    def test_empty_list(self):
        assert frequencies_map_with_map_and_groupby_from([]) == {}

    def test_single_element_list(self):
        assert frequencies_map_with_map_and_groupby_from(["a"]) == {"a": 1}

    def test_several_identical_elements_list(self):
        assert frequencies_map_with_map_and_groupby_from(["a", "a", "a"]) == {"a": 3}

    def test_several_different_elements_list_sorted(self):
        assert frequencies_map_with_map_and_groupby_from(["a", "a", "a", "b", "b", "c", "d", "d", "d", "d"]) == {"a": 3, "b": 2, "c": 1, "d": 4}

    def test_several_different_elements_list_unsorted(self):
        assert frequencies_map_with_map_and_groupby_from(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]) == {"a": 3, "b": 2, "c": 1, "d": 4}

Cette solution est intéressante pour expérimenter l’utilisation de groupby mais n’est au final pas très lisible même si on arrive à avoir une solution en une seule ligne.

Pour une bonne compréhension

Comment pourrait-on améliorer le code pour améliorer sa compréhension ? Et bien justement avec une compréhension ! En Python, en général là où il y a une boucle for, il peut y avoir une compréhension ; au minimum cela mérite de se pencher sur la question. Surtout que Python ne se limite pas au compréhension pour les listes, cela marche aussi avec les dictionnaires.

Cela ne devrait pas être compliqué : pour chaque paire de notre séquence groupby(sorted(elements)), je veux extraire la clé et la valeur associée. Je sais que cette valeur associée est une liste et ce qui m'intéresse c'est sa longueur. Essayons dans l'interpréteur !

>>> from itertools import groupby
>>> {k: len(list(v)) for k, v in groupby(sorted(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]))}
{'a': 3, 'b': 2, 'c': 1, 'd': 4}

Ok, le résultat est très exactement ce que nous recherchons : {'a': 3, 'b': 2, 'c': 1, 'd': 4}.

Cela nous donne la fonction suivante avec les tests associés :

from itertools import groupby


def frequencies_map_with_comprehension_and_groupby_from(elements):
    return {k: len(list(v)) for k, v in groupby(sorted(elements))}

from frequencies_map import frequencies_map_with_comprehension_and_groupby_from


class TestFrequenciesMapWithMapAndGroupBy:
    def test_empty_list(self):
        assert frequencies_map_with_map_and_groupby_from([]) == {}

    def test_single_element_list(self):
        assert frequencies_map_with_map_and_groupby_from(["a"]) == {"a": 1}

    def test_several_identical_elements_list(self):
        assert frequencies_map_with_map_and_groupby_from(["a", "a", "a"]) == {"a": 3}

    def test_several_different_elements_list_sorted(self):
        assert frequencies_map_with_map_and_groupby_from(["a", "a", "a", "b", "b", "c", "d", "d", "d", "d"]) == {"a": 3, "b": 2, "c": 1, "d": 4}

    def test_several_different_elements_list_unsorted(self):
        assert frequencies_map_with_map_and_groupby_from(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]) == {"a": 3, "b": 2, "c": 1, "d": 4}

La solution avec la compréhension tient en 1 ligne tout en étant un peu plus lisible que la première solution avec map. Néanmoins, ces 2 solutions imposent de trier la liste pour pouvoir exploiter groupby alors que la solution impérative n'a pas cette contrainte.

Compter sur une solution idiomatique

Ces détours par itertools, groupby et les compréhensions c’est intéressant pour progresser dans la connaissance de Python, mais cela ne fournit pas une vraie solution idiomatique.

En Python, il existe la structure de données collections.Counter qui est une sous-classe de dictionnaire et qui peut très directement être utilisée comme tableau de fréquence. Counter est une implémentation en Python d'un multiensemble. Un multiensemble est une manière formelle de définir un tableau de fréquences (pour la petite histoire j’ai découvert l’existence de cette structure de données en pratiquant Python sur Exercism suite au retour d’un mentor sur un puzzle).

>>> from collections import Counter
>>> Counter(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"])
Counter({'d': 4, 'a': 3, 'b': 2, 'c': 1})

On résout le problème en appelant juste la bonne abstraction dans le langage. Counter peut être initialisé avec une séquence d'éléments ou un autre dictionnaire et offre notamment une méthode pour extraire les éléments les plus fréquents (Cette classe et le module collections mériteraient des billets spécifiques).

Cela nous donne la fonction suivante avec les tests associés :

from collections import Counter


def frequencies_map_with_counter_from(elements):
    return Counter(elements)

from frequencies_map import frequencies_map_with_counter_from


class TestFrequenciesMapWithCounter:
    def test_empty_list(self):
        assert frequencies_map_with_counter_from([]) == {}

    def test_single_element_list(self):
        assert frequencies_map_with_counter_from(["a"]) == {"a": 1}

    def test_several_identical_elements_list(self):
        assert frequencies_map_with_counter_from(["a", "a", "a"]) == {"a": 3}

    def test_several_different_elements_list_sorted(self):
        assert frequencies_map_with_counter_from(["a", "a", "a", "b", "b", "c", "d", "d", "d", "d"]) == {"a": 3, "b": 2, "c": 1, "d": 4}

    def test_several_different_elements_list_unsorted(self):
        assert frequencies_map_with_counter_from(["a", "b", "c", "a", "d", "a", "d", "b", "d", "d"]) == {"a": 3, "b": 2, "c": 1, "d": 4}

Conclusion

Comme l’écrivait Nicolas Boileau, Vingt fois sur le métier remettez votre ouvrage. Des exercices de style comme celui-ci ou des coding katas sous différentes formes offrent des manières concrètes d’approfondir notre connaissance et notre maîtrise d’un langage. Même quand on pense avoir fait le tour d’un sujet, il peut encore avoir des choses à en apprendre. Et quand on apprend un nouveau langage, on n’est jamais au bout de ses surprises.

Le code source est disponible sous forme de Gist.

J’avais publié une première version de ce billet sur mon blog personnel.

Remerciement

Je remercie mon collègue Anthony Tenneriello pour sa relecture attentive et ses remarques.