Travailler avec des listes triées en Python : la magie du module « bisect »

Travailler avec des listes triées peut parfois être un peu délicat. Vous devez conserver l'ordre de la liste après chaque insertion et rechercher efficacement les éléments qu'elle contient. La recherche binaire est un algorithme puissant pour rechercher dans une liste triée. Bien que sa mise en œuvre à partir de zéro ne soit pas trop difficile, cela peut prendre du temps. Heureusement, Python propose le module bisect, qui facilite grandement la gestion des listes triées.

Qu’est-ce que la recherche binaire ?

La recherche binaire est un algorithme qui trouve la position d'une valeur cible dans un tableau trié. Imaginez que vous recherchez un nom dans un annuaire téléphonique. Au lieu de commencer par la première page, vous commencerez probablement au milieu du livre et déciderez de poursuivre la recherche dans la première ou la seconde moitié, selon que le nom est alphabétiquement supérieur ou inférieur à celui du milieu. La recherche binaire fonctionne de manière similaire : elle commence par deux pointeurs, l'un au début et l'autre à la fin de la liste. L'élément du milieu est ensuite calculé et comparé à la cible.

Le module bisect : simplifier les opérations de liste triée

Bien que la recherche binaire soit efficace, écrire l'implémentation à chaque fois peut être fastidieux. Et si vous pouviez effectuer les mêmes opérations avec une seule ligne de code ? C'est là qu'intervient le module bisect de Python. Faisant partie de la bibliothèque standard de Python, bisect vous aide à maintenir une liste triée sans avoir besoin de la trier après chaque insertion. Il le fait en utilisant un simple algorithme de bissection.

Le module bisect fournit deux fonctions clés : bisect et insort. La fonction bisect trouve l'index où un élément doit être inséré pour garder la liste triée, tandis que insort insère l'élément dans la liste tout en conservant son ordre de tri.

Utilisation du module bisect : un exemple pratique

Commençons par importer le module :

import bisect

Exemple 1 : insertion d'un numéro dans une liste triée

Supposons que nous ayons une liste triée de nombres :

data = [1, 3, 5, 6, 8]

Pour insérer un nouveau numéro tout en gardant la liste triée, utilisez simplement :

bisect.insort(data, 7)

après avoir exécuté ce code, les données ressembleront à ceci :

[1, 3, 5, 6, 7, 8]

Exemple 2 : Trouver le point d'insertion

Et si vous souhaitez simplement savoir où un numéro serait inséré sans réellement l'insérer ? Vous pouvez utiliser les fonctions bisect_left ou bisect_right :

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

Cela nous indique que le chiffre 4 doit être inséré à l'index 2 pour garder la liste triée.

Exemple 3 : Maintenir l'ordre de tri dans une liste dynamique

Disons que vous gérez une liste à croissance dynamique et que vous devez insérer des éléments tout en vous assurant qu'elle reste triée :

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

Cela affichera la liste à chaque étape au fur et à mesure que les éléments sont insérés :

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

Exemple 4 : Utilisation de la bisecte avec des objets personnalisés

Supposons que vous ayez une liste d'objets personnalisés, tels que des tuples, et que vous souhaitiez les insérer en fonction d'un critère spécifique :

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

Ou vous souhaiterez peut-être insérer en fonction du deuxième élément de chaque tuple :

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

bisect en action : à la recherche de mots

Le module bisect ne se limite pas aux nombres ; cela peut également être utile pour rechercher dans des listes de chaînes, de tuples, de caractères, etc.
Par exemple, pour rechercher un mot dans une liste triée :

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

Ou pour trouver le premier mot d'un groupe de mots avec un préfixe spécifique :

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix + 'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

Cependant, gardez à l'esprit que bisect_left renvoie l'index où la cible doit être insérée, et non si la cible existe dans la liste.

Variantes de bissect et insort

Le module comprend également des variantes du côté droit : bisect_right et insort_right. Ces fonctions renvoient l'index le plus à droite auquel insérer un élément s'il est déjà dans la liste. Par exemple, bisect_right renverra l'index du premier élément supérieur à la cible si la cible est dans la liste, tandis que insort_right insère l'élément à cette position.

diviser sous le capot

La puissance du module bisect réside dans sa mise en œuvre efficace de l'algorithme de recherche binaire. Lorsque vous appelez bisect.bisect_left, par exemple, la fonction effectue essentiellement une recherche binaire sur la liste pour déterminer le point d'insertion correct pour le nouvel élément.

Voici comment cela fonctionne sous le capot :

1. Initialisation : la fonction commence par deux pointeurs, lo et hi, qui représentent les limites inférieure et supérieure de la plage de recherche dans la liste. Initialement, lo est défini au début de la liste (index 0) et hi est défini à la fin de la liste (index égal à la longueur de la liste). Mais vous pouvez également spécifier des valeurs lo et hi personnalisées pour effectuer une recherche dans une plage spécifique de la liste.

2. Bisection: Within a loop, the function calculates the midpoint (mid) between lo and hi. It then compares the value at mid with the target value you’re looking to insert.

3. Comparison:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid + 1`.

1. Termination: This process continues, halving the search range each time, until lo equals hi. At this point, lo (or hi) represents the correct index where the target should be inserted to maintain the list's sorted order.

2. Insertion: For the insort function, once the correct index is found using bisect_left, the target is inserted into the list at that position.

This approach ensures that the insertion process is efficient, with a time complexity of O(log n) for the search and O(n) for the insertion due to the list shifting operation. This is significantly more efficient than sorting the list after each insertion, especially for large datasets.

bisect_left code example:

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

insort_left code example:

def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

Conclusion

The bisect module makes working with sorted lists straightforward and efficient. The next time you need to perform binary search or insert elements into a sorted list, remember the bisect module and save yourself time and effort.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!