Implémenter une fenêtre glissante en Python avec un deque


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.

8 thoughts on “Implémenter une fenêtre glissante en Python avec un deque

  • anucunnilinguiste

    Les fenêtres glissantes, c’est exactement ce que j’utilise pour dessiner mes courbes en temps réel avec matplotlib et Qt à partir d’informations récupérées sur psutil. J’ai besoin de tracer 600 valeurs en permanence, du coup j’utilise les piles…

  • anucunnilinguiste

    Moi j’aime l’article car je visualise directement une application concrète, je fonctionnais à la bourrin (je teste la taille de la pile)…Avec les collections, c’est plus propre. Merci.

  • François

    Pour l’exemple, il y a une semaine j’ai implémenté à la rache une petite fonction qui détecte le premier max d’une liste. L’idée était d’introduire une fenêtre glissante de taille 2n+1 et de dire qu’on a trouvé quand le max se trouve au milieu de la fenêtre. Plutôt que de faire des vues à tour de boucle, le deque aurait été plus approprié et est amha un cas parlant.

    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.

    Sans dec’

    OK —->[]

  • Sebastien

    Pourquoi faire compliqué ?


    a=range(10)
    d=deque(a[:3], 3)
    for i in a[3:]:
    print d
    d.append(i)

  • Sam Post author

    La solution de l’article n’est pas équivalente. C’est une solution générique qui est importable, réutilisable, et qui marche sur n’importe quel itérable, y compris un itérable de taille infini ou un iterable qui n’es pas sliceable.

  • scaringella

    ALORS LA! MERCI!
    J’apprend encore des trucs en python ….
    Bookmarker.
    MAN YOUR NOT SO FAR FROM GOD!

  • cendrieR

    Encore un truc que je ne pense pas avoir à utiliser avant longtemps, mais dont le principe est bien sympa.

  • Alex

    En fait les fenêtres glissantes c’est carrément la base du traitement de signal. Par exemple pour enlever le bruit. Exemple: tu mesures au LIDAR le profil de hauteur d’une coline. Tu t’en fout des arbustes et autres merveilles de la nature qui te pourrisent le profil de la coline sur ton joli plot, donc hop! fenêtre glissante où tu moyenne à chaque itération.

    Conclusion: THANKS BRO! C’est de la balle ce deck ;)

Comments are closed.

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.