8.5. bisect — Algorithme de bissection de listes

Nouveau dans la version 2.1.

Code source : Lib/bisect.py

Ce module fournit des outils pour maintenir une liste triée sans avoir à la trier à chaque insertion. Il pourrait être plus rapide que l’approche classique pour de longues listes d’éléments dont les opérations de comparaison sont lourdes. Le module se nomme bisect car il utilise une approche simple par bissection. Si vous voulez un exemple de cet algorithme, le mieux est d’aller lire le code source de ce module (les conditions sur les limites y étant justes !).

Les fonctions suivantes sont fournies :

bisect.bisect_left(a, x, lo=0, hi=len(a))

Trouve le point d’insertion de x dans a permettant de conserver l’ordre. Les paramètres lo et hi permettent de limiter les emplacements à vérifier dans la liste, par défaut toute la liste est utilisée. Si x est déjà présent dans a, le point d’insertion proposé sera avant (à gauche) de l’entrée existante. Si a est déjà triée, la valeur renvoyée peut directement être utilisée comme premier paramètre de list.insert().

Le point d’insertion renvoyé, i, coupe la liste a en deux moitiés telles que, pour la moitié de gauche : all(val < x for val in a[lo:i]), et pour la partie de droite : all(val >= x for val in a[i:hi]).

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))

Semblable à bisect_left(), mais renvoie un point d’insertion après (à droite) d’une potentielle entrée existante valant x dans a.

Le point d’insertion renvoyé, i, coupe la liste a en deux moitiés telles que, pour la moitié de gauche : all(val <= x for val in a[lo:i]) et pour la moitié de droite : all(val > x for val in a[i:hi]).

bisect.insort_left(a, x, lo=0, hi=len(a))

Insère x dans a en conservant le tri. C’est l’équivalent de a.insert(bisect.bisect_left(a, x, lo, hi), x), tant que a est déjà triée. Gardez en tête que bien que la recherche ne coûte que O(log n), l’insertion coûte O(n).

bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))

Similaire à insort_left(), mais en insérant x dans a après une potentielle entrée existante égale à x.

Voir aussi

SortedCollection recipe utilise le module bisect pour construire une classe collection exposant des méthodes de recherches naturelles et gérant une fonction clef. Les clefs sont pré-calculées pour économiser des appels inutiles à la fonction clef durant les recherches.

8.5.1. Chercher dans des listes triées

Les fonctions bisect() ci-dessus sont utiles pour insérer des éléments, mais peuvent être étranges et peu naturelles à utiliser pour rechercher des éléments. Les cinq fonctions suivantes montrent comment les transformer en recherche plus classique pour les listes triées :

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

8.5.2. Autres Exemples

La fonction bisect() peut être utile pour des recherches dans des tableaux de nombres. Cet exemple utilise bisect() pour rechercher la note (sous forme de lettre) correspondant à un note sous forme de points, en se basant sur une échelle prédéfinie : plus de 90 vaut “A”, de 80 à 89 vaut “B”, etc… :

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
        i = bisect(breakpoints, score)
        return grades[i]

>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

Contrairement à la fonction sorted(), ça n’aurait pas de sens pour la fonction bisect() d’avoir un paramètre key ou reversed, qui conduiraient à une utilisation inefficace (des appels successifs à la fonction bisect n’auraient aucun moyen de se « souvenir » des recherches de clef précédentes).

Il est préférable d’utiliser une liste de clefs pré-calculée pour chercher l’index de l’enregistrement en question :

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)