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

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 i particiona o vetor a em duas metades de modo que all(val < x for val in a[lo:i]) para o lado esquerdo e all(val >= x for val in a[i:hi]) para o lado direito.

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

bisect.bisect(a, x, lo=0, hi=len(a))

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 i particiona o vetor a em duas metades de modo que all(val <= x for val in a[lo:i]) para o lado esquerdo e all(val > x for val in a[i:hi]) para o lado direito.

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

Insere x em a na ordem de classificação. Isso é equivalente a a.insert(bisect.bisect_left(a, x, lo, hi), x) supondo que a já esteja ordenado. Lembre-se de que a pesquisa O(log n) é dominada pela lenta etapa de inserção O(n).

bisect.insort_right(a, x, lo=0, hi=len(a))

bisect.insort(a, x, lo=0, hi=len(a))

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

Ver também

Receita de SortedCollection que usa bisect para construir uma classe de coleção completa com métodos de pesquisa 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 pesquisas.

8.6.1. Pesquisando em listas ordenadas

As funções bisect() acima são úteis para encontrar pontos de inserção, mas podem ser complicadas ou difíceis de usar para tarefas comuns de pesquisa. As cinco funções a seguir mostram como transformá-las nas pesquisas 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

8.6.2. Outros Exemplos

A função bisect() pode ser útil para pesquisas em tabelas numéricas. Este exemplo usa bisect() para pesquisar 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']

Ao contrário da função sorted(), não faz sentido que as funções bisect() tenham argumentos key ou reversed porque isso levaria a um design ineficiente (chamadas sucessivas para funções bisect não “lembrariam” de todas as pesquisas de chave anteriores).

Em vez disso, é melhor pesquisar uma lista de chaves pré-computadas para encontrar o índice do registro em questão:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed 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)