Effizienz von Python „in“ Stichwort für sortierte Liste

Question

Wenn ich eine Liste, die bereits sortiert ist und die in Schlüsselwort verwenden, zum Beispiel:

a = [1,2,5,6,8,9,10] 
print 8 in a 

Ich denke, das eine sequentielle Suche tun soll, sondern kann Ich mache es schneller, indem ich binäre Suche mache? Gibt es eine pythonische Art, in einer sortierten Liste zu suchen?

Answer 1

Es gibt eine binäre Suche nach Python in der Standardbibliothek im Modul bisect. Dabei spielt es keine in/contains unterstützen, aber Sie können eine kleine Funktion schreiben, es zu handhaben:

from bisect import bisect_left 
def contains(a, x): 
    """returns true if sorted sequence `a` contains `x`""" 
    i = bisect_left(a, x) 
    return i != len(a) and a[i] == x 

Dann allerdings Dies wird nicht sehr schnell

>>> contains([1,2,3], 3) 
True 
>>> contains([1,2,3], 4) 
False 

, wie bisect sind geschrieben in Python, und nicht in C, so dass Sie wahrscheinlich sequentielle in für ziemlich viele Fälle schneller finden.bisect hatte eine optionale C-Beschleunigung in CPython seit Python 2.4.

Es ist schwer, den genauen Break-Even-Punkt in CPython zu messen. Dies liegt daran, dass der Code in C geschrieben ist; wenn Sie auf einen Wert geprüft, die größer oder kleiner als jeder Wert in der Folge ist, dann die CPU des Verzweigungsvorhersage Tricks auf Sie spielen wird, und Sie erhalten:

In [2]: a = list(range(100)) 
In [3]: %timeit contains(a, 101) 
The slowest run took 8.09 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 370 ns per loop 

Hier ist der beste von 3 ist nicht repräsentativ der wahr Laufzeit des Algorithmus.

Aber Tweaking Tests, habe ich die Schlussfolgerung, dass die Halbierung könnte schneller als in für Listen mit nur 30 Elemente sein.

---

Allerdings, wenn Sie wirklich viele in Operationen tun sollten Sie verwenden set; Sie können die Liste einmal in einen Satz konvertieren (es nicht einmal sortiert werden wird) und der in Betrieb wird asymptotisch schneller als jede binäre Suche jemals sein würde:

>>> a = [10, 6, 8, 1, 2, 5, 9] 
>>> a_set = set(a) 
>>> 10 in a_set 
True 

Auf der anderen Seite, eine Liste Sortierung hat größer Zeit-Komplexität als ein Set zu bauen, so dass die meiste Zeit ein Set wäre der Weg zu gehen.

Answer 2

Die Standardbibliothek verfügt über das Modul bisect, das das Suchen in sortierten Sequenzen unterstützt.

Allerdings würde ich für kleine Listen wetten, dass die C-Implementierung hinter dem Operator inbisect schlagen würde. Sie müssten mit einem Bündel von gemeinsamen Fällen messen unter Hinweis auf die wirkliche Break-even auf Ihre Zielhardware ...

---

Es lohnt sich, um festzustellen, dass, wenn Sie mit einer ungeordneten iterable wegkommen kann (dh ein set), dann können Sie die Suche in O(1) Zeit im Durchschnitt (mit dem Operator in), im Vergleich zu Bisektion auf einer Sequenz, die O(logN) und der in Operator auf einer Sequenz ist, die O(N) ist. Und mit einem Set vermeiden Sie auch die Sortierkosten :-).