CKTIS / Python
Přidání prvku na pravý konec `deque`
`collections.deque.append` přidá jeden prvek na pravý konec oboustranné fronty. V tomto příkladu s posuvným oknem monotónní fronta ukládá indexy místo samotných hodnot.
Verze: Python 3.12
Syntaxe
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneV Pythonu 3.12 je collections.deque.append metoda typu deque z modulu collections. Při volání d.append(x) předáte x jako poziční argument. Metoda přidá x na pravý konec jako jediný prvek, i když je x iterovatelný objekt. Změní přímo d a vrátí None, proto nepište d = d.append(x). Pro přidání vlevo použijte appendleft(x), pro přidání jednotlivých prvků iterovatelného objektu vpravo použijte extend(iterable).
Metody list.append i deque.append přidávají na konec. Pro frontu je důležitý rozdíl v tom, že přidávání a odebírání na obou koncích deque trvá přibližně O(1), zatímco list.pop(0) posouvá zbývající prvky a trvá O(n).
Bez maxlen nebo při maxlen=None nemá deque pevný limit délky. Je-li deque s kladným maxlen plná, append automaticky zahodí prvek z levého konce, místo aby kvůli naplnění vyvolala výjimku. Při maxlen=0 se žádný prvek neuchová. Příklad používá deque bez omezení: o tom, kdy index vypadne z okna, rozhoduje jeho pozice ve vstupu, ne počet kandidátů.
Při hledání maxim v posuvném okně nejprve pomocí popleft() odeberte zleva indexy, které už do okna nepatří. Pak pomocí pop() odebírejte zprava indexy s hodnotou menší nebo rovnou nové hodnotě. Při stejné hodnotě zůstane novější index v okně déle. Poté na deque zavolejte candidates.append(i): uložte index i a pro porovnávání používejte values[i]. Hodnoty na zbývajících indexech zleva doprava klesají, takže v úplném okně je values[candidates[0]] maximum.
Příklady
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)
Výsledek
[4, 5, 5, 5, 3]
Při příchodu druhé hodnoty `2` její index `2` nahradí index `1`. V posledním okně index `3` s hodnotou `5` vypadne z okna a odebere se zleva. Maximum je pak `3`.
Související lekce
- Python · Lekce 41 · Pokročilá · Verze: 5