Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / Python

Přidání prvku na pravý konec `deque`

`collections.deque.append` přidá jeden prvek na pravý konec oboustranné fronty. V tomto příkladu s posuvným oknem monotónní fronta ukládá indexy místo samotných hodnot.

Verze: Python 3.12

Syntaxe

d.append(x)  # d is a collections.deque; x is passed positionally; returns None

V Pythonu 3.12 je collections.deque.append metoda typu deque z modulu collections. Při volání d.append(x) předáte x jako poziční argument. Metoda přidá x na pravý konec jako jediný prvek, i když je x iterovatelný objekt. Změní přímo d a vrátí None, proto nepište d = d.append(x). Pro přidání vlevo použijte appendleft(x), pro přidání jednotlivých prvků iterovatelného objektu vpravo použijte extend(iterable).

Metody list.append i deque.append přidávají na konec. Pro frontu je důležitý rozdíl v tom, že přidávání a odebírání na obou koncích deque trvá přibližně O(1), zatímco list.pop(0) posouvá zbývající prvky a trvá O(n).

Bez maxlen nebo při maxlen=None nemá deque pevný limit délky. Je-li deque s kladným maxlen plná, append automaticky zahodí prvek z levého konce, místo aby kvůli naplnění vyvolala výjimku. Při maxlen=0 se žádný prvek neuchová. Příklad používá deque bez omezení: o tom, kdy index vypadne z okna, rozhoduje jeho pozice ve vstupu, ne počet kandidátů.

Při hledání maxim v posuvném okně nejprve pomocí popleft() odeberte zleva indexy, které už do okna nepatří. Pak pomocí pop() odebírejte zprava indexy s hodnotou menší nebo rovnou nové hodnotě. Při stejné hodnotě zůstane novější index v okně déle. Poté na deque zavolejte candidates.append(i): uložte index i a pro porovnávání používejte values[i]. Hodnoty na zbývajících indexech zleva doprava klesají, takže v úplném okně je values[candidates[0]] maximum.

Příklady

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)

Výsledek

[4, 5, 5, 5, 3]

Při příchodu druhé hodnoty `2` její index `2` nahradí index `1`. V posledním okně index `3` s hodnotou `5` vypadne z okna a odebere se zleva. Maximum je pak `3`.

Související lekce

  • Python · Lekce 41 · Pokročilá · Verze: 5

Zdroje