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 NoneV 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