CKTIS / Python
Elemente rechts an eine `deque` anhängen
`collections.deque.append` fügt rechts an eine doppelseitige Warteschlange ein Element an. In diesem Beispiel mit einem gleitenden Fenster speichert die monotone Warteschlange Indizes statt der Werte selbst.
Version: Python 3.12
Syntax
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneIn Python 3.12 ist collections.deque.append eine Methode des Typs deque aus dem Modul collections. Bei d.append(x) übergibst du x als Positionsargument. Die Methode fügt x rechts als einzelnes Element an, auch wenn x iterierbar ist. Sie verändert d direkt und gibt None zurück. Schreibe daher nicht d = d.append(x). Mit appendleft(x) fügst du links an, mit extend(iterable) fügst du rechts die Elemente eines iterierbaren Objekts an.
Sowohl list.append als auch deque.append fügen am Ende an. Für Warteschlangen ist der Unterschied wichtig: Bei einer deque dauert das Anfügen und Entfernen an beiden Enden ungefähr O(1). list.pop(0) verschiebt dagegen die übrigen Elemente und kostet O(n).
Ohne maxlen oder mit maxlen=None hat die deque keine feste Längenbegrenzung. Ist eine deque mit positivem maxlen voll, verwirft append automatisch das Element ganz links, statt wegen der vollen deque eine Ausnahme auszulösen. Bei maxlen=0 bleiben keine Elemente erhalten. Das Beispiel verwendet eine unbegrenzte deque: Ein Index fällt aufgrund seiner Position in den Eingabedaten aus dem Fenster, nicht aufgrund der Anzahl der Kandidaten.
Für das Maximum in einem gleitenden Fenster entfernst du zuerst mit popleft() links die Indizes außerhalb des Fensters. Dann entfernst du mit pop() rechts die Indizes, deren Werte kleiner oder gleich dem neuen Wert sind. Ein neuerer Index mit demselben Wert bleibt länger im Fenster. Danach rufst du candidates.append(i) auf der deque auf: Gespeichert wird der Index i, verglichen wird mit values[i]. Die Werte an den verbleibenden Indizes fallen von links nach rechts; bei einem vollständigen Fenster ist daher values[candidates[0]] das Maximum.
Beispiele
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)
Ergebnis
[4, 5, 5, 5, 3]
Beim zweiten Wert `2` ersetzt Index `2` den Index `1`. Im letzten Fenster fällt Index `3` mit dem Wert `5` aus dem Fenster und wird links entfernt. Das Maximum ist dann `3`.
Zugehörige Lektionen
- Python · Lektion 41 · Fortgeschritten · Version: 5