CKTIS / Python
Een item rechts aan een `deque` toevoegen
`collections.deque.append` voegt één item toe aan de rechterkant van een dubbelzijdige wachtrij. In dit voorbeeld met een schuivend venster bewaart de monotone wachtrij de indices in plaats van de waarden zelf.
Versie: Python 3.12
Syntax
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneIn Python 3.12 is collections.deque.append een methode van het type deque uit de module collections. Bij d.append(x) geef je x als positioneel argument door. De methode voegt x rechts toe als één item, ook als x itereerbaar is. De methode wijzigt d zelf en geeft None terug, dus schrijf niet d = d.append(x). Gebruik appendleft(x) om links iets toe te voegen of extend(iterable) om de items uit een itereerbaar object rechts toe te voegen.
Zowel list.append als deque.append voegen aan het einde toe. Voor een wachtrij is het verschil dat bij een deque toevoegen en verwijderen aan beide uiteinden ongeveer O(1) kost, terwijl list.pop(0) de overige items verschuift en O(n) kost.
Zonder maxlen of met maxlen=None heeft de deque geen vaste lengtelimiet. Is een deque met een positieve maxlen vol, dan verwijdert append automatisch het meest linkse item, zonder een exceptie te veroorzaken omdat de deque vol is. Met maxlen=0 blijven er geen items bewaard. Het voorbeeld gebruikt een onbegrensde deque: de positie van een index in de invoer bepaalt wanneer die buiten het venster valt, niet het aantal kandidaten.
Voor de maxima van een schuivend venster verwijder je links met popleft() de indices die buiten het venster vallen. Verwijder daarna rechts met pop() de indices waarvan de waarde kleiner dan of gelijk aan de nieuwe waarde is. Bij gelijke waarden blijft de nieuwere index langer in het venster. Roep vervolgens candidates.append(i) aan op de deque: sla de index i op en gebruik values[i] om te vergelijken. De waarden op de overgebleven indices dalen van links naar rechts, dus values[candidates[0]] is het maximum zodra het venster volledig is.
Voorbeelden
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)
Resultaat
[4, 5, 5, 5, 3]
Zodra de tweede `2` langskomt, vervangt index `2` index `1`. In het laatste venster valt index `3` met waarde `5` buiten het venster en wordt die links verwijderd. Het maximum wordt dan `3`.
Gerelateerde lessen
- Python · Les 41 · Gevorderd · Versie: 5