bisect — Bisektionsalgoritm för array

Källkod: Lib/bisect.py

Den här modulen ger stöd för att hålla en lista i sorterad ordning utan att behöva sortera listan efter varje inmatning. För långa listor med objekt med dyra jämförelseoperationer kan detta vara en förbättring jämfört med linjära sökningar eller frekventa sorteringar.

Modulen kallas bisect eftersom den använder en grundläggande bisektionsalgoritm för att utföra sitt arbete. Till skillnad från andra bisektionsverktyg som söker efter ett specifikt värde är funktionerna i den här modulen utformade för att hitta en insättningspunkt. Följaktligen anropar funktionerna aldrig en __eq__()-metod för att avgöra om ett värde har hittats. Istället anropar funktionerna endast metoden __lt__() och returnerar en insättningspunkt mellan värden i en array.

Anteckning

Funktionerna i denna modul är inte trådsäkra. Om flera trådar samtidigt använder bisect-funktioner på samma sekvens kan detta leda till odefinierat beteende. På samma sätt blir resultatet odefinierat om den angivna sekvensen muteras av en annan tråd medan en bisect-funktion används på den. Till exempel kan användning av insort_left() på samma lista från flera trådar resultera i att listan blir osorterad.

Följande funktioner finns tillgängliga:

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

Placera insättningspunkten för x i a för att bibehålla den sorterade ordningen. Parametrarna lo och hi kan användas för att ange en delmängd av listan som ska beaktas; som standard används hela listan. Om x redan finns i a kommer inmatningspunkten att ligga före (till vänster om) alla befintliga poster. Returvärdet är lämpligt att använda som första parameter i list.insert() förutsatt att a redan är sorterad.

Den returnerade insättningspunkten ip delar upp matrisen a i två skivor så att all(elem < x for elem in a[lo : ip]) är sann för den vänstra skivan och all(elem >= x for elem in a[ip : hi]) är sann för den högra skivan.

key anger en key function med ett argument som används för att extrahera en jämförelsenyckel från varje element i matrisen. För att underlätta sökning i komplexa poster tillämpas inte nyckelfunktionen på x-värdet.

Om key är None jämförs elementen direkt och ingen nyckelfunktion anropas.

Ändrad i version 3.10: Lagt till parametern key.

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

Liknar bisect_left(), men returnerar en insättningspunkt som kommer efter (till höger om) alla befintliga poster av x i a.

Den returnerade insättningspunkten ip delar upp matrisen a i två skivor så att all(elem <= x for elem in a[lo : ip]) är sann för den vänstra skivan och all(elem > x for elem in a[ip : hi]) är sann för den högra skivan.

Ändrad i version 3.10: Lagt till parametern key.

bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)

Infoga x i a i sorterad ordning.

Denna funktion kör först bisect_left() för att lokalisera en infogningspunkt. Därefter kör den metoden insert() på a för att infoga x på lämplig plats för att bibehålla sorteringsordningen.

För att stödja infogning av poster i en tabell tillämpas key-funktionen (om sådan finns) på x för söksteget men inte för infogningssteget.

Tänk på att O(log n)-sökningen domineras av det långsamma O(n)-insättningssteget.

Ändrad i version 3.10: Lagt till parametern key.

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort(a, x, lo=0, hi=len(a), *, key=None)

Liknar insort_left(), men infogar x i a efter alla befintliga poster av x.

Denna funktion kör först bisect_right() för att lokalisera en insättningspunkt. Därefter kör den metoden insert() på a för att infoga x på lämplig plats för att bibehålla sorteringsordningen.

För att stödja infogning av poster i en tabell tillämpas key-funktionen (om sådan finns) på x för söksteget men inte för infogningssteget.

Tänk på att O(log n)-sökningen domineras av det långsamma O(n)-insättningssteget.

Ändrad i version 3.10: Lagt till parametern key.

Anteckningar om prestanda

När du skriver tidskänslig kod med hjälp av bisect() och insort() ska du tänka på följande:

  • Bisektion är effektivt för sökning av värdeintervall. För att hitta specifika värden är ordböcker mer effektiva.

  • Funktionerna insort() är O(n) eftersom det logaritmiska söksteget domineras av det linjära tidsinsättningssteget.

  • Sökfunktionerna är stateless och kasserar nyckelfunktionens resultat efter att de har använts. Om sökfunktionerna används i en slinga kan nyckelfunktionen därför anropas om och om igen på samma arrayelement. Om nyckelfunktionen inte är snabb kan du överväga att omsluta den med functools.cache() för att undvika dubbla beräkningar. Alternativt kan du överväga att söka i en matris med förberäknade nycklar för att lokalisera insättningspunkten (som visas i exempelavsnittet nedan).

Se även

  • Sorted Collections är en högpresterande modul som använder bisect för att hantera sorterade samlingar av data.

  • Receptet SortedCollection använder bisect för att bygga en fullfjädrad samlingsklass med enkla sökmetoder och stöd för en nyckelfunktion. Nycklarna är förberäknade för att spara onödiga anrop till nyckelfunktionen under sökningar.

Söka i sorterade listor

Ovanstående bisect-funktioner är användbara för att hitta insättningspunkter men kan vara knepiga eller besvärliga att använda för vanliga sökuppgifter. Följande fem funktioner visar hur man omvandlar dem till standarduppslagningar för sorterade listor:

def index(a, x):
    "Leta reda på värdet längst till vänster som är exakt lika med x
    i = bisect_left(a, x)
    om i != len(a) och a[i] == x:
        returnera i
    höja ValueError

def find_lt(a, x):
    "Hitta värdet längst till höger som är mindre än x
    i = bisect_left(a, x)
    if i:
        returnera a[i-1]
    raise Värdefel

def find_le(a, x):
    "Hitta värdet längst till höger som är mindre än eller lika med x
    i = bisect_right(a, x)
    om i:
        returnera a[i-1]
    raise Värdefel

def find_gt(a, x):
    "Hitta värdet längst till vänster som är större än x
    i = bisect_right(a, x)
    om i != len(a):
        returnera a[i]
    raise VärdeFel

def find_ge(a, x):
    "Hitta objektet längst till vänster som är större än eller lika med x
    i = bisect_left(a, x)
    om i != len(a):
        returnera a[i]
    raise VärdeFel

Exempel

Funktionen bisect() kan vara användbar för numeriska tabelluppslagningar. I detta exempel används bisect() för att slå upp ett bokstavsbetyg för ett provresultat (säg) baserat på en uppsättning ordnade numeriska brytpunkter: 90 och uppåt är ett ’A’, 80 till 89 är ett ’B’, och så vidare:

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

Funktionerna bisect() och insort() fungerar också med listor av tupler. Argumentet key kan användas för att extrahera det fält som används för att ordna poster i en tabell:

>>> from collections import namedtuple
>>> from operator import attrgetter
>>> from bisect import bisect, insort
>>> from pprint import pprint

>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))

>>> movies = [
...     Movie('Jaws', 1975, 'Spielberg'),
...     Movie('Titanic', 1997, 'Cameron'),
...     Movie('The Birds', 1963, 'Hitchcock'),
...     Movie('Aliens', 1986, 'Cameron')
... ]

>>> # Find the first movie released after 1960
>>> by_year = attrgetter('released')
>>> movies.sort(key=by_year)
>>> movies[bisect(movies, 1960, key=by_year)]
Movie(name='The Birds', released=1963, director='Hitchcock')

>>> # Insert a movie while maintaining sort order
>>> romance = Movie('Love Story', 1970, 'Hiller')
>>> insort(movies, romance, key=by_year)
>>> pprint(movies)
[Movie(name='The Birds', released=1963, director='Hitchcock'),
 Movie(name='Love Story', released=1970, director='Hiller'),
 Movie(name='Jaws', released=1975, director='Spielberg'),
 Movie(name='Aliens', released=1986, director='Cameron'),
 Movie(name='Titanic', released=1997, director='Cameron')]

Om nyckelfunktionen är dyr är det möjligt att undvika upprepade funktionsanrop genom att söka i en lista med förberäknade nycklar för att hitta indexet för en post:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data]         # Precompute a list of keys.
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)