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 custosas, isso pode ser uma melhoria em relação à abordagem mais comum. O módulo é denominado bisect porque usa um algoritmo de bisseção básico para fazer seu trabalho. O código-fonte pode ser mais útil como um exemplo funcional de algoritmo (as condições fronteiriças já estão certas!).

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.

The returned insertion point i partitions the array a into two halves so that all(val < x for val in a[lo : i]) for the left side and all(val >= x for val in a[i : hi]) for the right side.

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.

If key is None, the elements are compared directly with no intervening function call.

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.

The returned insertion point i partitions the array a into two halves so that all(val <= x for val in a[lo : i]) for the left side and all(val > x for val in a[i : hi]) for the right side.

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.

If key is None, the elements are compared directly with no intervening function call.

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.

Esta função primeiro executa bisect_left() para localizar um ponto de inserção. Em seguida, ele executa o método insert() em a para inserir x na posição apropriada para manter a ordem de classificação.

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.

Tenha em mente que a busca O(log n) é dominada pelo etapa de inserção lenta O(n).

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.

Esta função primeiro executa bisect_right() para localizar um ponto de inserção. Em seguida, ele executa o método insert() em a para inserir x na posição apropriada para manter a ordem de classificação.

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.

Tenha em mente que a busca O(log n) é dominada pelo etapa de inserção lenta O(n).

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.

• As funções insort() são O(n) porque a etapa de busca logarítmica é dominada pela etapa de inserção de tempo linear.

• As funções de busca são stateless e descartam os resultados da função chave depois que são usadas. Consequentemente, se as funções de busca forem usadas em um laço, a função chave pode ser chamada repetidamente nos mesmos elementos do vetor. Se a função chave não for rápida, considere envolvê-la com functools.cache() para evitar cálculos duplicados. Como alternativa, considere buscar um vetor de chaves pré-calculadas para localizar o ponto de inserção (conforme mostrado na seção de exemplos abaixo).

Ver também

• Sorted Collections é um módulo de alto desempenho que usa bisseção para gerenciar coleções de dados classificadas.

• A receita de SortedCollection usa bisseção para construir uma classe de coleção completa com métodos de busca diretos e suporte para uma função chave. As chaves são pré-calculadas para economizar em chamadas desnecessárias para a função chave durante as buscas.

Buscando em listas ordenadas

As funções de bisseção acima são úteis para encontrar pontos de inserção, mas podem ser complicadas ou difíceis de usar para tarefas comuns de busca. As cinco funções a seguir mostram como transformá-las nas buscas padrão para listas ordenadas:

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

A função bisect() pode ser útil para buscas em tabelas numéricas. Este exemplo usa bisect() para buscar uma nota em letra para uma pontuação de exame (digamos) com base em um conjunto de pontos de interrupção numéricos ordenados: 90 e acima é um “A”, 80 a 89 é um “B” e por aí vai:

>>>

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

As funções bisect() e insort() também funcionam com listas de tuplas. O argumento key pode servir para extrair o campo usado para ordenar registros em uma tabela:

>>>

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

Se a função chave for custosa, é possível evitar chamadas de função repetidas buscando uma lista de chaves pré-calculadas para encontrar o índice de um registro:

>>>

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