CKTIS / Python
Dodawanie po prawej stronie kolejki `deque`
`collections.deque.append` dodaje jeden element na prawym końcu kolejki dwustronnej. W tym przykładzie z przesuwającym się oknem kolejka monotoniczna przechowuje indeksy zamiast samych wartości.
Wersja: Python 3.12
Składnia
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneW Pythonie 3.12 collections.deque.append to metoda kolejki dwustronnej deque z modułu collections. Wywołanie d.append(x) przyjmuje x pozycyjnie i dodaje go jako jeden element na prawym końcu, nawet gdy x jest obiektem iterowalnym. Metoda modyfikuje d i zwraca None: nie pisz d = d.append(x). Aby dodać element po lewej, użyj appendleft(x); aby dodać po prawej kolejne elementy obiektu iterowalnego, użyj extend(iterable).
Zarówno list.append jak i deque.append dodają element na końcu. Do obsługi kolejki przydaje się jednak deque: dodawanie i zdejmowanie elementów na obu końcach zajmuje w przybliżeniu O(1), podczas gdy list.pop(0) wymaga przesunięcia pozostałych elementów i zajmuje O(n).
Bez maxlen lub przy maxlen=None kolejka nie ma ustalonego limitu długości. W pełnej kolejce z dodatnim maxlen wywołanie append automatycznie usuwa skrajny lewy element, bez zgłaszania wyjątku z powodu zapełnienia. Przy maxlen=0 żaden element nie zostaje. W przykładzie kolejka nie ma limitu: o tym, czy indeks wypadł z okna, decyduje jego pozycja, a nie liczba kandydatów.
Aby obliczyć maksimum w przesuwającym się oknie, usuń z lewej indeksy spoza okna za pomocą popleft(), a z prawej usuń przez pop() indeksy o wartościach mniejszych od nowej lub jej równych. Nowszy indeks z równą wartością pozostanie w oknie dłużej. Następnie wywołaj candidates.append(i) na deque: przechowujesz indeks i, a wartości values[i] używasz do porównań. Wartości odpowiadające pozostałym indeksom maleją od lewej do prawej, więc dla pełnego okna values[candidates[0]] jest maksimum.
Przykłady
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)
Wynik
[4, 5, 5, 5, 3]
Gdy pojawia się drugie `2`, jego indeks `2` zastępuje indeks `1`. W ostatnim oknie indeks `3` o wartości `5` wypada z okna i zostaje usunięty z lewej; maksimum wynosi wtedy `3`.
Powiązane lekcje
- Python · Lekcja 41 · Zaawansowany · Wersja: 5