Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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 None

W 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

Źródła