База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / Python

Добавяне в десния край на `deque`

`collections.deque.append` добавя един елемент в десния край на двустранна опашка. В този пример с плъзгащ се прозорец монотонната опашка съхранява индексите вместо самите стойности.

Версия: Python 3.12

Синтаксис

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

В Python 3.12 collections.deque.append е метод на типа deque от модула collections. При извикване на d.append(x) подаваш x като позиционен аргумент. Методът добавя x като един елемент в десния край, дори ако x е итерируем обект. Той променя самия d и връща None, затова не пиши d = d.append(x). Използвай appendleft(x) за добавяне отляво или extend(iterable) за добавяне на елементите на итерируем обект отдясно.

И list.append, и deque.append добавят в края. За опашките важната разлика е, че добавянето и премахването в двата края на deque отнемат приблизително O(1) време, докато list.pop(0) измества останалите елементи и отнема O(n) време.

Ако maxlen е пропуснат или е None, deque няма фиксирано ограничение на дължината. Когато deque с положителен maxlen се запълни, append автоматично премахва най-левия елемент, вместо да предизвика изключение заради запълването. При maxlen=0 не се запазват елементи. Примерът използва deque без ограничение: индексът излиза от прозореца според позицията си във входните данни, а не според броя на кандидатите.

За да намериш максимумите в плъзгащ се прозорец, премахни отляво с popleft() индексите, които вече са извън прозореца. После с pop() премахни отдясно индексите, чиито стойности са по-малки или равни на новата стойност. При равни стойности по-новият индекс остава по-дълго в прозореца. Накрая извикай candidates.append(i) върху deque: запази индекса i, а за сравненията използвай values[i]. Стойностите на оставащите индекси намаляват отляво надясно, затова при пълен прозорец values[candidates[0]] е максимумът.

Примери

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)

Резултат

[4, 5, 5, 5, 3]

Когато се появи втората стойност `2`, нейният индекс `2` заменя индекс `1`. В последния прозорец индекс `3` със стойност `5` излиза от прозореца и се премахва отляво. Тогава максимумът е `3`.

Свързани уроци

  • Python · Урок 41 · Напреднало · Версия: 5

Източници