bisect — Algoritmo de bisseção de vetor

Código-fonte: Lib/bisect.py

Este módulo fornece suporte para manter uma lista em ordem de classificação sem ter que classificar a lista após cada inserção. Para longas listas de itens com operações de comparação caras, isso pode ser uma melhoria em relação a pesquisas lineares ou recorrência frequente.

The module is called bisect because it uses a basic bisection algorithm to do its work. Unlike other bisection tools that search for a specific value, the functions in this module are designed to locate an insertion point. Accordingly, the functions never call an __eq__() method to determine whether a value has been found. Instead, the functions only call the __lt__() method and will return an insertion point between values in an array.

As seguintes funções são fornecidas:

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

Localiza o ponto de inserção de x em a para manter a ordem de classificação. Os parâmetros lo e hi podem ser usados para especificar um subconjunto da lista que deve ser considerado; por padrão, toda a lista é usada. Se x já estiver presente em a, o ponto de inserção estará antes (à esquerda) de qualquer entrada existente. O valor de retorno é adequado para uso como o primeiro parâmetro para list.insert() supondo que a já esteja ordenado.

O ponto de inserção retornado ip particiona o vetor a em duas fatias de forma que all(elem < x for elem in a[lo : ip]) seja verdadeiro para a fatia esquerda e all(elem >= x for elem in a[ip : hi]) é verdadeiro para a fatia certa.

key especifica uma função chave de um argumento que é usado para extrair uma chave de comparação de cada elemento no vetor. Para oferecer suporte à pesquisa de registros complexos, a função chave não é aplicada ao valor x.

Se key for None, os elementos serão comparados diretamente e nenhuma função chave será chamada.

Alterado na versão 3.10: Adicionado o parâmetro key.

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

Semelhante a bisect_left(), mas retorna um ponto de inserção que vem depois (à direita de) qualquer entrada existente de x em a.

O ponto de inserção retornado ip particiona o vetor a em duas fatias de forma que all(elem <= x for elem in a[lo : ip]) seja verdadeiro para a fatia esquerda e all(elem > x for elem in a[ip : hi]) é verdadeiro para a fatia certa.

Alterado na versão 3.10: Adicionado o parâmetro key.

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

Insere x em a na ordem de classificação.

This function first runs bisect_left() to locate an insertion point. Next, it runs the insert() method on a to insert x at the appropriate position to maintain sort order.

Para oferecer suporte à inserção de registros em uma tabela, a função key (se houver) é aplicada a x para a etapa de pesquisa, mas não para a etapa de inserção.

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

Alterado na versão 3.10: Adicionado o parâmetro key.

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

Semelhante a insort_left(), mas inserindo x em a após qualquer entrada existente de x.

This function first runs bisect_right() to locate an insertion point. Next, it runs the insert() method on a to insert x at the appropriate position to maintain sort order.

Para oferecer suporte à inserção de registros em uma tabela, a função key (se houver) é aplicada a x para a etapa de pesquisa, mas não para a etapa de inserção.

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

Alterado na versão 3.10: Adicionado o parâmetro key.

Observações sobre desempenho

Ao escrever um código sensível ao tempo usando bisect() e insort(), lembre-se do seguinte:

  • A bisseção é eficaz para pesquisar intervalos de valores. Para localizar valores específicos, os dicionários são mais eficientes.

  • The insort() functions are O(n) because the logarithmic search step is dominated by the linear time insertion step.

  • The search functions are stateless and discard key function results after they are used. Consequently, if the search functions are used in a loop, the key function may be called again and again on the same array elements. If the key function isn’t fast, consider wrapping it with functools.cache() to avoid duplicate computations. Alternatively, consider searching an array of precomputed keys to locate the insertion point (as shown in the examples section below).

Ver também

  • Sorted Collections is a high performance module that uses bisect to managed sorted collections of data.

  • The SortedCollection recipe uses bisect to build a full-featured collection class with straight-forward search methods and support for a key-function. The keys are precomputed to save unnecessary calls to the key function during searches.

Pesquisando em listas ordenadas

The above bisect functions are useful for finding insertion points but can be tricky or awkward to use for common searching tasks. The following five functions show how to transform them into the standard lookups for sorted lists:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

Exemplos

The bisect() function can be useful for numeric table lookups. This example uses bisect() to look up a letter grade for an exam score (say) based on a set of ordered numeric breakpoints: 90 and up is an ‘A’, 80 to 89 is a ‘B’, and so on:

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

The bisect() and insort() functions also work with lists of tuples. The key argument can serve to extract the field used for ordering records in a table:

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

If the key function is expensive, it is possible to avoid repeated function calls by searching a list of precomputed keys to find the index of a record:

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