Explication détaillée du module de recherche binaire et de bisecte implémenté en Python

Avant-propos

En fait, l'implémentation interne de la liste (list) de Python est un tableau, qui est une liste linéaire. Pour rechercher des éléments dans une liste, vous pouvez utiliser la méthode list.index(), dont la complexité temporelle est O(n). Pour de grandes quantités de données, la recherche binaire peut être utilisée à des fins d'optimisation.

La recherche binaire nécessite que les objets soient ordonnés. Le principe de base est le suivant :

1. En partant de l'élément du milieu du tableau, si l'élément du milieu se trouve être l'élément à être. recherché, le processus de recherche se termine ;

2. Si un élément spécifique est supérieur ou inférieur à l'élément du milieu, recherchez dans la moitié du tableau qui est supérieure ou inférieure à l'élément du milieu, et démarrez la comparaison à partir de l’élément du milieu comme auparavant.

3. Si le tableau est vide à une certaine étape, cela signifie qu'il est introuvable.

La recherche binaire devient également une recherche binaire. Chaque comparaison de l'algorithme réduit la plage de recherche de moitié et sa complexité temporelle est O(logn).

Nous utilisons respectivement la récursivité et les boucles pour implémenter la recherche binaire :

def binary_search_recursion(lst, value, low, high):
 if high < low:
 return None
 mid = (low + high) / 2
 if lst[mid] > value:
 return binary_search_recursion(lst, value, low, mid-1)
 elif lst[mid] < value:
 return binary_search_recursion(lst, value, mid+1, high)
 else:
 return mid
 
def binary_search_loop(lst,value):
 low, high = 0, len(lst)-1
 while low <= high:
 mid = (low + high) / 2
 if lst[mid] < value:
 low = mid + 1
 elif lst[mid] > value:
 high = mid - 1
 else:
 return mid
 return None

Ensuite, nous effectuons un test de performances sur ces deux implémentations :

if __name__ == "__main__":
 import random
 lst = [random.randint(0, 10000) for _ in xrange(100000)]
 lst.sort()
 
 def test_recursion():
 binary_search_recursion(lst, 999, 0, len(lst)-1)
 
 def test_loop():
 binary_search_loop(lst, 999)
 
 import timeit
 t1 = timeit.Timer("test_recursion()", setup="from __main__ import test_recursion")
 t2 = timeit.Timer("test_loop()", setup="from __main__ import test_loop")
 
 print "Recursion:", t1.timeit()
 print "Loop:", t2.timeit()

Les résultats d'exécution sont les suivants :

Recursion: 3.12596702576
Loop: 2.08254289627

On voit que la méthode de boucle est plus efficace que la récursivité.

module bisect

Python a un module bisect pour gérer les listes ordonnées. Le module bisect implémente un algorithme pour insérer des éléments dans une liste ordonnée. Dans certains cas, cela est plus efficace que de trier la liste à plusieurs reprises ou de construire une grande liste puis de la trier. Bisect signifie bissection. La méthode bissection est utilisée ici pour trier. Elle insérera un élément à la position appropriée d'une liste ordonnée, ce qui élimine le besoin d'appeler sort à chaque fois pour maintenir la liste ordonnée.

Ce qui suit est un exemple d'utilisation simple :

import bisect
import random
 
random.seed(1)
 
print'New Pos Contents'
print'--- --- --------'
 
l = []
for i in range(1, 15):
 r = random.randint(1, 100)
 position = bisect.bisect(l, r)
 bisect.insort(l, r)
 print'%3d %3d' % (r, position), l

Résultat de sortie :

New Pos Contents
--- --- --------
 14 0 [14]
 85 1 [14, 85]
 77 1 [14, 77, 85]
 26 1 [14, 26, 77, 85]
 50 2 [14, 26, 50, 77, 85]
 45 2 [14, 26, 45, 50, 77, 85]
 66 4 [14, 26, 45, 50, 66, 77, 85]
 79 6 [14, 26, 45, 50, 66, 77, 79, 85]
 10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 44 4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
 77 9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1 0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

Le module Bisect fournit Les fonctions sont :

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

Trouver l'index d'insertion de x dans la liste ordonnée a. lo et hi sont utilisés pour spécifier la plage de la liste, et la valeur par défaut est d'utiliser la liste entière. Si x existe déjà, insérez-le à gauche. La valeur de retour est l'index.

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

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

Ces deux fonctions sont similaires à bisect_left, mais si x existe déjà, insérez-le à droite.

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

Insérer x dans la liste ordonnée a. L'effet est le même que a.insert(bisect.bisect_left(a,x, lo, hi), x).

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

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

Similaire à insort_left, mais si x existe déjà, insérez-le à droite.

Les fonctions fournies par le module Bisect peuvent être divisées en deux catégories : bisect* est uniquement utilisé pour trouver l'index et n'effectue pas d'insertion réelle ; tandis que insort* est utilisé pour l'insertion réelle.

Une application typique de ce module est de calculer les niveaux de score :

def grade(score,breakpoints=[60, 70, 80, 90], grades='FDCBA'):
 i = bisect.bisect(breakpoints, score)
 return grades[i]
 
print [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]

Résultats d'exécution :

['F', 'A', 'C', 'C', 'B', 'A', 'A']

De même, nous pouvons utiliser le module bisect pour implémenter la recherche binaire :

def binary_search_bisect(lst, x):
 from bisect import bisect_left
 i = bisect_left(lst, x)
 if i != len(lst) and lst[i] == x:
 return i
 return None

Testons ses performances avec la recherche binaire implémentée par récursion et boucles :

Recursion: 4.00940990448
Loop: 2.6583480835
Bisect: 1.74922895432

Vous pouvez voir qu'elle est légèrement plus rapide que l'implémentation en boucle et presque deux fois moins rapide que l'implémentation récursive.

La célèbre bibliothèque de traitement de données de Python numpy a également une fonction numpy.searchsorted pour la recherche binaire. L'utilisation est fondamentalement la même que bisect, sauf que si vous souhaitez insérer à droite, vous devez définir le côté paramètre. ='correct', par exemple :

>>> import numpy as np
>>> from bisect import bisect_left, bisect_right
>>> data = [2, 4, 7, 9]
>>> bisect_left(data, 4)
1
>>> np.searchsorted(data, 4)
1
>>> bisect_right(data, 4)
2
>>> np.searchsorted(data, 4, side='right')
2

Ensuite, comparons les performances :

In [20]: %timeit -n 100 bisect_left(data, 99999)
100 loops, best of 3: 670 ns per loop
 
In [21]: %timeit -n 100 np.searchsorted(data, 99999)
100 loops, best of 3: 56.9 ms per loop
 
In [22]: %timeit -n 100 bisect_left(data, 8888)
100 loops, best of 3: 961 ns per loop
 
In [23]: %timeit -n 100 np.searchsorted(data, 8888)
100 loops, best of 3: 57.6 ms per loop
 
In [24]: %timeit -n 100 bisect_left(data, 777777)
100 loops, best of 3: 670 ns per loop
 
In [25]: %timeit -n 100 np.searchsorted(data, 777777)
100 loops, best of 3: 58.4 ms per loop

On peut constater que l'efficacité de numpy.searchsorted est très faible, comparée à bisect, elle n'est pas du tout du même ordre de grandeur. Par conséquent, searchsorted ne convient pas à la recherche de tableaux ordinaires, mais il est assez rapide pour rechercher numpy.ndarray :

In [30]: data_ndarray = np.arange(0, 1000000)
 
In [31]: %timeit np.searchsorted(data_ndarray, 99999)
The slowest run took 16.04 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 996 ns per loop
 
In [32]: %timeit np.searchsorted(data_ndarray, 8888)
The slowest run took 18.22 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 994 ns per loop
 
In [33]: %timeit np.searchsorted(data_ndarray, 777777)
The slowest run took 31.32 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 990 ns per loop

numpy.searchsorted peut rechercher plusieurs valeurs en même temps :

>>> np.searchsorted([1,2,3,4,5], 3)
2
>>> np.searchsorted([1,2,3,4,5], 3, side='right')
3
>>> np.searchsorted([1,2,3,4,5], [-10, 10, 2, 3])
array([0, 5, 1, 2])

Résumé

Ce qui précède est l'intégralité du contenu de cet article. J'espère que le contenu de cet article pourra être utile à tout le monde dans l'apprentissage ou l'utilisation de Python. Si vous avez des questions, vous pouvez laisser des messages pour communiquer.

Pour plus d'articles sur la recherche binaire et l'implémentation du module bisect en Python, veuillez faire attention au site Web PHP chinois !