CKTIS / Python
Pridanie prvku na pravý koniec `deque`
`collections.deque.append` pridá jeden prvok na pravý koniec obojstranného radu. V tomto príklade s posuvným oknom monotónny rad uchováva indexy namiesto samotných hodnôt.
Verzia: Python 3.12
Syntax
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneV Pythone 3.12 je collections.deque.append metóda typu deque z modulu collections. Pri volaní d.append(x) odovzdáš x ako pozičný argument. Metóda pridá x na pravý koniec ako jediný prvok, aj keď je x iterovateľný objekt. Zmení priamo d a vráti None, preto nepíš d = d.append(x). Na pridanie vľavo použi appendleft(x), na pridanie jednotlivých prvkov iterovateľného objektu vpravo použi extend(iterable).
Metódy list.append aj deque.append pridávajú na koniec. Pre rad je dôležitý rozdiel v tom, že pridávanie a odoberanie na oboch koncoch deque trvá približne O(1), zatiaľ čo list.pop(0) posúva zvyšné prvky a trvá O(n).
Bez maxlen alebo pri maxlen=None nemá deque pevný limit dĺžky. Ak je deque s kladným maxlen plný, append automaticky zahodí prvok z ľavého konca namiesto toho, aby pre naplnenie vyvolala výnimku. Pri maxlen=0 sa neuchová žiadny prvok. Príklad používa deque bez obmedzenia: o tom, kedy index vypadne z okna, rozhoduje jeho pozícia vo vstupe, nie počet kandidátov.
Pri hľadaní maxím v posuvnom okne najprv pomocou popleft() odober zľava indexy, ktoré už do okna nepatria. Potom pomocou pop() odoberaj sprava indexy s hodnotou menšou alebo rovnou novej hodnote. Pri rovnakej hodnote zostane novší index v okne dlhšie. Potom na deque zavolaj candidates.append(i): ulož index i a na porovnávanie používaj values[i]. Hodnoty na zvyšných indexoch zľava doprava klesajú, takže v úplnom okne je values[candidates[0]] maximum.
Prí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ýsledok
[4, 5, 5, 5, 3]
Keď príde druhá hodnota `2`, jej index `2` nahradí index `1`. V poslednom okne index `3` s hodnotou `5` vypadne z okna a odoberie sa zľava. Maximum je potom `3`.
Súvisiace lekcie
- Python · Lekcia 41 · Pokročilá · Verzia: 5