Néanmoins, il n’y a pas dans l’API de moyen de récupérer le premier ou le dernier élément inséré dans dico. Il y a bien popitem(), mais ça retire l’élément du dictionnaire, et c’est pas forcément ce qu’on veut.

Heureusement OrderedDict est un itérable, et implémente __reversed__, et on peut donc utiliser les outils suivant our récupérer les extrémités avec une perf 0(1):

>>> from collections import OrderedDict
>>> d = OrderedDict.fromkeys('azerty')
>>> next(iter(d.items())) # premier élément
'a'
>>> next(reversed(d.items())) # dernier élément
'y'

Après l’implémentation de OrderedDict reste une liste doublement chainée, et on ne peut donc pas récupérer un élément à un index arbitraire sans le parcourir à la main…

Le parcours est à peu près toujours le même quand on veut grouper ou compter des valeurs en Python.

Malgré cela, je vois encore des gens qui sous utilisent ces collections. Par exemple, Counter peut compter automatiquement :

>>> from collections import Counter
>>> Counter('jfsqmfjdklmqfjsdqklmfjdsqhfdqsjkhfdshjkl')
    Counter({'j': 6, 'f': 6, 'q': 5, 's': 5, 'd': 5, 'k': 4, 'l': 3, 'm': 3, 'h': 3})

Mais ce que ne réalisent pas beaucoup de développeurs, c’est que cet objet accepte n’importe quel itérable en paramètre. Nous sommes en Python, et rededjiou, je me tue à répéter que l’itération est la philosophie centrale du langage.

Donc le compteur peut prendre une expression génératrice en paramètre.

Par exemple, si vous voulez compter un truc un peu plus complexe que des éléments, comme mettons, le ratio de lignes commentées dans un fichier, vous n’avez pas besoin de faire ça :

count = Counter()
for line in open('/etc/fstab', encoding='ascii'):
        count[line.startswith('#')] += 1
 # out : Counter({True: 10, False: 3})

Ceci marchera parfaitement :

count = Counter(line.startswith('#') for line in open('/etc/fstab', encoding='ascii'))
# out : Counter({True: 10, False: 3})

Vous pouvez également utiliser des générateurs plus complexes. Combien de fichiers par types d’extensions ?

import os
import pathlib

def get_extensions(path):
    for dirpath, dirnames, files in os.walk(path):
        for name in files:
            ext = pathlib.Path(name).suffix
            if ext: # on ignore les fichiers sans extension
                yield ext
            

Counter(get_extensions('/etc')).most_common(9)
 # Out : 
 # ('.conf', 632),
 # ('.0', 348),
 # ('.gz', 323),
 # ('.jhansonxi', 207),
 # ('.pem', 177),
 # ('.load', 127),
 # ('.ttb', 86),
 # ('.ktb', 80),
 # ('.kti', 55)]

Notez que le Counter peut faire plus que compter. Ici il nous donne les 9 plus grandes valeurs du classement, mais en prime, il peut aussi nous faire des opérations ensemblistes :

>>> c = Counter("aabbbbbbbbbbbbcccc")
>>> c & Counter('aaaaaaaaaaaaaaabbcddddddd') # valeurs min
    Counter({'b': 2, 'a': 2, 'c': 1})
>>> c | Counter('aaaaaaaaaaaaaaabbcddddddd') # valeurs max
    Counter({'a': 15, 'b': 12, 'd': 7, 'c': 4})

Le compteur fournit par Python est donc naturellement très, très puissant.

Une autre chose qui est rarement faite : sous-classer ces types.

Par exemple, si vous avez souvent des opérations où il faut grouper des valeurs :

from collections import defaultdict

class Grouper(defaultdict):
 
    def __init__(self, iterable):
        super(Grouper, self).__init__(list)
        self.update(iterable)
 
    def update(self, iterable):
        try:
            iterable = iterable.items()
        except AttributeError:
            iterable = iterable
        for k, v in iterable:
            self[k].append(v)

On prend un default dict, on lui dit qu’un update ajoute les éléments à la liste en valeur plutôt que de la remplacer, et zou, vous avez un dictionnaire qui va grouper toutes les valeurs automatiquement.

Liste des fichiers par extensions ? Fastoche !

def get_extensions(path):
    for dirpath, dirnames, files in os.walk(path):
        for name in files:
            ext = pathlib.Path(name).suffix
            if ext: 
                yield ext, name # on rajoute le name ici

>>>files = Grouper(get_extensions('/etc'))
>>> files['.tti']
['en-na-ascii.tti',
 'numbers-french.tti',
 'devanagari.tti',
 'letters-cyrillic.tti',
 'punctuation-basic.tti',
 'malayalam.tti',
 'ascii-basic.tti',
 'spaces.tti',
 'letters-latin.tti',
 'letters-latin-dot8.tti',
 'en-chess.tti',
 'numbers-dot8.tti',
 'punctuation-tibetan.tti',
 'boxes.tti',
 'gujarati.tti',
 'numbers-nemeth.tti',
 'punctuation-alternate.tti',
 'common.tti',
 'blocks.tti',
 'gurmukhi.tti',
 'kannada.tti',
 'telugu.tti',
 'tamil.tti',
 'numbers-dot6.tti',
 'de-chess.tti',
 'control-latin.tti',
 'letters-tibetan.tti',
 'oriya.tti',
 'bengali.tti']

Bref, compter et grouper sont des opérations si communes : ne vous faites par chier à refaire tout ça à la main.

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)

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

Les dictionnaires

Valeur par défaut

Une fois à l’aise en Python, on utilise souvent les dictionnaires. Et on fait souvent ça:

>>> def get(d, key, default):
...     try:
...         return d[key]
...     except KeyError:
...         return default
... 
>>> d = {'a':1}
>>> get(d, 'foo', 'bar')
'bar'
>>> get(d, 'a', 'bar')
1

C’est parfaitement superflux, puisque Python le propose en standard:

>>> d.get("foo", 'bar')
'bar'
>>> d.get("a", 'bar')
1

Plus tordu encore:

>>> def get_and_set_if_not_exist(d, key, default):
...     try:
...         return d[key]
...     except KeyError:
...         d[key] = default
...         return default
... 
>>> d = {'a':1}
>>> get_and_set_if_not_exist(d, 'foo', []).append('wololo')
>>> d
{'a': 1, 'foo': ['wololo']}
>>> get_and_set_if_not_exist(d, 'foo', []).append('oyo oyo')
>>> d
{'a': 1, 'foo': ['wololo', 'oyo oyo']}

Python le propose aussi en standard:

>>> d = {'a':1}
>>> d.setdefault('foo', []).append('wololo')
>>> d.setdefault('foo', []).append('oyo oyo')
>>> d
{'a': 1, 'foo': ['wololo', 'oyo oyo']}

Clés des dictionnaires

Les clés des dictionnaires n’ont pas à être des strings. N’importe quel objet hashable fait l’affaire, par exemple, des tuples:

>>> positions = {}
>>> positions[(48.856614, 48.856614)] = "Paris"
>>> positions[(40.7143528, -74.0059731)] = "New York"
>>> positions
{(48.856614, 48.856614): 'Paris', (40.7143528, -74.0059731): 'New York'}
>>> positions[(48.856614, 48.856614)]
'Paris'

Les sets

Les sets sont un type de structure peu connu: ils représentent un ensemble non ordonné d’objets uniques. Il n’y a donc pas d’ordre évident dans un set, et le résultat est garanti sans doublon:

>>> e = set((3, 2, 1, 1, 1, 1, 1))
>>> e
set([1, 2, 3])
>>> e.add(1)
>>> e.add(1)
>>> e.add(14)
>>> e
set([1, 2, 3, 14])

Les opérations du set acceptent n’importe quel itérable. Y compris les opérations ensemblistes:

>>> e.update('abcdef')
>>> e
set(['a', 1, 2, 3, 'e', 'd', 'f', 'c', 14, 'b'])
>>> e = set('abc')
>>> e.union("cde")
set(['a', 'c', 'b', 'e', 'd'])
>>> e.difference("cde")
set(['a', 'b'])
>>> e.intersection("cde")
set(['c'])

Vérifier la présence l’un élément dans un set (avec l’opérateur in) est une opération extrêment rapide (compléxité O(1)), beaucoup plus que dans une liste ou un tuple. Le set reste pourtant itérable (mais on ne peut pas compter sur l’ordre).

Les opérateurs binaires sont overridés pour les opérations entre sets. De plus on peut utiliser une notation littérale pour décrire un set à partir de Python 2.7:

>>> {'a', 'b', 'c'} | {'c', 'd'} # union
set(['a', 'c', 'b', 'd'])
>>> {'a', 'b', 'c'} & {'c', 'd'} # intersection
set(['c'])
>>> {'a', 'b', 'c'} - {'c', 'd'} # difference
set(['a', 'b'])

Les listes

Pop() prend un argument

La raison pour laquelle il n’y a pas de unshift sur les listes en Python, c’est que l’on en a pas besoin:

>>
>>> l = [1, 2, 3, 4, 5]
>>> l.pop()
5
>>> l
[1, 2, 3, 4]
>>> l.pop(0)
1
>>> l
[2, 3, 4]
>>> l.pop(-2)
3
>>> l
[2, 4]

Le slicing accepte un 3eme argument

Le slicing, que l’on peut appliquer à tous les indexables (listes, tuples, strings, etc), est la fonctionalité bien pratique qui permet de récupérer une sous partie de la structure de données:

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

Ca vous connaissiez sûrement. Mais cette syntaxe accepte un 3eme nombre: le pas.

Le premier nombre dit d’où l’on part. Le second où l’on s’arrête. Le dernier dit de combien on avance (par défaut de 1).

>>> l[2:8:2]
[2, 4, 6]
>>> l[2::2] # chaque paramètre est optionel
[2, 4, 6, 8]

Et le pas peut être négatif, ce qui est plutôt sympas si vous voulez parcourir une liste ou une string à reculon.

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

extend() accepte n’importe quel itérable

extend() permet de mettre à jour une liste. On l’utilise souvent en lui passant une autre liste:

>>> l = [1, 2, 3]
>>> l.extend([4, 5, 6])
>>> l
[1, 2, 3, 4, 5, 6]

Mais comme la plupart du code la bibliothèque standard, extend() accepte n’importe quel itérable.

>>> t = (42, 666, 1024) # un tuple
>>> s = '456' # une string
>>> d = {'3.14': 'pi'} # un dico
>>> l = [1, 2, 3]
>>> l.extend(s)
>>> l
[1, 2, 3, '4', '5', '6']
>>> l.extend(d) #
>>> l
[1, 2, 3, '4', '5', '6', '3.14']
>>> l.extend(t)
>>> l
[1, 2, 3, '4', '5', '6', '3.14', 42, 666, 1024]

Ca marche aussi avec les set, les fichiers, les expressions génératrices. Attention cependant, sachez que l’itération retourne: par exemple itérer sur un dico retourne ses clés, pas ses valeurs (car on peut récupérer l’un avec l’autre, mais pas l’inverse).

Les tuples

Ce qui permet de créer un tuple ne sont pas les parenthèses, mais la virgule:

>>> 1,2,3 # ceci EST un tuple
(1, 2, 3)
>>> 1, # tuple
(1,)
>>> 1 # int
1

La raison pour laquelle il est recommandé d’utiliser presque TOUJOURS les parenthèses, c’est qu’elles permettent d’éviter les ambiguïtés, et qu’elles autorisent la définition sur plusieurs lignes:

>>> type(1,2,3) # tuple ou paramètres ?
Traceback (most recent call last):
  File "", line 1, in 
    type(1,2,3)
TypeError: type() argument 1 must be string, not int
>>> type((1,2,3))

>>> (1, # un gros tuple s'écrit sur plusieurs lignes
... 2,
... 3)
(1, 2, 3)

Mais il existe des rares cas où il est acceptable de ne pas mettre de parenthèses:

>>> def debut_et_fin(lst):
...     """
...         Retourne le début et la fin d'une liste
...     """
...     debut = lst[0]
...     fin = lst[-1]
...     # donner l'illusion de retourner plusieurs valeurs
...     # alors qu'on retourne en fait un tuple
...     return debut, fin # 
... 
>>> debut, fin = debut_et_fin([1,2,3,4]) # unpacking
>>> debut
1
>>> fin
4
>>> debut, fin = fin, debut # variable swap
>>> debut
4
>>> fin
1

Le module collections

En plus des collections built-in, la bibliothèque standard de Python propose un module collections avec plein d’outils en bonus.

Des dictionnaires qui conservent l’ordre d’insertion (comme les Arrays en PHP):

>>> from collections import OrderedDict
>>> d = {} # l'ordre d'un dico n'est pas garanti
>>> d['c'] = 1
>>> d['b'] = 2
>>> d['a'] = 3
>>> d.keys()
['a', 'c', 'b']
>>> d = OrderedDict()
>>> d['c'] = 1
>>> d['b'] = 2
>>> d['a'] = 3
>>> d.keys()
['c', 'b', 'a']

Un compteur qui a une interface similaire à un dictionnaire spécialisé.

>>> from collections import Counter
>>> score = Counter()
>>> score['bob']
0
>>> score['robert'] += 1
>>> score['robert']
1
>>> score['robert'] += 1
>>> score['robert']
2

Comme vous pouvez le voir il gère les valeurs par defaut, mais en prime il compte le contenu de n’importe quel itérable:

>>> Counter([1, 1, 1, 1, 1, 1, 2, 3, 3])
Counter({1: 6, 3: 2, 2: 1})
>>> Counter('Une petite puce pique plus')
Counter({'e': 5, ' ': 4, 'p': 4, 'u': 3, 'i': 2, 't': 2, 'c': 1, 'l': 1, 'n': 1, 'q': 1, 's': 1, 'U': 1})

Des tuples qui ressemblent à des structs en C, mais itérables:

>>> from collections import namedtuple
>>> Fiche = namedtuple("Fiche", "force charisme intelligence")
>>> f = Fiche(force=18, charisme=17, intelligence=3)
>>> f
Fiche(force=18, charisme=17, intelligence=3)
>>> for x in f:
...     print x
...
18
17
3
>>> f.force
18

Des dicos dont la valeur par défaut est le résultat de l’appel d’une fonction:

>>> from collections import defaultdict
>>> import datetime
>>> d = defaultdict(datetime.datetime.now)
>>> d["jour"]
datetime.datetime(2012, 7, 10, 17, 34, 7, 265222)
>>> d["jour"] # la valeur est settée
datetime.datetime(2012, 7, 10, 17, 34, 7, 265222)
>>> d["raison"] = "test"
>>> d.items()
[("jour", datetime.datetime(2012, 7, 10, 17, 34, 7, 265222)), ("raison", 'test')]