Binäres Such- und Halbierungsmodul für Python

Die interne Implementierung der Python-Liste ist ein Array, bei dem es sich um eine lineare Liste handelt. Um ein Element in einer Liste zu finden, können Sie die Methode list.index() verwenden, die eine zeitliche Komplexität von O(n) hat. Bei großen Datenmengen kann die binäre Suche zur Optimierung eingesetzt werden. Die binäre Suche erfordert die Reihenfolge der Objekte:

1. Beginnen Sie mit dem mittleren Element des Arrays ;

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 beginnen Sie den Vergleich ab dem mittleren Element vor.

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

Die 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 bzw. Schleife, 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

Führen Sie dann 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 sind wie folgt folgt:

Recursion: 3.12596702576
Loop: 2.08254289627

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

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]

Die vom Bisect-Modul bereitgestellten 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 des Score-Levels:

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ührungsergebnis:

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

Ähnlich 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 die Leistung mit der binären Suche, die durch Rekursion und Schleife implementiert wird:

Recursion: 4.00940990448
Loop: 2.6583480835
Bisect: 1.74922895432

Sie können sehen, dass sie etwas schneller ist als die Schleifenimplementierung und fast die Hälfte schneller als 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 ='right', 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 noch einmal 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 festgestellt werden, dass die Effizienz von numpy.searchsorted sehr gering ist, nicht in der gleichen Größenordnung wie die Halbierung. 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])