Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / Python

Adicionar um elemento à direita de uma `deque`

`collections.deque.append` acrescenta um elemento à extremidade direita de uma fila de duas pontas. Neste exemplo de janela deslizante, a fila monótona guarda os índices em vez dos valores.

Versão: Python 3.12

Sintaxe

d.append(x)  # d is a collections.deque; x is passed positionally; returns None

Em Python 3.12, collections.deque.append é um método do tipo deque do módulo collections. Em d.append(x), passa x como argumento posicional. O método acrescenta x à direita como um único elemento, mesmo que x seja iterável. Altera a própria d e devolve None, por isso não escrevas d = d.append(x). Usa appendleft(x) para acrescentar à esquerda ou extend(iterable) para acrescentar à direita os elementos de um iterável.

Tanto list.append como deque.append acrescentam no fim. Para uma fila, a diferença é que uma deque permite adicionar e remover elementos nas duas extremidades em tempo de aproximadamente O(1), enquanto list.pop(0) desloca os restantes elementos e demora O(n).

Se maxlen for omitido ou tiver o valor None, a deque não tem um limite fixo de comprimento. Quando uma deque com maxlen positivo está cheia, append descarta automaticamente o elemento mais à esquerda em vez de lançar uma exceção por estar cheia. Com maxlen=0, não fica guardado nenhum elemento. O exemplo usa uma deque sem limite: o que determina quando um índice sai da janela é a sua posição nos dados de entrada, não o número de candidatos.

Para obter os máximos de uma janela deslizante, remove à esquerda com popleft() os índices que já ficaram fora da janela. Depois, usa pop() para remover à direita os índices cujos valores são menores ou iguais ao novo valor. Para valores iguais, o índice mais recente permanece mais tempo na janela. Chama então candidates.append(i) na deque: guarda o índice i e usa values[i] nas comparações. Os valores nos índices restantes diminuem da esquerda para a direita, pelo que values[candidates[0]] é o máximo quando a janela está completa.

Exemplos

from collections import deque

values = [4, 2, 2, 5, 3, 1, 2]
width = 3
candidates = deque()
maxima = []

for i, value in enumerate(values):
    while candidates and candidates[0] <= i - width:
        candidates.popleft()
    while candidates and values[candidates[-1]] <= value:
        candidates.pop()
    candidates.append(i)
    if i >= width - 1:
        maxima.append(values[candidates[0]])

print(maxima)

Resultado

[4, 5, 5, 5, 3]

Quando chega o segundo `2`, o seu índice `2` substitui o índice `1`. Na última janela, o índice `3`, cujo valor é `5`, fica fora da janela e é removido à esquerda. O máximo passa a ser `3`.

Lições relacionadas

  • Python · Lição 41 · Avançado · Versão: 5

Fontes