bisect¶
Par Yoan Blanc 1
bisect est un tout petit module permettant de travailler avec des listes triées. Son nom provient de l’algorithme utilisé nommé recherche dichotomique (Wikipedia) ou parfois bissection (en anglais notamment).
Introduction¶
Comme le cite l’article de _pymotw sur le suject, bisect est un petite module avec deux fonctionnalités simples.
Trouver la position pour insérer un élément dans une liste triée :
bisect()Insérer un élément dans la liste triée :
insort()
Par défaut, ces deux opérations travaillent à droite. C’est-à-dire que la recherche fournit le dernier élément trouvé en cas de doublons, et que l’ajout se fait à la suite de la liste.
>>> from bisect import bisect, insort
>>> xs = []
>>> insort(xs, 2)
>>> insort(xs, 1)
>>> insort(xs, 2)
>>> xs
[1, 2, 2]
>>> bisect(xs, 1)
1
>>> bisect(xs, 2)
3
>>> xs
[1, 2, 2]
Afin de travailler à gauche, et insérer au début d’une série, il faut travailler avec les alternatives bisect_left() et insort_left().
>>> from bisect import bisect_left
>>> xs = [1, 2, 2]
>>> bisect_left(xs, 1)
0
>>> bisect_left(xs, 2)
1
Note
bisect_right() est un alias pour bisect(), tout comme insort_right() et insort().
Exemple¶
L’exemple ci-dessous utilise le module collections.abc (voir Abstract Base Class (abc), et unittest / doctest) pour composer une collection restant triée en toute circonstance. Comme expliqué précédemment, l’intérêt par rapport à effectuer des tris à intervalle régulier est la complexité qui reste base.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | from bisect import bisect_left, insort
from collections.abc import MutableSequence
class SortedCollection(MutableSequence):
"""Collection triée.
>>> sc = SortedCollection()
>>> sc.append(2)
>>> sc.append(1)
>>> sc
[1, 2]
>>> 2 in sc
True
>>> 3 in sc
False
>>> tuple(sc)
(1, 2)
>>> sc.reverse() # reverse does nothing.
>>> sc
[1, 2]
>>> del sc[1]
>>> sc[0] = 3
>>> sc
[3]
"""
def __init__(self):
"""Initialise la collection triée."""
self._col = []
def __repr__(self):
"""S'affiche comme une list."""
return repr(self._col)
def __contains__(self, value):
"""Contient la valeur cherchée."""
try:
self.index(value)
except ValueError:
return False
return True
def __iter__(self):
"""Retourne un itérateur sur la liste."""
return iter(self._col)
def __len__(self):
"""Retourne la taille de la collection."""
return len(self._col)
def __getitem__(self, index):
"""Obtient un élément selon sa position."""
return self._col[index]
def __setitem__(self, index, value):
"""Modifie l'élément à l'index donnée.
Équivalent à supprimer un élément et en ajouter un (ailleurs).
"""
del self[index]
self.insert(index, value)
def __delitem__(self, index):
"""Supprime l'élément à l'indice donné."""
del self._col[index]
def insert(self, index, value):
"""Ajoute la valeur à sa place.
Indépendamment de la position donnée dans ``index``.
"""
insort(self._col, value)
def index(self, value):
"""Retourne la position dans la liste."""
i = bisect_left(self._col, value)
if i < len(self) and self[i] == value:
return i
raise ValueError
def reverse(self):
"""Inverse ne fait rien."""
|
Ce module est inspiré d’un article sur ActiveState (datant de 2010) adapté pour Python 3.
Alternatives¶
heapq est un module implémantant une liste de priorité, nommé tas ou heap en anglais permettant de, à moindre coût, obtenir la valeur la plus petite (par défaut), d’une liste de valeur.