Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

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 None

U 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

Izvori