2.38. Prioriteettijonot¶

Prioriteettijono on säiliö, joka tietää aina, mikä sen alkioista on pienin (tai suurin) ilman, että koko sisältöä tarvitsee lajitella. heapq toteuttaa sellaisen MicroPythonissa käyttäen tavallista list-oliota tallennustilana ja puuhun perustuvaa algoritmia nimeltä minimikeko, joka pitää pienimmän alkion indeksissä 0.

2.38.1. Ajatusmalli¶

Minimikeko on lista, joka on järjestetty niin, että jokaisessa indeksissä oleva alkio on pienempi tai yhtä suuri kuin indekseissä 2*i + 1 ja 2*i + 2 olevat alkiot. Tämä järjestely tekee kolmesta operaatiosta edullisia:

Pienimmän alkion löytäminen – se on kohdassa heap[0]. Yksi indeksihaku, ei läpikäyntiä.
Alkion lisääminen – se kuplii ylöspäin puun läpi vertaillen yhteen vanhempaan tasoa kohden. Tuhat alkiota vaatii noin kymmenen vertailua; miljoona noin kaksikymmentä.
Pienimmän alkion poistaminen – sama läpikäynti käänteisesti, samalla kourallisella vertailuja.

Listaa ei ole lajiteltu. Sen läpikäynti antaa alkiot mielivaltaisessa järjestyksessä. Vain heap[0] on taatusti minimi.

2.38.2. Kolme funktiota MicroPythonissa¶

MicroPythonin heapq tarjoaa täsmälleen kolme funktiota:

heapq.heappush() – lisää alkion säilyttäen kekoinvariantin eheänä.
heapq.heappop() – poistaa ja palauttaa pienimmän alkion.
heapq.heapify() – järjestää olemassa olevan listan keoksi paikan päällä.

Siinä koko rajapinta. CPythonin heappushpop, heapreplace, nlargest, nsmallest ja merge eivät ole olemassa; alla olevat mallit näyttävät, miten yleisimmät niistä rakennetaan käsin.

Tyhjästä aloittaen:

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

Olemassa olevasta datasta aloittaen:

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

Keon muodostaminen koskettaa jokaista alkiota kerran ja on huomattavasti nopeampaa kuin samojen alkioiden lisääminen yksi kerrallaan.

2.38.3. N suurinta virrasta¶

Prioriteettijonon luonteva käyttö: seuraa N suurinta alkiota virrassa, jonka voit lukea vain kerran.

Kikka on pitää yllä kokoa N olevaa minimikekoa. Jokainen uusi arvo työnnetään; jos keko kasvaa yli N:n, pudota pienin pois. Pienin on aina kohdassa heap[0], joten yksi vertailu ratkaisee, säilytetäänkö vai hylätäänkö kukin saapuva alkio:

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

Keko ei koskaan kasva yli N:n, joten jokainen saapuva arvo maksaa saman kourallisen vertailuja riippumatta siitä, kuinka pitkä virta on. Lopullinen sorted on ainoa vaihe, jonka kustannus riippuu suoraan N:stä.

2.38.4. Ajoitetut tapahtumat¶

(deadline, payload)-monikoiden prioriteettijono on tapahtuma-ajastimen vakiomuoto. Monikot vertautuvat leksikografisesti, joten monikko, jolla on pienin määräaika, nousee automaattisesti huipulle:

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

Jos kahdella tapahtumalla on sama määräaika, monikkovertailu siirtyy toiseen alkioon. Hyötykuormille, jotka eivät ole luonnostaan vertailtavissa, lisää laskuri monikon toiseksi alkioksi pakottaaksesi vakaan järjestyksen:

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

Nyt pienin-määräaika-ensin -käyttäytyminen säilyy ehjänä, tasapelit ratkeavat laskurin perusteella, joten aiemmin ajoitetut tehtävät suoritetaan ensin, eikä task-olion tarvitse olla vertailtavissa.

2.38.5. Mitä `heapq` ei tarjoa¶

Muutama malli, jotka näyttävät siltä kuin niiden pitäisi toimia, mutta eivät:

for x in heap -läpikäynti ei anna lajiteltua tulosta – listan taustalla oleva järjestys on keon puurakenne. Kuluttaaksesi keon järjestyksessä käytä heappop-funktiota, kunnes se on tyhjä.
Keossa jo olevan alkion prioriteettia ei voi muuttaa. Vakiokiertotapa on työntää uusi prioriteetti tuoreena merkintänä ja merkitä vanha peruutetuksi (ohita se, kun se nousee esiin).
Keko tallentaa viittaukset alkioihinsa, ei kopioita. Alkion muuttaminen sen työntämisen jälkeen voi rikkoa kekoinvariantin. Käytä muuttumattomia arvoja (numeroita, monikoita) vertailuavaimena.

Tavallisella listalla toimiva minimikeko on oikea työkalu mihin tahansa ”mikä on pienin”- tai ”mikä on kiireellisin” -kysymykseen pienessä sulautetussa laitteessa. Kolme funktiota, yksi lista, ja keko hoitaa loput.