Quand j’entends deque, je pense plus à un deck de Magic de Gathering qu’à un module Python, mais aujourd’hui j’utilise beaucoup plus le dernier que le précédent.

On a déjà vu comment implémenter l’itération par morceaux sur un itérable de n’importe quelle taille. Grâce au deque, on peut aussi facilement créer une fenêtre glissante.

Qu’est-ce qu’une fenêtre glissante ?

Il s’agit de parcourir un itérable par tranches de “n” élements, en faisant en sorte que l’insertion d’un nouvel élément dans la tranche implique la supression du premier entré. Mouai, dit comme ça c’est pas clair. Un p’tit exemple ?

Fenêtre glissante de 3 éléments sur une liste de 10 éléments, à la mano:

>>> l = range(10)
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l[:3]
[0, 1, 2]
>>> l[1:4]
[1, 2, 3]
>>> l[2:5]
[2, 3, 4]
>>> l[3:6]
[3, 4, 5]
...

A ne pas confondre avec le parcours par morceaux, qu’on déjà traité, et qui donne ça:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l[0:3]
[0, 1, 2]
>>> l[3:6]
[3, 4, 5]
>>> l[6:9]
[6, 7, 8]
...

Et bien sûr, comme d’hab, vous allez dire “Cher Sam, malgré ton génie qui n’a d’égal que ta beauté et l’incohérence de cette remarque, je ne vois pas vraiment à quoi ça sert.”

Et bien essentiellement dans les situations où un élément est dépendant des précédents, par exemple pour répondre à des questions existentielles comme “quel est le premier élément qui est la somme des 5 le précédant dans cette liste ?”. Ça n’arrive certes pas tous les jours, mais fuck, j’avais pas de meilleur exemple en tête, là, tout de suite.

Qu’est-ce qu’un deque ?

Un deque est une structure de données qui permet d’implémenter des comportements de types piles, files, FIFO, LIFO, et autres pipos avec efficacité. Traduit en langage de tous les jours, c’est comme une liste, mais:

• ajouter un élément à la fin ou au début est une opération super rapide;
• les retirer aussi;
• on peut itérer dessus à la même vitesse que la liste;
• mais accéder à un élement qui n’est pas au début ou à la fin juste par son index est très lent;
• on peut limiter le nombre d’éléments que ça contient automatiquement.

On va donc l’utiliser comme acumulateur ou pour faire des files d’attentes.

Démonstration:

>>> from collections import deque
>>> ze_deck = deque(maxlen=3) # on limite le deque à 3 éléments
>>> ze_deck.append(1)
>>> ze_deck
deque([1], maxlen=3)
>>> ze_deck.append(2)
>>> ze_deck
deque([1, 2], maxlen=3)
>>> ze_deck.append(3)
>>> ze_deck
deque([1, 2, 3], maxlen=3)
>>> ze_deck.append(4) # ... et MAGIQUEMENT !
>>> ze_deck
deque([2, 3, 4], maxlen=3)
>>> for x in ze_deck:
...     print x
...     
2
3
4

Bam le dernier élément est squizzé, et tout ça rapidement et efficacement. Vous voyez où je veux subtilement en venir ?

Et finalement: comment on utilise l’un pour faire l’autre ?

>>> from collections import deque
>>> from itertools import islice
>>> 
>>> def window(iterable, size=2):
...         iterable = iter(iterable)
...         d = deque(islice(iterable, size), size)
...         yield d
...         for x in iterable:
...                 d.append(x)
...                 yield d
...         
>>> for x in window('azertyuiop'):
...         print x
...     
deque(['a', 'z'], maxlen=2)
deque(['z', 'e'], maxlen=2)
deque(['e', 'r'], maxlen=2)
deque(['r', 't'], maxlen=2)
deque(['t', 'y'], maxlen=2)
deque(['y', 'u'], maxlen=2)
deque(['u', 'i'], maxlen=2)
deque(['i', 'o'], maxlen=2)
deque(['o', 'p'], maxlen=2)

Vous noterez au passage que nous faisons ici un usage malin des générateurs, ce qui nous permet de retourner un itérable sans tout charger en mémoire et de slider sur notre window avec classe.

Ainsi on peut se la peter en faisant des trucs compliqués en une ligne comme:

>>> {tuple(d): i for i, d in enumerate(window(xrange(10), 3))}
{(5, 6, 7): 5, (0, 1, 2): 0, (7, 8, 9): 7, (6, 7, 8): 6, (1, 2, 3): 1, (3, 4, 5): 3, (2, 3, 4): 2, (4, 5, 6): 4}

Ce qui n’a absolument aucun intérêt, mais si vous comprenez ce que ça fait, alors vous avec bien masterisé Python.