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.
O módulo é chamado de bisect
porque usa um algoritmo básico de bisseção para fazer seu trabalho. Ao contrário de outras ferramentas de bisseção que buscam um valor específico, as funções neste módulo são projetadas para localizar um ponto de inserção. Da mesma forma, as funções nunca chamam um método __eq__()
para determinar se um valor foi encontrado. Em vez disso, as funções apenas chamam o método __lt__()
e retornarão um ponto de inserção entre valores em um vetor.
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 eall(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 eall(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.
Esta função primeiro executa
bisect_left()
para localizar um ponto de inserção. Em seguida, ele executa o métodoinsert()
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étodoinsert()
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):
'Encontra o valor mais à esquerda exatamente igual a x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def find_lt(a, x):
'Encontra o valor mais à direita menor que x'
i = bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
def find_le(a, x):
'Encontra o valor mais à direita menor ou igual a x'
i = bisect_right(a, x)
if i:
return a[i-1]
raise ValueError
def find_gt(a, x):
'Encontra o valor mais à esquerda maior que x'
i = bisect_right(a, x)
if i != len(a):
return a[i]
raise ValueError
def find_ge(a, x):
'Encontra o item mais à esquerda maior ou igual a 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')
... ]
>>> # Encontra o primeiro filme lançado após 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')
>>> # Insere um filme enquanto mantém a ordem de classificação
>>> 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]) # Ou use operator.itemgetter(1).
>>> keys = [r[1] for r in data] # Pré-calcula uma lista de chaves.
>>> 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)