CKTIS / Python
Dodavanje elementa na desni kraj reda `deque`
`collections.deque.append` dodaje jedan element na desni kraj dvostranog reda. U ovom primjeru s kliznim prozorom monotoni red pohranjuje indekse umjesto samih vrijednosti.
Verzija: Python 3.12
Sintaksa
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneU Pythonu 3.12 collections.deque.append metoda je tipa deque iz modula collections. Pri pozivu d.append(x) predaj x kao pozicijski argument. Metoda dodaje x na desni kraj kao jedan element, čak i ako je x iterabilan. Mijenja sam objekt d i vraća None, pa nemoj pisati d = d.append(x). Za dodavanje na lijevi kraj upotrijebi appendleft(x), a za dodavanje pojedinačnih elemenata iterabilnog objekta na desni kraj upotrijebi extend(iterable).
I list.append i deque.append dodaju na kraj. Za red je važna razlika što dodavanje i uklanjanje na oba kraja reda deque traje približno O(1), dok list.pop(0) pomiče preostale elemente i traje O(n).
Ako izostaviš maxlen ili postaviš maxlen=None, deque nema fiksno ograničenje duljine. Kada je deque s pozitivnim maxlen pun, append automatski odbacuje krajnji lijevi element umjesto da zbog popunjenosti izazove iznimku. Uz maxlen=0 ne zadržava se nijedan element. Primjer koristi deque bez ograničenja: hoće li indeks ispasti iz prozora ovisi o njegovu položaju u ulaznim podacima, a ne o broju kandidata.
Za pronalaženje maksimuma kliznog prozora prvo pomoću popleft() slijeva ukloni indekse koji više nisu u prozoru. Zatim pomoću pop() zdesna ukloni indekse čije su vrijednosti manje ili jednake novoj vrijednosti. Pri jednakim vrijednostima noviji indeks dulje ostaje u prozoru. Potom na objektu deque pozovi candidates.append(i): spremi indeks i, a za usporedbe koristi values[i]. Vrijednosti na preostalim indeksima opadaju slijeva nadesno, pa je values[candidates[0]] maksimum kada je prozor potpun.
Primjeri
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)
Rezultat
[4, 5, 5, 5, 3]
Kad stigne drugi `2`, njegov indeks `2` zamjenjuje indeks `1`. U posljednjem prozoru indeks `3` s vrijednošću `5` ispada iz prozora i uklanja se slijeva. Maksimum je tada `3`.
Povezane lekcije
- Python · Lekcija 41 · Napredno · Verzija: 5