Ausführliche Erläuterung der in Python implementierten binären Suche und des Bisect-Moduls

Vorwort

Tatsächlich ist die interne Implementierung der Python-Liste (Liste) ein Array, bei dem es sich um eine lineare Liste handelt. Um Elemente in einer Liste zu finden, können Sie die Methode list.index() verwenden, deren Zeitkomplexität O(n) ist. Bei großen Datenmengen kann die binäre Suche zur Optimierung eingesetzt werden.

Die binäre Suche erfordert, dass Objekte geordnet werden müssen. Das Grundprinzip ist wie folgt:

1. Beginnend mit dem mittleren Element des Arrays, wenn das mittlere Element zufällig das zu seinde Element ist gesucht, der Suchvorgang endet;

2. Wenn ein bestimmtes Element größer oder kleiner als das mittlere Element ist, suchen Sie in der Hälfte des Arrays, die größer oder kleiner als das mittlere Element ist. und starten Sie den Vergleich wie zuvor vom mittleren Element aus.

3. Wenn das Array in einem bestimmten Schritt leer ist, bedeutet dies, dass es nicht gefunden werden kann.

Binäre Suche wird auch zu einer binären Suche. Jeder Vergleich des Algorithmus reduziert den Suchbereich um die Hälfte und seine zeitliche Komplexität beträgt O(logn).

Wir verwenden Rekursion und Schleifen, um die binäre Suche zu implementieren:

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

Dann führen wir einen Leistungstest für diese beiden Implementierungen durch:

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()

Die Ausführungsergebnisse lauten wie folgt:

Recursion: 3.12596702576
Loop: 2.08254289627

Es ist ersichtlich, dass die Schleifenmethode effizienter ist als die Rekursion.

Bisect-Modul

Python verfügt über ein Bisect-Modul zum Verwalten geordneter Listen. Das Bisect-Modul implementiert einen Algorithmus zum Einfügen von Elementen in eine geordnete Liste. In manchen Fällen ist dies effizienter, als die Liste wiederholt zu sortieren oder eine große Liste zu erstellen und diese dann zu sortieren. Bisect bedeutet Halbierung. Die Bisektionsmethode wird hier zum Sortieren verwendet. Sie fügt ein Element an der entsprechenden Position einer geordneten Liste ein, sodass nicht jedes Mal die Sortierung aufgerufen werden muss, um die geordnete Liste zu verwalten.

Das Folgende ist ein einfaches Anwendungsbeispiel:

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

Ausgabeergebnis:

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]

Bisect-Modul bietet Die Funktionen sind:

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

Finden Sie den Index zum Einfügen von x in die geordnete Liste a. lo und hi werden verwendet, um den Bereich der Liste anzugeben. Standardmäßig wird die gesamte Liste verwendet. Wenn x bereits existiert, fügen Sie es links ein. Der Rückgabewert ist index.

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

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

Diese beiden Funktionen ähneln bisect_left, aber wenn x bereits existiert, fügen Sie es rechts ein.

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

Füge x in die geordnete Liste a ein. Der Effekt ist der gleiche wie bei 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)) :

Ähnlich wie insort_left, aber wenn x bereits existiert, fügen Sie es rechts ein.

Die vom Bisect-Modul bereitgestellten Funktionen können in zwei Kategorien unterteilt werden: bisect* wird nur zum Suchen des Indexes verwendet und führt keine tatsächliche Einfügung durch, während insort* für die tatsächliche Einfügung verwendet wird.

Eine typische Anwendung dieses Moduls ist die Berechnung von Punkteständen:

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]]

Ausführungsergebnisse:

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

Ebenso können wir das Bisect-Modul verwenden, um die binäre Suche zu implementieren:

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

Testen wir seine Leistung mit der binären Suche, die durch Rekursion und Schleifen implementiert wird:

Recursion: 4.00940990448
Loop: 2.6583480835
Bisect: 1.74922895432

Sie sehen, dass es etwas schneller ist als die Schleifenimplementierung und fast halb so schnell wie die rekursive Implementierung.

Numpy, die berühmte Datenverarbeitungsbibliothek von Python, verfügt auch über die Funktion numpy.searchsorted für die binäre Suche. Die Verwendung ist im Grunde die gleiche wie bei bisect, außer dass Sie die Parameterseite festlegen müssen, wenn Sie sie rechts einfügen möchten ='richtig', zum Beispiel:

>>> 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

Dann vergleichen wir die Leistung:

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

Es kann gefunden werden Die Effizienz von numpy.searchsorted ist sehr gering und liegt im Vergleich zu bisect überhaupt nicht in derselben Größenordnung. Daher eignet sich searchsorted nicht zum Durchsuchen gewöhnlicher Arrays, ist aber recht schnell zum Durchsuchen von 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 kann mehrere Werte gleichzeitig durchsuchen:

>>> 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])

Zusammenfassung

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels für jeden beim Erlernen oder Verwenden von Python hilfreich sein kann. Wenn Sie Fragen haben, können Sie Nachrichten zur Kommunikation hinterlassen.

Weitere verwandte Artikel zur binären Suche und zur Implementierung von Bisect-Modulen in Python finden Sie auf der chinesischen PHP-Website!