Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / Python

Pridanie prvku na pravý koniec `deque`

`collections.deque.append` pridá jeden prvok na pravý koniec obojstranného radu. V tomto príklade s posuvným oknom monotónny rad uchováva indexy namiesto samotných hodnôt.

Verzia: Python 3.12

Syntax

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

V Pythone 3.12 je collections.deque.append metóda typu deque z modulu collections. Pri volaní d.append(x) odovzdáš x ako pozičný argument. Metóda pridá x na pravý koniec ako jediný prvok, aj keď je x iterovateľný objekt. Zmení priamo d a vráti None, preto nepíš d = d.append(x). Na pridanie vľavo použi appendleft(x), na pridanie jednotlivých prvkov iterovateľného objektu vpravo použi extend(iterable).

Metódy list.append aj deque.append pridávajú na koniec. Pre rad je dôležitý rozdiel v tom, že pridávanie a odoberanie na oboch koncoch deque trvá približne O(1), zatiaľ čo list.pop(0) posúva zvyšné prvky a trvá O(n).

Bez maxlen alebo pri maxlen=None nemá deque pevný limit dĺžky. Ak je deque s kladným maxlen plný, append automaticky zahodí prvok z ľavého konca namiesto toho, aby pre naplnenie vyvolala výnimku. Pri maxlen=0 sa neuchová žiadny prvok. Príklad používa deque bez obmedzenia: o tom, kedy index vypadne z okna, rozhoduje jeho pozícia vo vstupe, nie počet kandidátov.

Pri hľadaní maxím v posuvnom okne najprv pomocou popleft() odober zľava indexy, ktoré už do okna nepatria. Potom pomocou pop() odoberaj sprava indexy s hodnotou menšou alebo rovnou novej hodnote. Pri rovnakej hodnote zostane novší index v okne dlhšie. Potom na deque zavolaj candidates.append(i): ulož index i a na porovnávanie používaj values[i]. Hodnoty na zvyšných indexoch zľava doprava klesajú, takže v úplnom okne je values[candidates[0]] maximum.

Prí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ýsledok

[4, 5, 5, 5, 3]

Keď príde druhá hodnota `2`, jej index `2` nahradí index `1`. V poslednom okne index `3` s hodnotou `5` vypadne z okna a odoberie sa zľava. Maximum je potom `3`.

Súvisiace lekcie

  • Python · Lekcia 41 · Pokročilá · Verzia: 5

Zdroje