Estruturas eficientes: deque, heapq e bisect

deque: filas rápidas nas duas pontas

A lista do Python é excelente no fim: adicionar com append e remover com pop na última posição são O(1). O problema é o começo. Inserir ou remover no início de uma lista obriga o Python a deslocar todos os outros itens uma casa, o que é O(n). Se o seu programa trata a coleção como uma fila, tirando do início e pondo no fim, a lista vira um gargalo silencioso. A collections.deque foi feita exatamente para isso: uma fila de duas pontas em que adicionar e remover em qualquer extremidade custa O(1).

from collections import deque

fila = deque(["ana", "bruno", "carla"])
fila.append("davi")        # entra no fim, O(1)
primeiro = fila.popleft()   # sai do inicio, O(1)
print(primeiro)             # ana
print(fila)                 # deque(["bruno", "carla", "davi"])

# A deque tambem serve de janela deslizante com tamanho fixo
ultimos = deque(maxlen=3)
for n in range(6):
    ultimos.append(n)
print(list(ultimos))        # [3, 4, 5]: so os tres ultimos

popleft e append na deque são O(1); com maxlen ela vira uma janela dos últimos itens.

O recurso do maxlen merece destaque. Ao criar uma deque com tamanho máximo, ela descarta sozinha o item mais antigo quando um novo entra. Isso resolve com elegância problemas como manter os últimos registros, uma média móvel ou um histórico limitado, sem você precisar cortar a lista manualmente a cada passo. É o tipo de detalhe que troca várias linhas de código por uma escolha de estrutura.

heapq: o menor elemento sempre à mão

Imagine que você processa tarefas por prioridade e sempre precisa da mais urgente, ou que quer os cinco maiores de uma sequência enorme. Ordenar a coleção inteira a cada consulta é caro. O módulo heapq mantém os dados como um heap, uma organização em que o menor elemento fica sempre no topo, acessível de imediato. Inserir um novo item e retirar o menor são operações eficientes, sem reordenar tudo. O heap vive numa lista comum, e o heapq oferece as funções para manipulá-la corretamente.

import heapq

tarefas = []
heapq.heappush(tarefas, (2, "responder email"))
heapq.heappush(tarefas, (1, "corrigir bug critico"))
heapq.heappush(tarefas, (3, "revisar documento"))

# heappop sempre devolve a menor prioridade primeiro
prioridade, tarefa = heapq.heappop(tarefas)
print(prioridade, tarefa)   # 1 corrigir bug critico

# Os tres maiores de uma sequencia, sem ordenar tudo
numeros = [8, 3, 15, 1, 9, 22, 4]
print(heapq.nlargest(3, numeros))   # [22, 15, 9]

O heap entrega o menor com heappop; nlargest e nsmallest evitam ordenar a coleção inteira.

bisect: listas ordenadas sem reordenar

Quando você mantém uma lista já ordenada e quer inserir um novo valor no lugar certo, ou descobrir onde ele se encaixaria, ordenar de novo a cada inserção é desperdício. O módulo bisect faz uma busca binária: em vez de varrer a lista, ele divide o intervalo pela metade a cada passo e acha a posição correta em tempo O(log n), muito mais rápido que O(n). A função bisect encontra o ponto de inserção; a insort insere já mantendo a ordem. É a ferramenta certa para rankings, faixas e tabelas de corte ordenadas.

import bisect

notas = [50, 62, 70, 85, 91]   # ja ordenada

# Onde entraria a nota 75, mantendo a ordem?
pos = bisect.bisect(notas, 75)
print(pos)                 # 3

bisect.insort(notas, 75)   # insere no lugar certo
print(notas)               # [50, 62, 70, 75, 85, 91]

# Classificar uma nota em faixas de conceito com busca binaria
cortes = [50, 70, 90]
conceitos = ["D", "C", "B", "A"]
print(conceitos[bisect.bisect(cortes, 84)])   # B

bisect acha a posição por busca binária; insort insere mantendo a lista ordenada.

O último exemplo mostra um uso elegante do bisect que muita gente não conhece: classificar um valor em faixas. Em vez de uma cadeia longa de if e elif comparando limites, você guarda os cortes ordenados e deixa a busca binária dizer em qual faixa o valor cai. O código fica menor, mais rápido e mais fácil de manter, porque adicionar uma faixa nova é só acrescentar um corte e um rótulo. É o espírito deste módulo: a estrutura certa não só acelera, ela simplifica.