Vous savez, on veut parfois parcourir tous les trucs, et leur appliquer tous les machins. Ca donne une boucle imbriquée :

res = []
for truc in trucs:
    for machin in machins:
        res.append(bidule(machin, truc))

Un code parfaitement légitime, clair, lisible. Mais l’envie de faire une liste en intension est si forte !

C’est là que product() intervient, avec ses petits bras musclés :

from itertools import product
res  = [ bidule(machin, truc) for truc, machin in product(trucs, machins)]

Python va magiquement créer autant de tuples (machin, truc) qu’il y en a besoin.

Et parce que ça fait un mois que j’ai pas mis d’article, faut prendre tout de suite les bonnes habitudes :

for but in buts

Bref, c’était un petit article qui donnait une recette de parcours d’un itérable par morceaux.

Au programme :

• Correction de l’API de l’itérateur (__next__, next).
• On remplace xrange() par range().
• open() prend l’encoding en paramètre.
• Mise à jour du code montré pour retourner des tuples.
• Quelques corrections d’orthographe.
• Ajout de liens vers quelques notions expliquées ailleurs sur le blog.

Ce n’est pas dans le top 10 des trucs à lire à tout prix, mais c’est instructif si vous avez 10 minutes à tuer.

Puis une petit vidéo – c’est devenu traditionnel – qui illustre c’est qu’est un fish net (la tenue de la miss) :

C’est l’exemple typique du truc sexy en théorie et super pourri en pratique : ça racle, ça gratte, ça irrite, et on peut pas caresser ou trouver une prise pour les mains. Super frustrant.

Du coup, on utilise pas beaucoup while, à part dans quelques cas particuliers.

Le cas d’école, c’est la lecture d’un fichier octet par octet.

Imaginez, vous créez un petit array de float écrits en 64 bits :

>>> import numpy as np
>>> a = np.sin(np.linspace(2.0, 3.0, num=100))
>>> a.dtype
dtype('float64')

Vous sauvegardez tout ça dans un fichier :

>>> a.tofile('/tmp/data')

Si vous voulez lire le fichier hors de numpy, il faut le charger float par float, donc le lire 64 bits par 64 bits soit par groupes de 8 octets.

La méthode canonique :

with open('/tmp/data', 'rb') as f:
    while True:
        nombre = f.read(8)
        if not nombre:
            break
        # faire un truc avec le nombre

Mais il existe une autre manière de faire cela, moins connue : utiliser iter().

with open('/tmp/data', 'rb') as f:
    for nombre in iter(lambda: f.read(8), b''):
        # faire un truc avec nombre

Cela marche car iter(), parmi ses nombreuses fonctionnalités, accepte un callable en paramètre (ici notre lambda), et va l’appeler jusqu’à ce que celui-ci retourne une valeur dite “sentinelle” (ici notre second paramètre).

Le principe de base

Normalement, si vous voulez mettre le contenu d’un tuple dans des variables, vous devez procéder ainsi :

>>> ducks = ('riri', 'fifi', 'loulou')
>>> duck1 = ducks[0]
>>> duck2 = ducks[1]
>>> duck3 = ducks[2]
>>> print(duck1)
'riri'
>>> print(duck2)
'fifi'
>>> print(duck3)
'loulou'

L’unpacking, qu’on pourrait traduire par le terme fort moche de “déballage”, dans le sens “ouvrir un colis”, permet de faire la même chose, bien plus facilement :

>>> duck1, duck2, duck3 =  ducks
>>> print(duck1)
'riri'
>>> print(duck2)
'fifi'
>>> print(duck3)
'loulou'

Il n’y a rien à faire, c’est automatique. La seule condition est que le nombre de variables à gauche du signe égal soit le même que le nombre d’éléments dans la collection de droite.

D’ailleurs, ça marche même avec un seul élément :

>>> ducks = ('riri',)
>>> duck1, = ducks # notez la virgule
>>> duck1
'riri'

Et ça marche avec n’importe quel itérable, pas uniquement les tuples. Avec une liste, une string, un générateur…

>>> a, b, c, d = [1, 2, 3, 4]
>>> c
3
>>> a, b = "12"
>>> b
'2'
>>> def yolo():
    yield "leroy"
    yield "jenkins"
...
>>> nom, prenom = yolo()
>>> nom
'leroy'
>>> prenom
'jenkins'

Ça marche bien entendu avec un dico ou un set, mais comme ils ne sont pas ordonnés, c’est pas très utile.

Astuces autour de l’unpacking

On peut utiliser l’unpacking dans des endroits inattendus. Par exemple, pour échanger la valeur de deux variables :

>>> a = 1
>>> b = 2
>>> a, b = (b, a)
>>> a
2
>>> a, b = b, a # les parenthèses sont facultatives dans les tuples
>>> b
2

Puisqu’on est dans les tuples sans parenthèses, on peut retourner un tuple et donner l’illusion de retourner plusieurs variables :

>>> def duckmebaby():
...     return "rifi", 'filou', 'louri'
...
>>> et, hop, la = duckmebaby()
>>> et
'rifi'
>>> hop
'filou'
>>> la
'louri'

Allons plus loin.

On peut utiliser l’unpacking à l’intérieur d’une boucle for. Souvenez vous que les itérables peuvent contenir d’autres itérables. Par exemple, j’ai une liste qui contient 3 tuples, chaque tuple contient deux éléments :

>>> scores = [('Monique', '3'), ('David', 10), ('Dick', 1)]
>>> for score in scores:
...     print(score)
...
('Monique', '3')
('David', 10)
('Dick', 1)

Si je veux afficher le nom et le score l’un en dessous de l’autre :

>>> for nom_et_score in scores:
...     print(nom_et_score[0])
...     print(nom_et_score[1])
...
Monique
3
David
10
Dick
1

Je peux appliquer l’unpacking dans la boucle pour rendre cette opération plus élégante :

>>> for nom, score in scores:
...     print(nom)
...     print(score)
...
Monique
3
David
10
Dick
1

Cela marche avec des itérables plus gros, bien entendu. C’est aussi particulièrement utile avec des dictionnaires car on peut les transformer en itérable de tuples :

>>> scores = {'Monique': '3', 'David': 10, 'Dick': 1}
>>> scores['Monique']
'3'
>>> scores.items() # transformation !
dict_items([('Monique', '3'), ('David', 10), ('Dick', 1)])
>>> for nom, score in scores.items():
...     print(nom)
...     print(score)
...
Monique
3
David
10
Dick
1

Tout aussi utile, mais plus compliqué, est l’usage de l’unpacking dans l’appel de fonction. Pour cela, on utilise l’opérateur splat, l’étoile en Python.

Soit une fonction qui additionne des nombres :

>> def add(a, b, c):
...     return a + b + c
...
>>> add(1, 2, 3)
6

Oui, imaginons que je suis complètement débile, et que j’ai cette fonction pérave dans mon code. Vous noterez dans les articles que je l’utilise souvent sur le blog. C’est la fonction fourre tout pour expliquer un truc quand j’ai pas d’idée.

Maintenant, imaginez que je veuille additionner des canards. Si, ça marche en Python :

>>> 'riri' + 'fifi' + 'loulou' # what the duck ?
'rirififiloulou'

Maintenant je me refais mon tuples de canards :

>>> # nous entrerons dans la bande à picsou, youhou
>>> duckyou = ('riri', 'fifi', 'loulou')

Si je veux utiliser ma fonction pourrie pour mon use case stupide, je ferai ceci :

>>> add(duckyou[0], duckyou[1], duckyou[2])
'rirififiloulou'

Voilà une perte de productivité intolérable, c’est pas comme ça qu’on va faire fructifier son sou fétiche.

On peut forcer l’unpacking avec l’étoile :

>>> add(*duckyou)
'rirififiloulou'

Si on oublie l’étoile, le premier paramètre reçoit tout le tuple, et les autres paramètres rien :

>>> add(duckyou)
Traceback (most recent call last):
  File "", line 1, in 
    add(1)
TypeError: add() missing 2 required positional arguments: 'b' and 'c'

Les fonctions ont même le droit à un bonus car on peut unpacker des dictionnaires en utilisant la double étoile. Ca ne marche qu’avec les fonctions, et ça va déballer le dico pour que chaque paire clé/valeur soit passée comme nom et valeur de l’argument :

>>> def pas_add(arg1, arg2):
    print(arg1)
    print(arg2)
...
>>> pas_add(arg1="Je suis la valeur 1", arg2="Je m'en branle de qui tu es")
Je suis la valeur 1
Je m'en branle de qui tu es
>>> dicocorico = {'arg1': 'cotcot', 'arg2': 'ouai je pête un cable, l\'avion me soule'}
>>> pas_add(**dicocorico)
cotcot
ouai je pête un cable, l'avion me soule

Quand on unpacke des paramètres, il faut s’assurer que le nombre d’arguments passé n’est pas supérieur à ceux existant, sinon ça plante :

>>> dicocorico = {'arg1': 'cocot', 'arg2': 'ouai je pête un cable, l\'avion me soule', 'dang': 'je suis en trop et ça fait chier tout le monde'}
>>> pas_add(**dicocorico)
Traceback (most recent call last):
  File "", line 1, in 
    pas_add(**dicocorico)
TypeError: pas_add() got an unexpected keyword argument 'dang'
>>> stuplet = (1, 2, 3)
>>> pas_add(*stuplet)
Traceback (most recent call last):
  File "", line 1, in 
    pas_add(*stuplet)
TypeError: pas_add() takes 2 positional arguments but 3 were given

Par contre, rien ne vous empêche de fournir moins d’arguments et de remplir les autres à la main :

>>> def encore_add(a, b, c, d):
    return a + b + 0 + c + d # je feinte
...
>>> encore_add(10, *stuplet)
16

Et on peut bien entendu faire le mega mix. Par exemple, prenons la fonction print, dont la signature accepte une infinité d’arguments positionnels et quelques arguments nommés :

print(value, ..., sep=' ', end='\n', file=sys.stdout, flush=False)

Aller, on va lui unpacker sa mère :

>>> ducks = ['riri', 'fifi', 'loulou'] # is this duck typing ?
>>> keywords = {'sep': ' / ', "end": " : vous êtes du coin ? \n"}
>>> print('picsou', *ducks, **keywords)
picsou / riri / fifi / loulou : vous êtes du coin ?

Ça c’est fait.

Python 3, c’est du chocolat

En Python 3, l’unpacking a été amélioré, et on peut maintenant faire de l’unpacking partiel :

>>> # exemple 100% repompé d'un autre article du blog. Duck it.
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> a, *b = l
>>> a
0
>>> b
[1, 2, 3, 4]
>>> a, *b, c = l
>>> a
0
>>> b
[1, 2, 3]
>>> c
4

Ce qui peut être très pratique sur les longs itérables. Comment obtenir la dernière ligne d’un fichier ?

>>> *contenu, dernire_ligne = open('/etc/fstab')
>>> dernire_ligne
'UUID=0e8c3132-8fa2-46d5-a541-2890db9b371f none            swap    sw              0       0\n'

Ou alors, dans une boucle :

>>> for initiale, *reste in ducks:
    print(initiale)
...
r
f
l

En Python on aime le duck typing. On ne va donc pas s’intéresser à un type, mais à un comportement.

Quand vous voyez un suffixe “-able” en anglais, ça veut dire “accepte qu’on lui fasse quelque chose”. Par exemple, “fuckable” = “baisable”.

Sur ce morceau de poésie, je vous offre un peu de Vivaldi pour faire glisser profondément ce gros article qui va lister les chosables les plus connus.

Iterable

Le plus important en Python.

Un itérable est ce qui accepte l’itération, ce sur quoi on peut itérer, c’est à dire une collection dont on peut prendre les éléments un à un.

Pour faire simple, tout ce sur quoi on peut appliquer une boucle for.

L’exemple le plus connu sont les listes :

for x in ['une', 'liste']:
    print(x)
une
liste

Mais cela s’applique à bien d’autres types :

for x in 'unechaine':
...     print(x)
...
u
n
e
c
h
a
i
n
e
for x in ('un', 'tuple'):
...     print(x)
...
un
tuple
for x in {'un': 'dico', 'par': 'cle'}:
...     print(x)
...
un
par
for x in set(('un', 'set')):
...     print(x)
...
un
set
with open('/tmp/test', 'w') as f:
    f.write('un\nfichier')
...
for x in open('/tmp/test'):
...     print(x, end="")
...
un
fichier

Les tuples, dicos, sets, fichiers, et strings sont itérables. Beaucoup de structures de données du module collections (deque, namedtupple, defaultdict) sont itérables.

Mais surtout, les générateurs sont itérables :

def generator():
    yield 1
    yield 2
 
for x in generator():
    print(x)
1
2

Pour vérifier si quelque chose est itérable, on peut utiliser la fonction iter(). Cette fonction prend un iteérable, et retourne un générateur (appelé “iterator”) qui permet d’énumérer chaque élément de l’iterable :

lst = ['ceci', 'est', 'aussi', 'une', 'liste']
generateur = iter(lst)
next(generateur)
'ceci'
next(generateur)
'est'
next(generateur)
'aussi'
next(generateur)
'une'

iter() lève TypeError sur un non iterable :

iter(1)
Traceback (most recent call last):
  File "", line 1, in 
    iter(1)
TypeError: 'int' object is not iterable

Pour la culture, c’est ainsi que la boucle for fonctionne : à coup de next() sur un itérateur.

On peut rendre n’importe quelle objet itérable en définissant la méthode __iter__, qui doit retourner un générateur :

class NouvelIterable:
    def __iter__(self):
        # mettre des yield marche aussi
        return iter([1, 2, 3])
 
for x in NouvelIterable():
    print(x)
1
2
3

Les itérables sont les bidulables les plus important en Python car de très nombreuses fonctions les acceptent :

list(sorted(('AZERTY'))) # tri
['A', 'E', 'R', 'T', 'Y', 'Z']
list(reversed('AZERTY')) # inversion
['Y', 'T', 'R', 'E', 'Z', 'A']
list(zip('AZERTY', (100, 300, 600))) # lier deux itérables
[('A', 100), ('Z', 300), ('E', 600)]
any(set((1, 0, 1, 0, 1, 1, 2))) # un élément au moins est vrai ?
True
all(set((1, 0, 1, 0, 1, 1, 2)) # tous les éléments sont vrais ?
)
False

Et elles retournent souvent des itérables également :)

La plupart des itérables sont compatibles entre eux. Y compris les générateurs. Qui souvent traitent eux même des itérables et retournent des itérables. Cela permet de faire d’énormes pipelines de traitements connectés les uns aux autres :

s = '123456789'
res = (int(x) * x for x in s)
tuple(reversed(list(res)))[:4]
('999999999', '88888888', '7777777', '666666')

Mutable

Dont on peut changer la valeur.

Quand on assigne une variable en Python, on ne change pas la valeur de l’objet, on change la valeur de la variable :

a = 1
a = 2

Ici 1 n’a pas changé, la valeur stockée dans a a changé.

C’est différent de ceci :

a = [1]
a[0] = 2
a
[2]

Ici, c’est la même liste qui est dans a, mais la valeur stockée dans la liste a changé.

Cette notion est importante car en Python, les variables ne contiennent en fait pas vraiment des valeurs, mais des références à ces valeurs.

Si je change le contenu de la variable, il n’y a pas d’effet de bords :

a = [1, 2, 3]
b = a # b et a contienne une référence à la même liste
b
[1, 2, 3]
a = [4, 5, 6] # le contenu de a change
b
[1, 2, 3] # b et a ont une contenu différents

Si je change la valeur de ma structure de données, ici ma liste, alors il y a un effet de bord :

a = [1, 2, 3]
b = a
a[0] = 1000
b # a et b référencent la même liste
[1000, 2, 3]

En effet, a ne contient pas la liste, mais une référence à la liste. Quand on copie le contenu de a vers b, on ne copie pas la liste, mais cette référence. Donc a et b sont des variables qui pointent vers la même liste.

Il est alors important de savoir quelles opérations modifient quelque chose, et lesquelles ne les modifient pas.

Les listes, les dictionnaires et les sets sont modifiables, on dit qu’il sont “mutables”.

On peut le voir avec la fonction id() qui renvoie le numéro unique de l’objet :

une_liste = []
id(une_liste)
140693805855368
une_liste.append(1)
une_liste
[1]
id(une_liste)
140693805855368

La liste a changé, mais l’id est le même, c’est le même objet.

Les opérations qui “changent la valeur” sur les types mutables sont performantes en Python car il n’y a pas besoin de recréer un objet à chaque fois.

Les tuples, les nombres, les chaînes de caractères ne sont pas modifiables. Il ne sont pas “mutables” :

id(une_liste)
140693805855368
un_tuple = (1, 2, 3)
id(un_tuple)
140693772746040
un_tuple += (4, 5, 6)
un_tuple
(1, 2, 3, 4, 5, 6)
id(un_tuple)
140693772879144

Le tuple n’a pas changé : l’id n’est pas le même car la variable un_tuple contient un nouvel objet.

Les opérations qui “changent la valeur” sur les types non mutables sont moins performantes en Python car il faut recréer un objet à chaque fois.

Par défaut, toute classe que vous écrivez crée un objet mutable.

Callable

Tout ce qui peut être appelé, c’est à dire qu’on peut mettre () après le nom de la variable qui le contient pour obtenir un effet.

Ce qui vient en premier en tête ce sont les fonctions (ou les méthodes):

def foo():
...     print("Je suis appelée")
...
foo() # j'appelle ma fonction
Je suis appelée

Mais, en Python, le concept d’appeler va plus loin.

Une classe est un callable :

class Bar:
    def __init__(self):
        print("Je suis appelée")
Bar() # j'instancie en utilisant ()
 
Je suis appelée

Un type est un callable :

set()
set()

Et on peut rendre n’importe quel objet callable en définissant la méthode __call__ :

class UnCallableQuiCreerUnCallable:
    def __call__(self):
        print('Je suis appelé')
 
callable = UnCallableQuiCreerUnCallable()
callable()
Je suis appelé

Donc quand on vous dit : “ceci attend un callable en paramètre”, vous pouvez passer n’importe quel type de callable. Pas juste une fonction. On peut créer des décorateurs avec et pour n’importe quel callable.

Si on essaye d’appeler un objet qui n’est pas un callabe, on obtient un TypeError :

lst
[1]
lst()
Traceback (most recent call last):
  File "", line 1, in 
    lst()
TypeError: 'list' object is not callable

Hashable

Les clés des dictionnaires n’ont pas besoin d’être des chaînes de caractères. Elles peuvent être n’importe quel objet hashable. Pour les types de base, ce sont les non mutables, soit les strings, mais aussi ints, floats ou tuples :

dico = {('une', 'cle', 'qui', 'est', 'un', 'tuple'): 1}
len(dico)
1
dico[('une', 'cle', 'qui', 'est', 'un', 'tuple')]
1

Pour obtenir cet effet, le dictionnaire prend l’objet passé en clé, et calcule un hash, une empreinte unique de l’objet. Pour que cela marche, il faut que le hash d’un objet donne toujours le même résultat si il est appliqué deux fois au même objet, ou à deux objets parfaitement égaux.

Un objet hashable est donc un objet qu’on peut utiliser comme clé de dictionnaire. C’est un objet qu’on peut passer à la fonction hash(). Dans la stdlib, les types non mutables sont hashable, et les types mutables ne le sont pas :

hash("fdkslmf")
4874978338908949266
hash([])
Traceback (most recent call last):
  File "", line 1, in 
    hash([])
TypeError: unhashable type: 'list'

Mais on peut créer sa propre définition de ce qu’est un objet hashable avec la méthode __hash__, qui doit retourner un entier :

class Personne:
    def __init__(self, nom, prenom, age):
        self.nom = nom
        self.prenom = prenom
        self.age = age
    def __hash__(self):
        return sum((ord(x) for x in (self.nom + self.prenom))) + self.age
...
hash(Personne("bob", "sinclaire", 78))
1339

Vous avez néanmoins intérêt à savoir ce que vous faites en faisant ça, c’est un nid de frelons.

Subscriptables

Ce dont on peut récupérer une partie avec []. Essayer sur un objet qui ne l’est pas peut lever TypeError: 'x' object is not subscriptable ou une sous erreur.

Car on peut utiliser [] de deux façons.

Indexable

Dont on peut récupérer un élément à une position particulière, avec la syntaxe []. Dans la stdlib, les listes, les chaînes de caractères, les tuples et les dictionnaires sont indexables mais pas les sets :

"fdjskl"[0]
'f'
('1', '2')[0]
'1'
{'yo': 'man'}['yo']
'man'
s = set((1, 2))
s[0]
Traceback (most recent call last):
  File "", line 1, in 
    s[0]
TypeError: 'set' object does not support indexing

On peut définir son propre comportement d’indexation avec __getitem__ :

class MainGauche:
    def __getitem__(self, index):
        return "Index de la main gauche"
 
main = MainGauche()
print(main[0])
Index de la main gauche

Sliceable

Dont on peut récupérer un sous ensemble des éléments avec la syntaxe [start:stop:step]. Un sliceable est souvent indexable, mais l’inverse n’est pas forcément vrai. Dans la stdlib, les listes, les strings et les tuples sont sliceables, mais pas les dictionnaires ni les sets :

"fdjskl"[1::2]
'dsl'
('1', '2', True, False)[:-1]
('1', '2', True)
{'yo': 'man'}[1:2]
Traceback (most recent call last):
  File "", line 1, in 
    {'yo': 'man'}[1:2]
TypeError: unhashable type: 'slice'

Le slice s’implémente comme l’index, avec __getitem__. La différence est qu’au lieu de recevoir une valeur ordinaire, vous allez recevoir un objet slice :

class MainDroite:
    def __getitem__(self, slice):
        print(slice.start, slice.stop)
        return "Slice de la main droite. Heu..."
 
main = MainDroite()
print(main[2:6])
2 6
Slice de la main droite. Heu...

• Qu’est-ce qu’un doublon ?
• Quels types d’itérables traite-t-on ?
• Quel est la taille de l’itérable ?
• Et niveau perfs ?

En Python, on a des structures de données qui suppriment automatiquement les doublons : les sets et les dictionnaires. Mais elles ne conservent pas l’ordre des élements.

Il y a aussi le fait qu’un itérable en Python peut avoir une taille inconnue, ou infinie.

Le post est long, donc…

Solution 1 : générateur et hashing

En utilisant conjointement les générateurs, les sets et une petite injection de dépendance, on peut trouver un compromis entre flexibilité et performances :

def skip_duplicates(iterable, key=lambda x: x):
 
    # on va mettre l’empreinte unique de chaque élément dans ce set
    fingerprints = set()
 
    for x in iterable:
        # chaque élement voit son emprunte calculée. Par défaut l’empreinte
        # est l'élément lui même, ce qui fait qu'il n'y a pas besoin de
        # spécifier 'key' pour des primitives comme les ints ou les strings.
        fingerprint = key(x)
 
        # On vérifie que l'empreinte est dans la liste des empreintes  des
        # éléments précédents. Si ce n'est pas le cas, on yield l'élément, et on
        # rajoute sont empreinte ans la liste de ceux trouvés, donc il ne sera
        # pas yieldé si on ne le yieldera pas une seconde fois si on le
        # rencontre à nouveau
        if fingerprint not in fingerprints:
            yield x
            fingerprints.add(fingerprint)

La fonction s’appelle skip_duplicates car c’est ce qu’elle fait. Elle ne retire pas vraiment les doublons, elle produit un flux de d’éléments qui ne comporte pas de doublons en ignorant tout doublons présent dans l’itérable initial.

Cette approche a plusieurs avantages :

• Les doublons sont bien retirés, et l’ordre est conservé.
• La complexité est de 0(n).
• L’utilisateur peut choisir ce qui fait qu’un élément est unique : un attribut, un sous-élément, l’affichage sous forme de string…
• C’est un générateur, est cela fonctionne donc avec des itérables de toute taille, même inconnue ou infinie.

Il faut néanmoins que l’ensemble des éléments uniques tiennent au moins une fois en mémoire en plus de l’itérable initial, et potentiellement d’un stockage à la sortie du générateur. On fait donc un trade-off sur la mémoire.

Comme la valeur de key par défaut est une valeur saine, ça fonctionne comme on s’y attend pour les cas simples :

>>> list(skip_duplicates([1, 2, 3, 4, 4, 2, 1, 3 , 4]))
[1, 2, 3, 4]
>>> list(skip_duplicates('fjsqlkdmfjsklqmdfjdmsl'))
[u'f', u'j', u's', u'q', u'l', u'k', u'd', u'm']
>>> list(skip_duplicates(((1, 2), (2, 1), (1, 2), (1, 1))))
[(1, 2), (2, 1), (1, 1)]

Pourvoir spécifier ‘key’ permet de faire des choix dans ce qu’est un doublon :

>>> list(skip_duplicates((1, 2, '1', '1', 2, 3, '3')))
[1, 2, u'1', 3, u'3']
>>> list(skip_duplicates((1, 2, '1', '1', 2, 3, '3'), key=lambda x: str(x)))
[1, 2, 3]

Et si on s’attaque à des cas plus complexes, le fonction vous force à préciser votre pensée :

>>> list(skip_duplicates(([], [], (), [1, 2], (1, 2)))
... )
Traceback (most recent call last):
  File "<ipython-input-20-ed44f170c634>", line 1, in <module>
    list(skip_duplicates(([], [], (), [1, 2], (1, 2)))
  File "<ipython-input-18-42dbb94f03f8>", line 7, in skip_duplicates
    if fingerprint not in fingerprints:
TypeError: unhashable type: 'list'

En effet les listes ne sont pas des types hashables en Python, on ne peut donc pas les stocker dans un set.

Mais on peut caster la liste, et faire ainsi le choix de savoir sur quel critère on base notre égalité. Par exemle, considère-t-on que deux itérables ayant le même contenu sont égaux, où alors doivent-ils avoir le même type ?

>>> list(skip_duplicates(([], [], (), [1, 2], (1, 2)), lambda x: tuple(x)))
[[], [1, 2]]
>>> list(skip_duplicates(([], [], (), [1, 2], (1, 2)), lambda x: (type(x), tuple(x))))
[[], (), [1, 2], (1, 2)]

Nous utilisons le fait que :

>>> tuple([1, 2]) == (1, 2)
True
>>> (type([1, 2]), tuple([1, 2])) == (type((1, 2)), (1, 2))
False

Puisque :

>>> (type([1, 2]), tuple([1, 2]))
(<type 'list'>, (1, 2))
>>> (type((1, 2)), (1, 2))
(<type 'tuple'>, (1, 2))

Dans le cas où nous ne sommes pas capables de déterminer ce qu’est un doublon, la fonction ne retire simplement rien :

class Test(object):
    def __init__(self, foo='bar'):
        self.foo = foo
    def __repr__(self):
        return "Test('%s')" % self.foo
 
>>> list(skip_duplicates([Test(), Test(), Test('other')]))
[Test('bar'), Test('bar'), Test('other')]

Mais permet encore une fois de faire le choix de quoi retirer :

>>> list(skip_duplicates([Test(), Test(), Test('other')], key=lambda x: x.foo))
[Test('bar'), Test('other')]

Ce principe de la fonction key, on le retrouve dans sorted(), donc les habitués seront déjà à l’aise. Et j’aime beaucoup ce pattern, car il est très puissant. On peut avoir la fonction key qui renvoit des choses très simples :

• Un attribut.
• Un element (x[2], x['cle']…)
• Une version castée avec int(), str(), tuple(), etc

Mais on peut aussi faire des choses très complexes. En effet, rien ne nous oblige à utiliser une lambda, on peut mettre une fonction complète et lui faire retourner :

• Un hash md5.
• Une entrée en base de données.
• Un nouvel objet customisé.
• Un tuple de tuples d’objets custos avec des dictionnaires en attributs…
• Le contenu d’un fichier.

Python sait naturellement comparer tout ça.

Notez que nous trichons un peu, puisque nous retirons les doublons en nous basant sur un set qui va calculer un hash de l’objet, et pas véritablement vérifier l’égalité. La fonction en fonctionnera donc pas si l’utilisateur définie __eq__ et s’attend à ce que les doublons soient retirés. Ce qui nous amène à …

Solution 2 : iterateur et comparaison

Pour ce genre de chose, un autre algo, qui ne fontionerait que sur les itérables de taille finie, et qui serait bien plus lent (complexité n log(n)), peut être utilisé :

def strip_duplicates(iterable, equals=lambda x, y: x == y):
 
    # On transforme l'itérable en iterateur sur lui même, cela va nous
    # permettre d'appeler next() dessus et récupérer le premier élément,
    # même sur un objet non indexable (sur lequel on ne peut utiliser [0])
    iterable = iter(iterable)
 
    res = []
    # Une petite boucle infinie est nécessaire car la boucle 'for' ne nous
    # permet pas de récupérer le premier élément indépendamment des autres,
    # et la boucle 'while' attend une condition de sortie, ce que nous n'avons
    # pas forcément (il n'est pas possible de vérifier le nombre d'éléments
    # restant dans un générateur).
    while True:
 
        # on récupère le premier élément de l'iterable restant, si il n'y en
        # a plus, on sort de la boucle.
        try:
            elem = next(iterable)
        except StopIteration:
            break
 
        # Le premier élément est ajouté au résultat sans doublons. Maintenant
        # on va recréer l'itérable, mais en retirant tout ce qui était égal
        # au premier élément. Notez que 'être égal' est une condition modifiable
        # en passant une fonction en paramètre, comme l'était 'key' précédemment.
        res.append(elem)
 
        iterable = iter([x for x in iterable if not equals(elem, x)])
 
    return res

La fonction s’appelle strip_duplicates car elle produit une nouvelle liste, mais sans les éléments indésirables, comme le fait strip() sur une chaîne (produit une nouvelle chaîne, sans les éléments indésirables).

Ce type de fonction peut être utile dans plusieurs cas :

• On a pas envie de se poser la question de savoir si nos types à comparer sont hashable ou pas, et on est prêt à payer un peu de CPU pour cela.
• On a besoin de retirer les doublons sur la base d’une égalité, par exemple sur l’existence de la méthode __eq__.
• On a besoin de retirer les doublons sur la base d’une logique complexe qui dépend du contexte.

A première vu cela fonctionne presque de la même manière que skip_duplicates, mais en retournant une liste plutôt qu’un générateur :

>>> strip_duplicates('fdjqkslfjdmkfdsqjkfmjqsdmlkfjqslkmfjsdklfl')
['f', 'd', 'j', 'q', 'k', 's', 'l', 'm']

Mais déjà il n’y a pas à se soucier de savoir si une structure de données est hashable :

>>> strip_duplicates(([], [], (), [1, 2], (1, 2)))
[[], (), [1, 2], (1, 2)]

Même si on garde la même flexibilité, bien que la fonction à passer ait une signature légèrement différente :

>>> strip_duplicates(([], [], (), [1, 2], (1, 2)), lambda x, y: tuple(x) == tuple(y))
[[], [1, 2]]

Le plus interessant reste que cela fonctionne sur l’égalité, et donc cela marche d’office avec les objets qui déclarent __eq__ ce qui est le cas dans de nombreuses libs, comme les ORM :

class Test(object):
    def __init__(self, foo='bar'):
        self.foo = foo
    def __repr__(self):
        return "Test('%s')" % self.foo
    def __eq__(self, other):
        return self.foo == other.foo
 
>>> strip_duplicates([Test(), Test(), Test('other')])
[Test('bar'), Test('other')]

Dans certains cas, notamment dans le cas où le point de comparaison est un object non hashable de très grosse taille (par exemple un dico très long), on peut espérer aussi pas mal économiser en mémoire. Mais on est qu’en est-il des besoins en mémoire et en CPU ?

Solution 3 : retirer les doublons, in place

Enfin, pour ceux qui ont de grosses contraintes de mémoire et qui veulent un algo rapide au prix de la flexibilité du code, voici une solution qui oblige à travailler sur des listes et à modifier la liste sur place :

def remove_duplicates(lst, equals=lambda x, y: x == y):
 
    # Normalement en Python on adore le duck typing, mais là cet algo suppose
    # l'usage d'une liste, donc on met un gardefou.
    if not isinstance(lst, list):
        raise TypeError('This function works only with lists.')
 
    # là on est sur quelque chose qui ressemble vachement plus à du code C ^^
    i1 = 0
    l = (len(lst) - 1)
 
    # on itère mécaniquement sur la liste, à l'ancienne, avec nos petites
    # mains potelées.
    while i1 < l:
 
        # on récupère chaque élément de la liste, sauf le dernier
        elem = lst[i1]
 
        # on le compare à l'élément suivant, et chaque élément après
        # l'élément suivant
        i2 = i1 + 1
        while i2 <= l:
            # en cas d'égalité, on retire l'élément de la liste, et on
            # décrément la longueur de la liste ainsi amputée
            if equals(elem, lst[i2]):
                del lst[i2]
                l -= 1
            i2 += 1
 
        i1 += 1
 
    return lst

Et là on est bien dans de la modification sur place :

>>> lst = list('fjdsklmqfjskdfjmld')
>>> lst
[u'f', u'j', u'd', u's', u'k', u'l', u'm', u'q', u'f', u'j', u's', u'k', u'd', u'f', u'j', u'm', u'l', u'd']
>>> remove_duplicates(lst)
[u'f', u'j', u'd', u's', u'k', u'l', u'm', u'q']
>>> lst
[u'f', u'j', u'd', u's', u'k', u'l', u'm', u'q']

La fonction s’appelle cette fois bien remove_duplicates puisque c’est ce qu’elle fait : retirer les doublons de la liste originale.

Et maintenant, c’est l’heure du benchmark à deux balles !

skip_duplicates :

setup = """
def skip_duplicates(iterable, key=lambda x: x):
        fingerprints = set()
        for x in iterable:
                fingerprint = key(x)
                if fingerprint not in fingerprints:
                        yield x
                        fingerprints.add(fingerprint)
import string
lst = list(string.ascii_letters * 100)"""
>>> timeit.timeit('list(skip_duplicates(lst))', setup=setup, number=1000)
0.9810519218444824

strip_duplicates :

>>> setup = """
def strip_duplicates(iterable, equals=lambda x, y: x == y):
    iterable = iter(iterable)
    res = []
    while True:
        try:
            elem = next(iterable)
        except StopIteration:
            break
        res.append(elem)
 
        iterable = iter([x for x in iterable if not equals(elem, x)])
 
    return res
 
import string
lst = list(string.ascii_letters * 100)"""
>>> timeit.timeit('list(strip_duplicates(lst))', setup=setup, number=1000)
41.462974071502686

remove_duplicates :

setup = """
def remove_duplicates(lst, equals=lambda x, y: x == y):
    if not isinstance(lst, list):
        raise TypeError('This function works only with lists.')
    i1 = 0
    l = (len(lst) - 1)
    while i1 < l:
        elem = lst[i1]
        i2 = i1 + 1
        while i2 <= l:
            if equals(elem, lst[i2]):
                del lst[i2]
                l -= 1
            i2 += 1
        i1 += 1
    return lst
 
import string
lst = list(string.ascii_letters * 100)"""
>>> timeit.timeit('list(remove_duplicates(lst))', setup=setup, number=1000)
0.37493896484375

Sans surprise, la version inplace est la plus rapide puisque la plus restrictive. En second vient notre strip_duplicates, beaucoup fois plus lente. Et en dernier, 50 fois plus lente, le compromis entre les deux : souple, consomme moins de mémoire que skip, mais plus que remove.

Mais ce n’est pas très juste pour strip, puisque que skip n’a pas à faire un gros travail de conversion. Essayons avec des clés plus grosses :

skip_duplicates :

setup = """
def skip_duplicates(iterable, key=lambda x: x):
        fingerprints = set()
        for x in iterable:
                fingerprint = key(x)
                if fingerprint not in fingerprints:
                        yield x
                        fingerprints.add(fingerprint)
import string, random
lst = [list(string.ascii_letters * 100) for x in xrange(100)]
for x in lst:
    x.pop(random.randint(0, len(x) - 1))"""
>>> timeit.timeit('list(skip_duplicates(lst, lambda x: tuple(x)))', setup=setup, number=1000)
15.516181945800781

strip_duplicates :

>>> setup = """
def strip_duplicates(iterable, equals=lambda x, y: x == y):
    iterable = iter(iterable)
    res = []
    while True:
        try:
            elem = next(iterable)
        except StopIteration:
            break
        res.append(elem)
 
        iterable = iter([x for x in iterable if not equals(elem, x)])
 
    return res
 
import string, random
lst = [list(string.ascii_letters * 100) for x in xrange(100)]
for x in lst:
    x.pop(random.randint(0, len(x) - 1))"""
>>> timeit.timeit('list(strip_duplicates(lst))', setup=setup, number=1000)
22.047110080718994

remove_duplicates :

setup = """
def remove_duplicates(lst, equals=lambda x, y: x == y):
    if not isinstance(lst, list):
        raise TypeError('This function works only with lists.')
    i1 = 0
    l = (len(lst) - 1)
    while i1 < l:
        elem = lst[i1]
        i2 = i1 + 1
        while i2 <= l:
            if equals(elem, lst[i2]):
                del lst[i2]
                l -= 1
            i2 += 1
        i1 += 1
    return lst
 
import string, random
lst = [list(string.ascii_letters * 100) for x in xrange(100)]
for x in lst:
    x.pop(random.randint(0, len(x) - 1))"""
>>> timeit.timeit('list(remove_duplicates(lst))', setup=setup, number=1000)
14.763166904449463

Comme souvent les résultats sont contre untuitifs, car bien que remove garde son avance, elle s’est largement réduite. A l’inverse, skip n’est pas tant à la ramasse que ça, et strip reste le plus lent.

Il faudrait aussi mesurer la consommation mémoire, je suis certain que ce serait interessant.

Bon, il est temps de mettre tout ça dans batbelt.

Bonne pêche !

Voici des fonctions qui s’utilisent sur des itérables, n’importe lequel, même un dont la taille est inconnu ou infini. La première retourne le premier élément, et, si l’itérable est vide, elle retourne une valeur par défaut :

def first(iterable, default=None):
    for x in iterable:
        return x
    return default

C’est une sorte de [0], mais valable pour tous les itérables, par juste les indexables comme les tuples, les strings ou les listes. Et en prime, pas besoin de faire un try / catch dessus puisqu’il permet une valeur par défaut :

>>> first([0, 1, 2, 3])
0
>>> first([], 'flammkuchen')
'flammkuchen'

Le second est aussi sympathique, il fait la même chose, mais retourne l’élément seulement si il est vrai :

def first_true(iterable, key=lambda x: x, default=None):
    for x in iterable:
        if key(x):
            return x
    return default

key fonctionne comme pour la fonction sorted(), à savoir que c’est une injection de dépendance. C’est cette fonction qui va déterminer si l’élément est vrai ou non. Par défaut la fonction retourne l’élément tel quel, et le fait qu’il soit vrai ou non sera donc déterminé par son contexte booléen :

>>> first_true([0, 1, 2, 3])
1
>>> first_true([(0, 1), (2, 3)])
(0, 1)
>>> first_true([(0, 1), (2, 3)], lambda x: x[0])
(2, 3)
>>> first_true([], lambda x: x[0], 'socca')
u'socca'

Ce petit article m’a fait réaliser qu’on pourrait sans problème fusionner les deux en faisant :

def first(iterable, key=lambda x: True, default=None):
    for x in iterable:
        if key(x):
            return x
    return default

Mais j’ai pas la foi de faire un commit ce soir, donc fuck.

pip install batbelt

Et la plupart des fonctions sont accessible avec un from batbelt import...

Voici les choses qui pourraient vous intéresser le plus dans batbelt…

To timestamp

Mais combien de fois j’ai du la coder celle-là ? En plus l’inverse existe, alors pourquoi, mon Dieu, pourquoi ?

>>> from datetime import datetime
>>> to_timestamp(datetime(2000, 1, 1, 2, 1, 1))
946692061
>>> datetime.fromtimestamp(946688461) # tu as codé celle là et pas l'autre connard !
datetime.datetime(2000, 1, 1, 2, 1, 1)

Récupérer une valeur dans une structure de données imbriquée

Au lieu de faire :

try:
    res = data['cle'][0]['autre cle'][1]
except (KeyError, IndexError):
    res = "valeur"

On peut faire :

get(data, 'cle', 0, 'autre cle', 1, default="valeur")

Récupérer la valeur d’un attribut dans un attribut dans un attribut…

Pareil, mais pour les attributs.

try:
    devise = voiture.moteur.prix.devise
except AttributeError:
    devise = "euro"

On peut faire :

devise = attr(voiture, 'moteur', 'prix', 'devise', default='euro')

Itérons, mon bon

Ces fonctions retournent des générateurs qui permettent d’itérer par morceau ou par fenêtre glissante.

>>> for chunk in chunks(l, 3):
...     print list(chunk)
...
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
[9]
>>> for slide in window(l, 3):
...     print list(slide)
...
[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
[4, 5, 6]
[5, 6, 7]
[6, 7, 8]
[7, 8, 9]

Ça devrait être en standard dans Python.

Parfois on veut juste le premier élément d’une collection. Ou juste le premier à être vrai:

>>> first(xrange(10))
0
>>> first_true(xrange(10))
1

Marche avec n’importe quel itérable, contrairement à [0] qui ne marche que sur les indexables. Et en prime on peut spécifier une valeur par défaut:

>>> first([], default="What the one thing we say to the God of Death ?")
'What the one thing we say to the God of Death ?'

Set ordonné

On a des dicts ordonnés dans la lib standard, mais pas de set ordonné. On en a pas besoin souvent, mais ça peut être TRES pratique, et TRES chiant à implémenter soi-même.

Donc acte.

>>> for x in set((3, 2, 2, 2, 1, 2)): # booooooo
...     print x
...
1
2
3
>>> for x in sset((3, 2, 2, 2, 1, 2)): # clap clap !
...     print x
...
3
2
1

Attention, c’est pas la structure de données la plus rapide du monde…

Je suis une feignasse et j’aime les one-liners sur les dicos

Je ne comprends pas pourquoi + ne fonctionne pas sur les dico.

>>> dmerge({"a": 1, "b": 2}, {"b": 2, "c": 3})
{'a': 1, 'c': 3, 'b': 2}

Ne modifie pas les dictionnaires originaux.

>>> from batbelt.structs import rename
>>> rename({"a": 1, "b": 2})
>>> rename({"a": 1, "b": 2}, 'b', 'z')
{u'a': 1, u'z': 2}

Modifie le dictionnaire original et n’est PAS thread safe.

Et le cas tordu mais tellement satisfaisant :

>>> from batbelt.structs import unpack
>>> dct = {'a': 2, 'b': 4, 'z': 42}
>>> a, b, c = unpack(dct, 'a', 'b', 'c', default=1)
>>> a
2
>>> b
4
>>> c
1

Slugifier

>>> slugify(u"Hélo Whorde")
helo-whorde

Il y a pas mal de réglages possibles avec slugify(), mais je vous laisse les découvrir :-) Cette fonction fait partie du sous-module strings, qui contient d’autres utilitaires comme escape_html/unescape_html (qui transforme les caractères spéciaux en HTML entities et inversement) ou json_dumps/json_loads (qui fait un dump / load du JSON en prenant en compte le type datetime).

Importer une classe ou une fonction depuis une string

Dès que vous faites un fichier de config vous avez besoin de ce genre de truc, mais la fonction __import__ a une signature uber-zarb. Voici une version beaucoup plus simple:

TaClasse = import_from_path('foo.bar.TaClasse')
ton_obj = TaClasse()

Capturer les prints

Parfois on a une lib qui print plutôt que de retourner une valeur. C’est très chiant. J’ai donc fait un context manager qui permet de récupérer tout ce qui est printé dans le block du with.

>>> with capture_ouput() as (stdout, stderr):
...    print "hello",
...
>>> print stdout.read()
hello

Créer un décorateur qui accepte des arguments

Même dans le cas où vous avez parfaitement compris les décorateurs grâce à un très bon tuto (^^), se souvenir de comment faire un décorateur qui attend des arguments en paramètre, c’est mission impossible. Voici donc un décorateur… pour créer un décorateur.

Étape un, écrire votre décorateur :

# tout les arguments après 'func' sont ceux que votre décorateur acceptera
@decorator_with_args()
def votre_decorateur(func, arg1, arg2=None):
 
    if arg1:
        # faire un truc
 
    # ici on fait juste le truc habituel des décorateurs
    # wrapper, appel de la fonction wrappée et retour du wrapper...
    def wrapper():
        # arg2 est dans une closure, on peut donc l'utiliser dans
        # la fonction appelée
        return func(arg2)
 
 
    return wrapper

Et on peut utiliser son décorateur tranquile-bilou :

@votre_decorateur(False, 1)
def hop(un_arg):
    # faire un truc dans la fonction décorée

Les processus parallèles finissent toujours par se rencontrer à l’infini et corrompre leurs données

Mais en attendant on en a quand même besoin. Parfois un petit worker, c’est sympa, pas besoin de faire compliqué et de sortir des libs de task queue complètes:

 
from batbelt.parallel import worker
 
@worker()
def une_tache(arg):
    # faire un truc avec arg
    arg = arg + 10
    return arg
 
 
# on demarre le worker
process = une_tache.start()
 
# on balance des tâches au worker
for x in range(10):
    process.put(x)
 
# on récupère les résultats (optionnel)
# ca peut être dans un fichier différent
for x in range(10):
    print process.get()
 
## 10
## 11
## 12
## 13
## 14
## 15
## 16
## 17
## 18
## 19
 
# on arrête le worker
process.stop()

Le worker est un subprocess par défaut, mais vous pouvez en faire un thread avec @worker(method=”tread”). Toujours utile, par exemple pour avec un processeur de mails qui envoit tous les mails hors du cycle requête / réponse de votre site Web. Par contre si votre process meurt la queue est perdue.

Template du pauvre

Avec format(), on a déjà un mini-langage de template intégré. Pas de boucle, mais pour des tâches simples ça suffit. Du coup j’ai une fonction render() qui prend un fichier de template au format string Python et qui écrit le résultat dans un autre. Pratique pour faire des fichiers de conf configurable.

from batbelt.strings import render
 
render('truc.conf.tpl', {"var": "value"}, "/etc/truc.conf")

Il y a aussi des implémentations de Singleton, du Null Pattern, etc. Mais ça s’utilise moins souvent alors je vais pas faire une tartine.

C’est pas compliquéééééééééééé, j’vais tout t’expliquuuuuerrrrrrrrrr.

C´est le p´tit zinzin qui passe par ici:

>>> class MonIterable(object): # faisons notre propre itérable
...
...     def __init__(self):
...         self.values = [1, 2]
...
...     def __iter__(self): # ('for' appelle __iter__ automatiquement)
...         return self # __iter__ doit renvoyer un iterateur, ici nous-même
...
...     def next(self): # chaque tour de boucle, for appelle next()
...         if self.values: # qui retourne une des valeus de self.values
...             return self.values.pop() # en l'enlevant de la liste initiale
...         raise StopIteration() # si il y en a plus, il dit stop !
...

Et qui va toucher le p´tit machinnnnnnnnnnnnnnnnnnnnnnnnn !

>>> for x in MonIterable(): # ceci appelle next() jusqu'à StopIteration
...    print x
2
1

Et le p´tit machin qui repasse par là:

>>> iterateur = iter(MonIterable()) # Voilà ce que ça donne à la main
>>> iterateur.next()
2
>>> iterateur.next()
1
>>> iterateur.next() # l'exception: mécanisme naturel de Python pour stopper une boucle !
Traceback (most recent call last):
  File "<pyshell#9>", line 19, in <module>
    iterateur.next()
  File "<pyshell#9>", line 14, in next
    raise StopIteration()
StopIteration

Et qui fait marcher ce p´tit zinzinnnnnnnnnnnnn !

>>> iterateur = iter(range(3)) # c'est pareil pour tous les iterables
>>> iterateur.next() # un iterateur est juste un truc avec une méthode next()
0
>>> iterateur.next() # next() doit retourner la prochain valeur de l'iterable
1
>>> iterateur.next() # un itérateur itère donc sur un iterable
2
>>> iterateur.next() # jusqu'à la fin, où il lève StopIteratino
Traceback (most recent call last):
  File "<ipython-input-19-6c9f9efdd35c>", line 1, in <module>
    iterateur.next()
StopIteration

Ah bon ?

Ca aurait été sur ce blog, le mec se serait pris un tampon “drozophiliafucker” dans la gueule et ça aurait été plié. Mais quand on est BDFL et, à l’époque, employé chez Google, on est obligé de donner une réponse un peu sérieuse.

Si vous avez suivi le lien précédent, vous verrez que sa réponse implique un obscure module appelé heapq. Si vous allez sur la doc du-dit module, vous verrez qu’elle implique une obscure explication innomable et vous aller retourner à la vidéo de porn que vous avez laissé bufferiser en haute résolution afin de pouvoir voir les grains de beauté qui longent le pourtour anal de la principale protagoniste. Respirons.

Il y a une explication rationnelle à tout cela

heapq est un algorithme qui organise une liste sous forme d’arbre binaire. Vous voyez c’était simple non ?

Nan je déconne, je vais pas vous laisser avec ça quand même.

Le module heapq permet d’utiliser le type “list” pour y ajouter ou retirer les éléments de telle sorte qu’ils soient toujours dans l’ordre.

Sous le capot, ça marche effectivement avec un arbre binaire, mais on s’en branle. Tout ce qu’il faut comprendre c’est:

>>> from heapq import heappush, heappop
>>> l = []
>>> heappush(l, 69)
>>> heappush(l, 42)
>>> heappush(l, 2048)
>>> heappush(l, -273.15)
>>> l # la liste est ordonnée en arbre binaire...
[-273.15, 42, 2048, 69]
>>> for x in xrange(len(l)): # et on depop pour itérer dans l'odre
    print heappop(l)
...     
-273.15
42
69
2048

Donc on a une liste, on lui met des éléments dans la tronche dans n’importe quel ordre, et bam, on peut itérer dans le bon ordre sans avoir à rien faire. Et cette insertion est assez rapide (O(lg n) pour les tatillons). Le parcours l’est également (de l’ordre de O(n log n)).

Et donc c’est très pratique pour trouver les x plus petits éléments (ou les plus grands), implémenter des queues de priorité, etc.

Exemple de queue de priorité, (courageusement volé d’ici):

import heapq
 
class PriorityQueue(list):
 
    def __init__(self, data):
        super(Heap, self).__init__()
        for i, x in enumerate(data):
            self.push(i, x)
 
    def push(self, priority, item):
        """
            On push en rajoute une priorité
        """
        heapq.heappush(self, (priority, item))
 
    def pop(self):
        """
            On pop en retirant la proprité
        """
        return heapq.heappop(self)[1]
 
    def __len__(self):
        return len(self)
 
    def __iter__(self):
        """
            Comme on a une méthode next(), on peut se retourner soi-même.
            Ainsi la boucle for appelera next() automatiquement. 
        """
        return self
 
    def next(self):
        """ 
           On depop la liste du plus petit au plus grand.
        """
        try:
            return self.pop()
        except IndexError:
            raise StopIteration
 
>>> l = PriorityQueue(("azerty"))
>>> l
>>> l.push(100, 'après')
>>> l.push(-1, 'avant')
>>> l.push(5, 'pendant')
>>> for x in l:
...     print x
...     
avant
a
z
e
r
t
pendant
y
après

Et le plus beau, c’est qu’on peut prendre plusieurs itérables ordonnés, et utiliser heapq.merge pour obtenir un générateur (qui ne charge pas tout en mémoire d’un coup) qui va permettre d’iterer de manière ordonnée sur tous les éléments.

>>> import heapq
>>> l1 = sorted([random.randint(0, 1000) for x in xrange(5)])
>>> l2 = sorted([random.randint(0, 1000) for x in xrange(5)])
>>> l3 = sorted([random.randint(0, 1000) for x in xrange(5)])
>>> list(heapq.merge(l1, l2, l3))
[52, 59, 60, 171, 174, 262, 336, 402, 435, 487, 557, 645, 899, 949, 996]

Notez que ce n’est pas du tout la même chose que de concaténer les listes:

>>> l1 + l2 + l3
[59, 174, 336, 487, 996, 52, 171, 557, 645, 949, 60, 262, 402, 435, 899]

Car des élements de l2 peuvent être inférieurs à ceux de l1. heap.merge nous ordonne tout bien correctement. C’est l’équivalent de sorted(l1 + l2 + l3), sauf que ça ne charge pas tout en mémoire:

>>> heapq.merge(l1, l2, l3)
<generator object merge at 0x0314F238>

Alors que sorted(), charge tout en mémoire:

>>> sorted(l1 + l2 + l3)
[52, 59, 60, 171, 174, 262, 336, 402, 435, 487, 557, 645, 899, 949, 996]

Bien entendu, ça marche avec des listes créées avec
heapq, ainsi:

>>> l1 = []

>>> for x in xrange(5): heappush(l1, random.randint(0, 1000))

>>> l2 = []

>>> for x in xrange(5): heappush(l2, random.randint(0, 1000))

>>> l3 = []

>>> for x in xrange(5): heappush(l3, random.randint(0, 1000))

>>> list(heapq.merge(l1, l2, l3))

[31, 40, 133, 360, 504, 508, 513, 679, 645, 792, 838, 413, 765, 886, 924]

(Grosse connasserie de ma part, faites comme si vous aviez rien vu.)

Quand on a de grosses quantités de données à trier, c’est très pratique, car l’effort de tri est répartie à chaque insertion, et à chaque itération pendant le parcours, pas concentré sur de gros appels de sorted().

On peut aussi récupérer des trucs du genre, les n plus petits / grands éléments sans tout coder à la main:

>>> l = [random.randint(0, 1000) for x in xrange(100)]
>>> heapq.nsmallest(4, l)
[0, 2, 4, 7]
>>> heapq.nlargest(3, l)
[999, 996, 983]

Et c’est beaucoup plus efficace que de le faire soi-même.

J’en profite pour rappeler au passage que tous les objets en Python sont ordonnables:

>>> (1, 2) > (2, 1)
False
>>> (1, 2) < (2, 1)
True
>>> "a" > "b"
False
>>> "a" < "b"
True

Et qu’en définissant les méthodes __eq__, __lt__, __gt__, etc., on peut donner un moyen de comparer n’importe quelle classe.

Bref, pour tous les besoins de classement, de priorisations, d’ordonnancement, de notion de plus petits, de plus grands, etc. qui concernent un gros jeu de données, heapq est le module qu’il vous faut.

Et là je percute que ça fait quelque temps déjà que je fais des articles élitistes pour des uses cases de 1% de la population. Donc les prochains tutos concerneront des trucs plus terre à terre. Parce que, je fais le malin là, mais je savais pas à quoi servait heapq il y a 3 semaines.

xoxo les filles