Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / Python

Dodajanje elementa na desni konec `deque`

`collections.deque.append` doda en element na desni konec dvostranske vrste. V tem primeru z drsečim oknom monotona vrsta hrani indekse namesto samih vrednosti.

Različica: Python 3.12

Sintaksa

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

V Pythonu 3.12 je collections.deque.append metoda tipa deque iz modula collections. Pri klicu d.append(x) podaj x kot pozicijski argument. Metoda doda x na desni konec kot en element, tudi če je x iterabilen. Spremeni kar d in vrne None, zato ne piši d = d.append(x). Za dodajanje na levi uporabi appendleft(x), za dodajanje elementov iterabilnega objekta na desni pa extend(iterable).

Tako list.append kot deque.append dodajata na konec. Za vrsto je pomembna razlika, da imata dodajanje in odstranjevanje na obeh koncih deque časovno zahtevnost približno O(1), medtem ko list.pop(0) premakne preostale elemente in zahteva čas O(n).

Če maxlen izpustiš ali nastaviš na None, deque nima določene največje dolžine. Ko je deque s pozitivnim maxlen polna, append samodejno zavrže skrajni levi element, ne da bi zaradi polnosti sprožila izjemo. Pri maxlen=0 se ne ohrani noben element. Primer uporablja neomejeno deque: kdaj indeks izpade iz okna, določa njegov položaj v vhodnih podatkih, ne število kandidatov.

Za iskanje maksimumov v drsečem oknu najprej s popleft() na levi odstrani indekse zunaj okna. Nato s pop() na desni odstrani indekse, katerih vrednosti so manjše ali enake novi vrednosti. Pri enaki vrednosti novejši indeks ostane v oknu dlje. Zatem na deque pokliči candidates.append(i): shrani indeks i, za primerjave pa uporabi values[i]. Vrednosti na preostalih indeksih od leve proti desni padajo, zato je pri polnem oknu values[candidates[0]] maksimum.

Primeri

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]

Ko se pojavi druga vrednost `2`, njen indeks `2` nadomesti indeks `1`. V zadnjem oknu indeks `3` z vrednostjo `5` izpade iz okna in ga odstranimo na levi. Maksimum je nato `3`.

Povezane lekcije

  • Python · Lekcija 41 · Napredna · Različica: 5

Viri