Adresse : http://docs.python.org/3.3/library/bisect.html
Le module bisect permet de rechercher des positions d’insertion (et d’insérer de nouvelles valeurs) dans une liste triée.
Les positions d’insertion peuvent être calculées soit “par la gauche”, soit (par défaut) “par la droite” (c’est important si on veut insérer des valeurs qui figurent déjà dans la liste).
|
1 2 3 4 5 6 7 8 9 10 |
>>> from bisect import * # importe la totalité du module bisect (noms courts) >>> tab = list(range(0,100,10)); tab # une liste triée dans l'ordre croissant >>> bisect_left(tab,25) # la valeur 25 viendrait s'insérer en position 3 3 >>> bisect_left(tab,60) # 60 s'insèrerait à gauche en position 7 7 >>> bisect(tab,60) # 60 s'insèrerait à droite en position 8 8 >>> insort(tab,28); tab # on insère 28 dans la liste [0, 10, 20, 28, 30, 40, 50, 60, 70, 80, 90] |
On peut également effectuer des insertions (ou chercher des positions) en spécifiant un intervalle de positions (mais attention, l’insertion effective risque alors de briser la nature globalement triée de la liste).
|
1 2 3 4 5 6 7 8 9 10 11 12 |
>>> tab # rappelons le contenu de la liste tab [0, 10, 20, 28, 30, 40, 50, 60, 70, 80, 90] >>> bisect(tab,75) # 75 devrait normalement s'insérer en position 9 9 >>> bisect(tab,75,lo=2,hi=5) # mais si on impose [2,5], il viendrait en position 5 5 >>> insort(tab,75,hi=7); tab # on décide d'insérer 75 en position maximum 7 [0, 10, 20, 28, 30, 40, 50, 75, 60, 70, 80, 90] >>> insort(tab,15,lo=6); tab # on décide d'insérer 15 en position minimum 6 [0, 10, 20, 28, 30, 40, 15, 50, 75, 60, 70, 80, 90] >>> insort(tab,5,lo=3,hi=7); tab # insère 5 en imposant l'intervalle de positions [3,7] [0, 10, 20, 5, 28, 30, 40, 15, 50, 75, 60, 70, 80, 90] |
La documentation Python contient un certain nombre d’exemples montrant comment “humaniser” un peu les fonctions précédentes, notamment dans les recherches d’occurrences dans une liste triée.
On trouvera ces fonctions ici : http://docs.python.org/3.3/library/bisect.html#searching-sorted-lists
Voici un exemple d’utilisation du module bisect (créer une liste triée par insertions successives d’entiers aléatoires) :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
>>> from bisect import * # importe le package bisect (noms courts) >>> from random import * # importe le package random (noms courts) >>> seed(4); tab = [] # initialise graîne aléatoire, tableau vide >>> for k in range(1,15): # à quatorze reprises insort(tab,randint(10,100)) # on insère un entier aléatoire à deux chiffres print(tab) # on affiche le tableau après cette insertion [40] [40, 48] [23, 40, 48] [23, 40, 48, 60] [23, 40, 48, 60, 71] [23, 29, 40, 48, 60, 71] [21, 23, 29, 40, 48, 60, 71] [18, 21, 23, 29, 40, 48, 60, 71] [12, 18, 21, 23, 29, 40, 48, 60, 71] [12, 18, 21, 23, 29, 40, 48, 60, 61, 71] [12, 18, 21, 23, 29, 40, 48, 60, 61, 71, 80] [12, 18, 21, 23, 29, 40, 47, 48, 60, 61, 71, 80] [12, 17, 18, 21, 23, 29, 40, 47, 48, 60, 61, 71, 80] [12, 17, 18, 21, 23, 29, 38, 40, 47, 48, 60, 61, 71, 80] |
Retour à l’accueil du cours Python/Numpy
Sommaire du chapitre 7
- Le module random
- Le module decimal
- Le module fractions
- Le module string
- Le module itertools
- Les modules operator et functools
- Le module time
- La classe Counter du module collections
- La classe deque du module collections
- Le module heapq
- Le module bisect
- Le module copy
- Autres modules et adresses utiles