3. Stromy a generátory

Keď sme ale definovali triedu rad, vedeli sme to urobiť tak, aby práca s radom nezávisela od konkrétnej realizácie.

class Queue:
    def __init__(self):
        '''nicializácia dátovejh štruktúry'''

    def is_empty(self):
        '''zistí, či je rad prázdny'''

    def enqueue(self, data):
        '''vloží na koniec radu'''

    def dequeue(self):
        '''vyberie zo začiatku radu'''

    def front(self):
        '''vráti prvý prvok radu'''

Práca s radom bude vždy rovnaká bez ohľadu na to, či je realizovaná zoznamom (list), spájaným zoznamom alebo cyklickým poľom. Preto sa budeme zaoberať štruktúrou strom tak, aby metódy nezáviseli od konkrétnej realizácie.

V prvom ročníku sme dátovú štruktúru strom riešili vždy len ako spájanú štruktúru, t. j. potomkovia vrcholu boli uložení ako referencie na objekty:

class BinarnyStrom:

    class Vrchol:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right

    def __init__(self):
        self.root = None

    def __len__(self):

        def pocet_rek(vrch):
            if vrch is None:
                return 0
            return 1 + pocet_rek(vrch.left) + pocet_rek(vrch.right)

        return pocet_rek(self.root)

    def preorder(self):

        def preorder_rek(vrch):
            if vrch is None:
                return ''
            return repr(vrch.data) + ' ' + preorder_rek(vrch.left) + preorder_rek(vrch.right)

        return preorder_rek(self.root)

    def postorder(self):

        def postorder_rek(vrch):
            if vrch is None:
                return ''
            return postorder_rek(vrch.left) + postorder_rek(vrch.right) + repr(vrch.data) + ' '

        return postorder_rek(self.root)

    def inorder(self):

        def inorder_rek(vrch):
            if vrch is None:
                return ''
            return inorder_rek(vrch.left) + repr(vrch.data) + ' ' + inorder_rek(vrch.right)

        return inorder_rek(self.root)

podobne pre všeobecný strom:

class VseobecnyStrom:
    class Vrchol:
        def __init__(self, data):
            self.data = data
            self.child = []

    def __init__(self):
        self.root = None

    def __len__(self):

        def pocet_rek(vrch):
            if vrch is None:
                return 0
            #return sum(map(pocet_rek, vrch.child)) + 1

            vysl = 1
            for syn in vrch.child:
                vysl += pocet_rek(syn)
            return vysl

        return pocet_rek(self.root)

    def __repr__(self):

        def repr1(vrch):
            if vrch is None:
                return '()'
            vysl = [repr(vrch.data)]
            for syn in vrch.child:
                vysl.append(repr1(syn))
            return '(' + ','.join(vysl) + ')'

        return repr1(self.root)

Pripomeňme si, ako sme mohli skonštruovať nejaký strom a potom v nejakom poradí vypísať všetky vrcholy:

>>> t = BinarnyStrom()
>>> t.root = t.Vrchol(11)
>>> t.root.left = t.Vrchol(12)
>>> t.root.right = t.Vrchol(13)
>>> t.root.right.left = t.Vrchol(14)
>>> t.root.right.right = t.Vrchol(15)
>>> t.root.left.right = t.Vrchol(16)
>>> t.preorder()
'11 12 16 13 14 15 '
>>> t.inorder()
'12 16 11 14 13 15 '

Ak by sme potrebovali realizovať strom nejakým iným spôsobom, museli by sme úplne zmeniť spôsob manipulácie s vrcholmi stromu - nemohli by sme takto jednoducho pracovať s ľavými a pravými potomkami vrcholov.

Stromy

Pripomeňme si, čo vieme o stromoch z programovania v prvom ročníku:

  • strom je množina vrcholov (node), v ktorej okrem jedného vrcholu (tzv. koreň stromu teda root) má každý vrchol práve jedného predka (tiež hovoríme otec alebo parent)
  • každý vrchol má množinu potomkov (tzv. synov alebo children) = sú to tie vrcholy, pre ktoré je tento vrchol otcom
  • vrcholu, ktorý nemá žiadnych potomkov, hovoríme list (tiež vonkajší alebo niekedy ako external alebo leaf)
  • vrcholu, ktorý má aspoň jedného potomka, hovoríme vnútorný (internal)
  • vrcholom, ktoré majú spoločného predka, hovoríme bratia, súrodenci, resp. siblings
  • hrana stromu (edge) je dvojica vrcholov (u, v), v ktorej buď v je otcom u, alebo naopak
  • cesta (path) je postupnosť vrcholov, v ktorej každé dva susedné vrcholy sú hranou

Neprázdny strom môžeme definovať napr. takto:

  • ako jeden špeciálny vrchol - koreň
  • pre všetky zvyšné vrcholy (rôzne od koreňa) platí, že každý z nich má jediný iný vrchol v strome, ktorý je jeho otcom

Niekedy sa strom definuje aj rekurzívne:

  • strom je buď prázdny
  • alebo sa skladá z jedného vrcholu r (koreň stromu) a množiny podstromov (možno prázdnej), ktorých korene sú synmi vrcholu r (zrejme podstromy sú tiež stromy a platí pre nich tiež táto definícia)

Abstraktný dátový typ

ADT je taký popis dátového typu, ktorý je nezávislý od konkrétnej implementácie. Cieľom je zjednodušiť a hlavne sprehľadniť programy, ktoré pracujú s daným dátovým typom. ADT teda obsahuje metódy, ktoré by mali fungovať úplne rovnako bez ohľadu na konkrétnu implementáciu pomocou nejakej dátovej štruktúry. V spojitosti s ADT sa často spomína duck typing. Tento označuje taký programátorský štýl, pri ktorom sa nezisťuje typ objektu ale len metódy objektu, resp. sa používajú atribúty objektu („ak nejaký vták chodí ako kačica, pláva ako kačica a kváka ako kačica, tak potom je to kačica“).

Vymenujme základné metódy, ktoré charakterizujú štruktúru strom, teda ADT pre strom sa skladá z metód:

  • t.root() - vráti koreň stromu, resp. None, ak je strom prázdny
  • t.parent(n) - pre daný vrchol n stromu t vráti jeho predka
  • t.children(n) - pre daný vrchol stromu vráti postupnosť jeho potomkov
  • t.num_children(n) - pre daný vrchol stromu zistí počet jeho potomkov
  • len(t) - zistí počet všetkých vrcholov stromu (táto funkcia je definovaná ako metóda __len__)
  • t.data(n) - pre daný vrchol stromu vráti hodnotu vo vrchole
  • t.is_root(n) - pre daný vrchol stromu zistí, či je to koreň, teda pre koreň vráti True
  • t.is_leaf(n) - pre daný vrchol stromu zistí, či je to list, teda vráti True, ak vrchol nemá žiadnych potomkov
  • t.is_empty() - zistí, či je strom prázdny
  • t.__iter__() - vráti iterovateľný objekt všetkých vrcholov stromu
    • najčastejšie to bude generátorový objekt
    • vďaka tomu budeme môcť zapísať konštrukciu for vrchol in strom: ..., pomocou ktorej môžeme postupne (v nejakom poradí) navštíviť a spracovať každý vrchol stromu

Zapíšme to ako základnú (bázovú) abstraktnú triedu, z ktorej budeme ďalej odvádzať ďalšie triedy:

class Tree:
    def root(self):
        raise NotImplementedError()

    def parent(self, node):
        raise NotImplementedError()

    def children(self, node):
        raise NotImplementedError()

    def num_children(self, node):
        raise NotImplementedError()

    def __len__(self):
        raise NotImplementedError()

    def data(self, node):
        raise NotImplementedError()

    def is_root(self, node):
        return self.root() == node

    def is_leaf(self, node):
        return self.num_children(node) == 0

    def is_empty(self):
        return len(self) == 0

    def __iter__(self):
        raise NotImplementedError()

Zrejme, kým nepredefinujeme všetky abstraktné metódy (ktoré vyvolajú výnimku NotImplementedError), nemá zmysel vytvárať inštancie tejto triedy. Všimnite si, že nie všetky metódy sú abstraktné: niektoré sme vedeli zapísať pomocou ostatných, napr. metóda is_empty() je definovaná pomocou metódy __len__(), teda keď neskôr zadefinujeme __len__(), bude fungovať aj is_empty().

Takto by to fungovalo v poriadku, hoci inštancia triedy Tree by bola úplne nepoužiteľná. Až inštancie z odvodených tried, v ktorých všetky abstraktné metódy (obsahujú raise NotImplementedError()) sú prekryté konkrétnou realizáciou, budú mať nejaký zmysel. V praxi, hlavne pri väčších projektoch, sa zaužívala prax, v ktorej abstraktný dátový typ doplníme o špeciálnu kontrolu:

  • kým sa nerealizujú všetky abstraktné metódy, tak z takejto triedy nedovolí vytvoriť inštanciu
  • pri definovaní tejto našej abstraktnej triedy zapíšeme špeciálneho predka triedy: ABC, čím sa zabezpečí samotná kontrola
  • okrem toho každú abstraktnú metódu označíme popisom (tzv. dekorátorom) @abstractmethod, aby kontrola vedela zistiť, ktoré metódy má strážiť, aby neostali abstraktné
  • obe označenia ABC a abstractmethod sú definované v štandardnom module abc (čo znamená modul abstract base classes)

Prepíšme abstraktný dátový typ Tree s využitím modulu abc:

from abc import ABC, abstractmethod

class Tree(ABC):

    @abstractmethod
    def root(self):
        pass

    @abstractmethod
    def parent(self, node):
        pass

    @abstractmethod
    def children(self, node):
        pass

    @abstractmethod
    def num_children(self, node):
        pass

    @abstractmethod
    def __len__(self):
        pass

    @abstractmethod
    def data(self, node):
        pass

    def is_root(self, node):
        return self.root() == node

    def is_leaf(self, node):
        return self.num_children(node) == 0

    def is_empty(self):
        return len(self) == 0

    @abstractmethod
    def __iter__(self):
        pass

Keď sa teraz pokúsime vytvoriť inštanciu tejto triedy, dostávame chybovú správu:

>>> t = Tree()
Traceback (most recent call last):
  File "<pyshell#0>", line 1, in <module>
    t = Tree()
TypeError: Can't instantiate abstract class Tree with abstract methods __iter__,
__len__, children, data, num_children, parent, root

Vidíme, že Python teraz stráži, vytváranie inštancie a vypisuje, ktoré abstraktné metódy treba ešte implementovať.

Hĺbka a výška

Do triedy Tree pridáme ešte dve ďalšie metódy, ktoré sú pre dátovú štruktúru veľmi dôležité:

  • hĺbka vrcholu (metóda depth):
    • vzdialenosť konkrétneho vrcholu od koreňa stromu
    • teda pre daný vrchol zistíme jeho predka, pre predka zistíme jeho predka a toto budeme opakovať, kým prídeme na vrchol, ktorý už predka nemá (otca) a počet týchto prechodov na predkov označuje vzdialenosť
    • zrejme koreň stromu má hĺbku 0
  • výška vrcholu, resp. celého stromu (metóda height):
    • vzdialenosť konkrétneho vrcholu od najvzdialenejšieho listu v tomto podstrome
    • teda budeme generovať všetky cesty od daného vrcholu ku všetkým listom a maximálna dĺžka cesty je výška vrcholu
    • výškou celého stromu rozumieme výšku koreňa stromu
    • zrejme všetky listy majú výšku 0

Obe tieto metódy pridáme do základnej triedy Tree:

class Tree(ABC):

    ...

    def depth(self, node):
        if self.is_root(node):
            return 0
        return 1 + self.depth(self.parent(node))

    def height(self, node=None):
        if node is None:
            node = self.root()
        if node is None or self.is_leaf(node):
            return 0
        return 1 + max(self.height(n) for n in self.children(node))

Vďaka tomu, že obe tieto metódy využívajú len ďalšie metódy základnej triedy, môžeme ich definovať už na tejto úrovni a teda každá ďalšia implementácia stromu, ktorá vychádza z bázovej triedy Tree, má už zadefinované obe tieto nie až tak jednoduché metódy. Zložitosť oboch algoritmov pre hĺbku aj výšku stromu je O(n).

Výšku celého stromu by sme mohli počítať aj ako maximum hĺbok všetkých listov stromu:

class Tree(ABC):

    ...

    def height1(self):
        return max(self.depth(v) for v in self if self.is_leaf(v))

Tento algoritmus je veľmi neefektívny: O(n**2)

  • zápis for v in self zavolá metódu strom.__iter__(), t. j. postupne vygeneruje všetky vrcholy stromu (predpokladáme, že jeho zložitosť je O(n)

Binárne stromy

vlastnosti:

  • každý vrchol má maximálne dvoch potomkov (synov), pričom sú pomenované ako ľavý a pravý syn
  • v zozname potomkov (metóda children()) je uvedený najprv ľavý a potom pravý syn

rekurzívna definícia: binárny strom je buď prázdny alebo sa skladá z

  • koreňa, v ktorom je uložená nejaká informácia
  • binárneho stromu (možno prázdneho), ktorý sa volá ľavý podstrom
  • binárneho stromu (možno prázdneho), ktorý sa volá pravý podstrom

ďalšie metódy do ADT pre binárny strom:

  • t.left(node) - ľavý syn alebo None
  • t.right(node) - pravý syn alebo None
  • t.sibling(node) - súrodenec vrcholu alebo None

Teraz už vieme definovať aj metódu children() - metóda vráti zoznam všetkých synov vrcholu - zoznam môže byť prázdny, jednoprvkový alebo dvojprvkový.

Aj trieda BinaryTree ja abstraktný dátový typ, lebo tiež obsahuje abstraktné metódy (predpokladáme, že trieda Tree je definovaná v súbore tree.py):

from abc import abstractmethod
from tree import Tree

class BinaryTree(Tree):
    @abstractmethod
    def left(self, node):
        pass

    @abstractmethod
    def right(self, node):
        pass

    def sibling(self, node):
        parent = self.parent(node)
        if parent is None:
            return None
        if self.left(parent) == node:
            return self.right(parent)
        return self.left(parent)

    def children(self, node):
        res = []
        if self.left(node) is not None:
            res.append(self.left(node))
        if self.right(node) is not None:
            res.append(self.right(node))
        return res

    def num_children(self, node):
        count = 0
        if self.left(node) is not None:
            count += 1
        if self.right(node) is not None:
            count += 1
        return count

Metódu children() budeme neskôr ešte vylepšovať. To, že aj táto trieda je abstraktná vidíme po otestovaní:

>>> t = BinaryTree()
Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    t = BinaryTree()
TypeError: Can't instantiate abstract class BinaryTree with abstract methods __iter__,
__len__, data, left, parent, right, root

Vlastnosti binárnych stromov:

  • označme vrcholy stromu s rovnakou hĺbkou d ako úroveň d
  • v úrovni 0 je len koreň stromu
  • v úrovni u je maximálne 2**u vrcholov
  • ak n je počet všetkých vrcholov, l je počet listov, h je výška stromu, tak
    • h+1 <= n <= 2**(h+1)-1
    • 1 <= l <= 2**h
    • log(n+1)-1 <= h <= n-1

Implementovanie binárnych stromov

Najčastejšie sú to tieto dva spôsoby:

  • pomocou poľa/zoznamu:
    • koreň pole[0], i-ty vrchol má synov pole[2*i+1] a pole[2*i+2], ak pole[i] je None alebo i >= len(pole), taký vrchol v strome neexistuje
  • pomocou spájanej štruktúry:
    • každý vrchol stromu (trieda Node) má okrem atribútu data (samotný údaj vo vrchole) aj referencie na ďalšie vrcholy: parent, left a right

Ďalej budeme binárny strom implementovať pomocou spájanej štruktúry, trieda LinkedBinaryTree využíva definíciu BinaryTree:

from bintree import BinaryTree

class LinkedBinaryTree(BinaryTree):

    class Node:
        def __init__(self, data, parent=None, left=None, right=None):
            self._data = data
            self._parent = parent
            self._left = left
            self._right = right

    #----------------------------------

    def __init__(self):
        self._root = None
        self._size = 0

    def root(self):
        return self._root

    def parent(self, node):
        return node._parent

    def left(self, node):
        return node._left

    def right(self, node):
        return node._right

    def data(self, node):
        return node._data

    def __len__(self):
        return self._size

Všimnite si, že všetky atribúty tried Node aj LinkedBinaryTree, ktoré sú premenné, začínajú podčiarkovníkom. Týmto sa v Pythone zvyknú označovať atribúty, ktoré by sa nemali používať ako verejné (public). Hoci je na programátorovi, ako ich bude používať. Táto trieda je stále ešte abstraktná lebo chýba implementácia metódy __iter__(). Túto naprogramujeme neskôr, zatiaľ ju môžeme zapísať ako return self.

Ďalej zadefinujeme niekoľko pomocných metód, ktoré budú slúžiť na pridávanie vrcholov do existujúceho stromu na presné miesto:

  • add_root() vytvorí koreň prázdneho stromu, ak koreň už existoval, metóda vyvolá chybu
  • add_left() konkrétnemu vrcholu pridá ľavého syna, ak ľavý syn už existoval, metóda vyvolá chybu
  • add_right() konkrétnemu vrcholu pridá pravého syna, ak pravý syn už existoval, metóda vyvolá chybu
  • add_random() konkrétnemu vrcholu pridá ľavého alebo pravého syna, metóda sa rozhoduje náhodne
    • ak v náhodne vybranom smere, už príslušný syn existuje, metóda sa presunie na tohto syna a na ňom spustí add_random()

Pridáme metódy:

class LinkedBinaryTree(BinaryTree):

    ...

    def __iter__(self):
        return self

    def add_root(self, data):
        if self.root() is not None:
            raise ValueError()
        self._root = self.Node(data)
        self._size = 1
        return self._root

    def add_left(self, node, data):
        if self.left(node) is not None:
            raise ValueError()
        node._left = self.Node(data, node)   # node je pre tento vrchol otcom
        self._size += 1
        return node._left

    def add_right(self, node, data):
        if self.right(node) is not None:
            raise ValueError()
        node._right = self.Node(data, node)
        self._size += 1
        return node._right

    def add_random(self, node, data):
        if random.randrange(2):
            if self.left(node) is None:
                self.add_left(node, data)
            else:
                self.add_random(self.left(node), data)
        else:
            if self.right(node) is None:
                self.add_right(node, data)
            else:
                self.add_random(self.right(node), data)

Zložitosť všetkých základných operácií okrem depth() a height() je O(1). Už vieme, že zložitosť height() je O(n), zložitosť depth() je O(h), kde h je výška stromu.

Vytvorenie binárneho stromu, napr. takto:

t = LinkedBinaryTree()
k = t.add_root('koren')
p1 = t.add_left(k, 11)
p2 = t.add_right(k, 22)
t.add_left(p1, 33)
t.add_right(p1, 44)
t.add_left(p2, 55)
t.add_right(p2, 66)

alebo

t = LinkedBinaryTree()
k = t.add_root('koren')
for i in range(1000):
    t.add_random(k, i)
print('vyska =', t.height())

Prechádzanie vrcholov stromu

Už z prvého ročníka poznáme tieto základné algoritmy na prechádzanie binárneho stromu

  • preorder - najprv koreň, potom postupne všetky podstromy
  • postorder - najprv postupne všetky podstromy, potom koreň
  • breadth-first - do šírky, t. j. po úrovniach: najprv koreň, potom 1. úroveň, potom 2. úroveň, …
  • inorder - najprv ľavý podstrom, potom koreň a na záver postupne všetky zvyšné podstromy
    • väčšinou sa definuje iba pre binárne stromy

Preorder

Potrebujeme pomocnú rekurzívnu funkciu:

class LinkedBinaryTree(BinaryTree):

    ...

    def preorder(self):
        if not self.is_empty():
            self.subtree_preorder(self.root())
        print()

    def subtree_preorder(self, node):
        print(self.data(node), end=' ')
        for n in self.children(node):
            self.subtree_preorder(n)

To isté, ale pomocná funkcia je vnorená priamo do metódy preorder:

class LinkedBinaryTree(BinaryTree):

    ...

    def preorder(self):

        def subtree_preorder(node):
            print(self.data(node), end=' ')
            for n in self.children(node):
                subtree_preorder(n)

        if not self.is_empty():
            subtree_preorder(self.root())
        print()

Vidíme, že metóda preorder() nevyužíva nič z toho, že je určená iba pre binárny strom. Môžeme ju teda presunúť do abstraktnej triedy Tree a pritom ešte namiesto výpisu hodnôt vo vrcholoch budeme vytvárať zoznam vrcholov (referencií na vrcholy). Teraz bude použiteľná vo všetkých ďalších implementáciách.

class Tree(ABC):

    ...

    def preorder(self):

        def subtree_preorder(node):
            res.append(node)
            for n in self.children(node):
                subtree_preorder(n)

        res = []
        if not self.is_empty():
            subtree_preorder(self.root())
        return res

Postorder

Postorder zapíšme podobne ako preorder, ktorý vytvára zoznam vrcholov:

class Tree(ABC):

    ...

    def postorder(self):

        def subtree_postorder(node):
            for n in self.children(node):
                subtree_postorder(n)
            res.append(node)

        res = []
        if not self.is_empty():
            subtree_postorder(self.root())
        return res

Otestujeme: vytvorme testovací strom:

t = LinkedBinaryTree()
k = t.add_root('koren')
p1 = t.add_left(k, 11)
p2 = t.add_right(k, 22)
t.add_left(p1, 33)
t.add_right(p1, 44)
t.add_left(p2, 55)
t.add_right(p2, 66)

a výpis oboch postupností preorder a postorder:

print('preorder = ', end='')
for n in t.preorder():
    print(t.data(n), end=' ')
print()

print('postorder = ', end='')
for n in t.postorder():
    print(t.data(n), end=' ')
print()

Zamyslite sa ným, ako by ste zrealizovali metódu postorder() ako iterátor, čo znamená, že každé volanie next() vráti nasledovný prvok postupnosti postorder. Bez generátorov v nasledovnej časti by to bol programátorsky netriviálny problém.

Generátory a iterátory

V Pythone existuje zaujímavý spôsob ako generovať postupnosti. Najčastejšie sme to doteraz robili pomocou zoznamu, napr. generovanie všetkých deliteľov nejakého čísla:

def delitele(n):
    res = []
    for i in range(1, n + 1):
        if n % i == 0:
            res.append(i)
    return res

>>> delitele(100)
[1, 2, 4, 5, 10, 20, 25, 50, 100]

Pre postupnosti je základnou vlastnosťou to, aby boli iterovateľné, t. j. aby sa jeho prvky dali postupne prechádzať pomocou for-cyklu. Napr.

>>> for i in delitele(100):
        print(i, end=' ')

1 2 4 5 10 20 25 50 100

Teda nie je dôležité mať všetky prvky k dispozícii naraz v nejakej dátovej štruktúre, ale dôležité je ich postupne získavať vždy keď potrebujeme získať ďalší (teda vlastne niečo ako __iter__() a __next__()). Na toto využijeme nový mechanizmus generátorov - bude to ďalší spôsob vytvárania iterátora. Tieto sa podobajú na bežné funkcie ale namiesto return používajú príkaz yield. Generátory fungujú na takomto princípe:

  • keď takúto generátorovú funkciu zavoláme, nevytvorí sa ešte žiadna hodnota, ale vytvorí sa generátorový objekt (pri iterátoroch sme tomu hovorili iterátorový objekt)
  • keď si od generátorového objektu teraz vypýtame jednu hodnotu, dozvieme sa prvú z nich (slúži na to štandardná funkcia next())
  • každé ďalšie vypýtanie hodnoty (funkcia next()) nám odovzdá ďalšiu hodnotu postupnosti
  • keď už generátorový objekt nemá ďalšiu hodnotu, tak volanie funkcie next() vyvolá chybovú správu StopIteration

Samotná generátorová funkcia pri výskyte príkazu yield nekončí „len“ odovzdá jednu z hodnôt postupnosti a pokračuje ďalej. Funkcia končí až na príkaze return (alebo na konci funkcie) a vtedy automaticky vygeneruje chybu (exception) StopIteration. Samotné odovzdanie hodnoty (príkazom yield) preruší vykonávanie generátorovej funkcie s tým, že sa presne zapamätá miesto, kde sa bude pokračovať aj s momentálnym menným priestorom. Volanie next() pokračuje na tomto mieste, aby odovzdal ďalšiu hodnotu.

Zadefinujme funkciu delitele() ako generátor:

def delitele(n):
    for i in range(1, n+1):
        if n % i == 0:
            yield i

vytvoríme generátorový objekt:

>>> d = delitele(15)

premenná d je naozaj generátorový objekt, ktorý zatiaľ nevygeneroval žiadny prvok postupnosti:

>>> d
<generator object delitele at 0x0000000003042828>

keď chceme prvý prvok, zavoláme metódu next() rovnako ako pri iterátoroch:

>>> next(d)
1

každé ďalšie volanie next() vygeneruje ďalšie prvky:

>>> next(d)
3
>>> next(d)
5
>>> next(d)
15
>>> next(d)
...
StopIteration

Po poslednom prvku funkcia next() vyvolala výnimku StopIteration. Mohli by sme to zapísať aj pomocou for-cyklu:

>>> for i in delitele(15):
        print(i, end=' ')

1 3 5 15

Ukážky generátorových funkcií

  • postupnosť piatich hodnôt:

    def prvo():
        yield 2
        yield 3
        yield 5
        yield 7
        yield 11
    
    
    >>> list(prvo())
    [2, 3, 5, 7, 11]
    
  • to isté pomocou for-cyklu:

    def prvo():
        for i in [2, 3, 5, 7, 11]:
            yield i
    
    >>> list(prvo())
    [2, 3, 5, 7, 11]
    

For-cyklus v generátorových funkciách, ktorý generuje yield, môžeme skrátene zapísať aj pomocou verzie yield from:

  • to isté ako predchádzajúca verzia:

    def prvo():
        yield from [2, 3, 5, 7, 11]
    
    >>> list(prvo())
    [2, 3, 5, 7, 11]
    

Parametrom yield from môže byť ľubovoľný iterovateľný objekt nielen zoznam, napr. aj range() alebo aj iný generátorový objekt (napr. v rekurzívnych funkciách).

  • využitie range():

    def test(n):
         yield from range(n+1)
         yield from range(n-1, -1, -1)       # alebo reversed(range(n))
    
    >>> list(test(3))
    [0, 1, 2, 3, 2, 1, 0]
    >>> list(test(5))
    [0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
    
  • skoro to isté ale rekurzívne:

    def urob(n):
        if n < 1:
            yield 0
        else:
            yield n
            yield from urob(n-1)
            yield n
    
    >>> list(urob(3))
    [3, 2, 1, 0, 1, 2, 3]
    >>> list(urob(5))
    [5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5]
    
  • fibonacciho postupnosť:

    def fib(n):
        a, b = -1, 1
        while n > 0:
            a, b = b, a+b
            yield b
            n -= 1
    
    >>> list(fib(10))
    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    >>> for i in fib(10):
            print(i, end=' ')
    
    0 1 1 2 3 5 8 13 21 34
    

    ak by sme chceli z fibonacciho postupnosti vypísať len po prvý člen, ktorý je aspoň 10000 a my nevieme odhadnúť, koľko ich budeme potrebovať, zapíšeme napr.

    >>> for i in fib(10000):
            print(i, end=' ')
            if i > 10000:
                break
    
    0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
    

vďaka tomu, že fib() je generátor a nie funkcia, ktorá vytvára zoznam hodnôt, nebolo pre tento for-cyklus potrebné vyrobiť 10000 prvkov, ale len toľko, koľko ich bolo treba v cykle.

Generátorovým funkciám se niekedy hovorí lenivé vyhodnocovanie (lazy evaluation), lebo funkcia počíta ďalšiu hodnotu až keď je o ňu požiadaná (pomocou next()) - teda nič nepočíta zbytočne dopredu.

Generované zoznamy

už sme sa dávnejšie stretli so zápismi:

>>> zoznam = [i for i in range(20) if i%7 in [2,3,5]]
>>> zoznam
[2, 3, 5, 9, 10, 12, 16, 17, 19]
>>> mn = {i for i in range(20) if i%7 in [2,3,5]}
>>> mn
{2, 3, 5, 9, 10, 12, 16, 17, 19}
>>> ntica = tuple(i for i in range(20) if i%7 in [2,3,5])
>>> ntica
(2, 3, 5, 9, 10, 12, 16, 17, 19)

Podobne vieme vygenerovať nielen zoznam (list), množinu (set) a n-ticu (tuple), ale aj slovník (dict). Hovoríme tomu list comprehension (resp. iný typ) - po slovensky generované zoznamy (niekedy aj generátorový zápis alebo notácia). Všimnite si, že n-ticu musíme generovať pomocou funkcie tuple(), lebo inak:

>>> urob = (i for i in range(20) if i%7 in [2,3,5])
>>> urob
<generator object <genexpr> at 0x022A6760>
>>> list(urob)
[2, 3, 5, 9, 10, 12, 16, 17, 19]

dostávame generátorový objekt úplne rovnaký ako napr.

def gg():
    for i in range(20):
        if i%7 in [2,3,5]:
            yield i

>>> urob = gg()
>>> urob
<generator object gg at 0x022A6828>
>>> list(urob)
[2, 3, 5, 9, 10, 12, 16, 17, 19]

Takže jednoduché generátorové objekty môžeme vytvárať aj takto zjednodušene:

def gg(*zoznam):
    return (i for i in range(20) if i%7 in zoznam)

>>> urob = gg(2, 3, 5)
>>> urob
<generator object <genexpr> at 0x0229E8A0>
>>> list(urob)
[2, 3, 5, 9, 10, 12, 16, 17, 19]

Generátory pri stromoch

Najprv zmeňme metódu children() na generátorovú funkciu:

class BinaryTree(Tree):

    ...

    def children(self, node):
        if self.left(node) is not None:
            yield self.left(node)
        if self.right(node) is not None:
            yield self.right(node)

Teraz metódy, ktoré prechádzajú všetky vrcholy v nejakom poradí, teda preorder() a postorder():

class Tree(ABC):

    ...

    def preorder(self):

        def subtree_preorder(node):
            yield node
            for n in self.children(node):
                yield from subtree_preorder(n)

        if not self.is_empty():
            yield from subtree_preorder(self.root())

    def postorder(self):

        def subtree_postorder(node):
            for n in self.children(node):
                yield from subtree_postorder(n)
            yield node

        if not self.is_empty():
            yield from subtree_postorder(self.root())

Iterovanie stromu

V niektorých algoritmoch potrebujeme prechádzať všetky vrcholy stromu, ale je nám jedno v akom poradí (napr. ako sme to použili v metóde height1()). Vtedy využijeme takýto zápis:

for vrchol in strom:
    'spracuj vrchol'

takéto správanie funguje vďaka metóde __iter__(). Predchádzajúci zápis je vlastne:

for vrchol in strom.__iter__():
    'spracuj vrchol'

Od metódy sa očakáva, že bude generátorom. Keďže my už nejaké generátory hotové máme, môžeme jeden z nich využiť:

class Tree(ABC):

    ...

    def __iter__(self):
        yield from self.preorder()

v tomto konkrétnom prípade bude fungovať aj:

class Tree(ABC):

    ...

    def __iter__(self):
        return self.preorder()


Cvičenia

L.I.S.T.

  1. Vytvorte a otestujte tieto štyri verzie funkcie mocniny(n), ktorá
    • vráti postupnosť (list) druhých mocnín [1, 4, 9, 16, ..., n**2] vytvorenú pomocou for-cyklu a metódy append()
    • vráti postupnosť (list) ale vytvorené pomocou generátorovej notácie (napr. [... for i in ...])
    • túto postupnosť vráti ako generátorovú funkciu (použitím yield)
    • túto postupnosť vráti ako generátorovú funkciu (použitím generátorového zápisu (... for i in ...) bez yield)

  1. Zapíšte generátor float_range(zac, kon=None, krok=1), ktorý funguje podobne ako štandardná funkcia range(...), ale nielen s celými ale aj s desatinnými číslami (float).

    • napr.

      >>> g = float_range(3)
      >>> g
      <generator object float_range at 0x7f87e8d78e60>
      >>> list(g)
      [0, 1, 2]
      >>> list(float_range(1, 5, 0.5))
      [1, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5]
      >>> list(float_range(10, 0, -1.25))
      [10, 8.75, 7.5, 6.25, 5.0, 3.75, 2.5, 1.25]
      

  1. Zapíšte dve verzie funkcie map(funkcia, zoznam), ktorá vráti prvky zoznamu prerobené funkciou funkcia (podobne ako to robí štandardná funkcia map(), ale riešte to bez tejto funkcie)
    • výsledok vytvorte najprv ako zoznam (list)
    • potom výsledok ako generátor
    • otestujte, ako sa bude správať map(), ak druhým parametrom je nejaký generátor
    • porovnajte so štandardnou funkciou map()

  1. Zapíšte dve verzie funkcie filter(funkcia, zoznam), ktorá vráti len tie prvky zoznamu, pre ktoré je splnená logická funkcia
    • výsledok najprv ako zoznam (list)
    • výsledok ako generátor
    • otestujte, ako sa bude správať filter(), ak druhým parametrom je nejaký generátor
    • porovnajte so štandardnou funkciou filter()

  1. Zapíšte funkciu zdvoj(gen), ktorá vygeneruje každý prvok 2-krát za sebou - funkcia vráti generátor

    • vyskúšajte nielen s parametrom typu generátor, ale napr. aj so zoznamom alebo s reťazcom

      napr.

      >>> g = zdvoj(i**2 for i in range(1, 5))
      >>> g
      <generator object zdvoj at 0x022A6828>
      >>> list(g)
      [1, 1, 4, 4, 9, 9, 16, 16]
      >>> zdvoj('Python')
      ...
      >>> zdvoj([2, 3, 5])
      

  1. Zapíšte dve verzie funkcie spoj(gen1, gen2), ktorá vygeneruje (vráti ako generátor) najprv všetky prvky gen1 potom všetky prvky gen2

    • vyskúšajte nielen s parametrami typu generátor, ale napr. aj so zoznamami a reťazcami

    • zapíšte verziu funkcie spoj(*gen), v ktorej sa spája ľubovoľne veľa generátorov

      >>> g = spoj(iter(range(5)), iter(range(10, 0, -2)))
      >>> g
      <generator object spoj at 0x00A823C0>
      >>> print(*g)
      0 1 2 3 4 10 8 6 4 2
      >>> g = spoj(iter(range(5)), iter('ahoj'), iter(range(10, 0, -2)))
      >>> print(*g)
      0 1 2 3 4 a h o j 10 8 6 4 2
      

  1. Zapíšte tri verzie funkcie mix(gen1, gen2), ktorá generuje prvky na striedačku - ak v jednom skončí skôr, tak už berie len zvyšné druhého

    • najprv s pomocným zoznamom: prvý generátor najprv presype prvky do zoznamu, a potom počas prechodu druhým generátorom dáva aj prvky z pomocného zoznamu

    • bez pomocného zoznamu len pomocou štandardnej funkcie next()

    • porozmýšľajte nad verziou mix(*gen), v ktorej sa mixuje ľubovoľne veľa generátorov

      >>> print(*mix(iter('PYTHON'), iter(range(4)), iter('ahoj')))
      P 0 a Y 1 h T 2 o H 3 j O N
      

  1. Na prednáške sa postupne definovali triedy Tree, BinaryTree a LinkedBinaryTree. Zapíšte ich postupne do súborov a otestujte funkčnosť vygenerovaním náhodného stromu s 20 vrcholmi a vygenerovaním preorder() a postorder() (tieto dve metódy sú generátory definované v abstraktnej triede Tree).

    • v súbore tree.py (nezabudnite na metódy depth(), height() a generátorové verzie prefix() a postfix()):

      from abc import ...
      
      class Tree(...):
          ...
      
    • v súbore bintree.py (nezabudnite na generátorovú verziu metódy children()):

      from abc import ...
      from tree import ...
      
      class BinaryTree(...):
          ...
      
    • v súbore linkbintree.py (nezabudnite na metódy add_root(), metódy add_left(), …):

      from bintree import ...
      
      class LinkedBinaryTree(...):
          ...
      

  1. Zadefinujte ďalšie metódy ako generátory:

    • do triedy BinaryTree metódu inorder():

      class BinaryTree(Tree):
      
          def inorder(self):
              ...
      
    • do triedy Tree metódu breadth_first() (algoritmus do šírky):

      class Tree(...):
      
          def breadth_first(self):
              ...
      

      algoritmus „do šírky“ generuje vrcholy po úrovniach: najprv koreň, potom jeho synov, potom jeho vnukov, … (zrejme využijete nejaký svoj vlastný queue), napr.

      algoritmus breadthfirst(T):
          inicializuj queue Q s hodnotou T.root()
          while Q not empty:
              p = Q.dequeue()
              spracuj vrchol p (napr. yield)
              for vrchol in T.children(p):
                  Q.enqueue(vrchol)
      
    • obe metódy otestujte a porovnajte s výsledkami z preorder() a postorder()


  1. Zadefinujte ďalšiu metódu ako generátor:

    • do triedy Tree metódu all_paths():

      class Tree(...):
      
          def all_paths(self):
              ...
      
    • metóda vygeneruje všetky cesty od koreňa k listom - zrejme pre každý list jedna cesta

    • každú cestu vygenerujte ako postupnosť vrchlov (podobne ako napr. preorder) ako zoznam (pythonovsky list)

    • otestujte s nejakým konkrétnym stromom

    • zamyslite sa, akú hodnotu vráti a čo vypíše:

      >>> max(map(len, t.all_paths()))
      ???
      >>> print(*(t.data(n) for n in max(t.all_paths(), key=len)))
      ???
      

  1. Implementujte triedu ArrayBinaryTree, v ktorej na reprezentáciu binárneho stromu využijete zoznam hodnôt:

    • koreň je v nultom prvku zoznam[0]

    • i-ty prvok (ak existuje) má svojich synov: ľavý v zoznam[2*i+1], pravý v zoznam[2*i+2]

    • vrchol neexistuje, buď je jeho index >= len(zoznam), alebo jeho hodnota v zozname je None (predpokladáme, že hodnota vo vrchole je rôzna od None) - v týchto prípadoch metódy napr. left(), parent(), … vrátia None

    • parameter node v týchto metódach označuje index do tohto zoznamu (teda celé číslo)

    • naprogramujte všetky metódy:

      class ArrayBinaryTree(BinaryTree):
          def __init__(self):
              self.zoznam = []
              self._size = 0
      
          def root(self):
              ...
      
    • vašu implementáciu otestujte (mali by fungovať aj metódy preorder, postorder, inorder, height, depth)


  1. Napíšte metódu gener() pre binárny strom, ktorá prejde (vygeneruje) všetky prvky (v poradí preorder) ale bez rekurzie a zásobníka

    • môžete použiť „pravidlo pravej ruky“, keďže každý vrchol si eviduje aj svojho predka (parent)

      class BinaryTree(...):
          ...
      
          def gener(self):
              ...
      


1. Domáce zadanie

L.I.S.T.

Použite túto definíciu abstraktnej stromovej štruktúry. Nemá zmysel ju upravovať, lebo testovač použije práve túto verziu:

Abstraktná trieda Tree

from abc import ABC, abstractmethod

class Tree(ABC):

    @abstractmethod
    def root(self):
        pass

    @abstractmethod
    def parent(self, node):
        pass

    @abstractmethod
    def children(self, node):
        pass

    @abstractmethod
    def num_children(self, node):
        pass

    @abstractmethod
    def siblings(self, node):
        pass

    @abstractmethod
    def __len__(self):
        pass

    @abstractmethod
    def data(self, node):
        pass

    @abstractmethod
    def __iter__(self):
        pass

    def is_root(self, node):
        return self.root() == node

    def is_leaf(self, node):
        return self.num_children(node) == 0

    def is_empty(self):
        return len(self) == 0

    def depth(self, node):
        if self.is_root(node):
            return 0
        return 1 + self.depth(self.parent(node))

    def height(self, node=None):
        if node is None:
            node = self.root()
        if node is None or self.is_leaf(node):
            return 0
        return 1 + max(self.height(n) for n in self.children(node))

    @abstractmethod
    def preorder(self):
        pass

    @abstractmethod
    def postorder(self):
        pass

    @abstractmethod
    def breadthfirst(self):
        pass

    @abstractmethod
    def leaves(self):
        pass

Trieda ParentTree

Dodefinujte metódy do tejto triedy ParentTree:

from tree import Tree

class ParentTree(Tree):

    class Node:
        def __init__(self, data, parent=None):
            self._data = data
            self._parent = parent

    #----------------------------------

    def __init__(self):
        self._all = set()

    def add_node(self, data, parent=None):
        node = self.Node(data, parent)
        self._all.add(node)
        return node

    ...

V triede nedefinujte žiadne ďalšie atribúty okrem chýbajúcich metód. Všimnite si, že v každom vrchole stromu sa pamätá jediná referencia a to na predka (parent). V pomocnom atribúte _all si strom uchováva množinu všetkých svojich vrcholov. Metóda add_node je jediná, ktorá do tejto množiny niečo pridáva - nemeňte ju. Taktiež nemeňte podtriedu Node ani metódu __init__ v ParentTree.

Naprogramujte chýbajúce metódy tak, aby fungoval napr. tento test:

if __name__ == '__main__':
    t = ParentTree()
    r = t.add_node('a')
    v1 = t.add_node('b', r)
    v2 = t.add_node('c', v1)
    v3 = t.add_node('d', v1)
    v4 = t.add_node('e', r)
    v5 = t.add_node('f', v1)
    v6 = t.add_node('g', v5)
    v7 = t.add_node('h', v3)
    v8 = t.add_node('i', v4)
    v9 = t.add_node('j', v5)
    v10 = t.add_node('k', v4)
    v11 = t.add_node('l', v7)
    v12 = t.add_node('m', v7)

    print('preorder =', *(t.data(n) for n in t.preorder()))
    print('postorder =', *(t.data(n) for n in t.postorder()))
    print('breadthfirst =', *(t.data(n) for n in t.breadthfirst()))
    print('leaves =', *(t.data(n) for n in t.leaves()))
    print('iter =', *(t.data(n) for n in t))

    for node in t:
        print(t.data(node), t.height(node), t.depth(node), t.is_leaf(node))
preorder = a b c d h l m f g j e i k
postorder = c l m h d g j f b i k e a
breadthfirst = a b e c d f i k h g j l m
leaves = l m c g i j k
iter = l m a b c d e f g h i j k
l 0 4 True
m 0 4 True
a 4 0 False
b 3 1 False
c 0 2 True
d 2 2 False
e 1 1 False
f 1 2 False
g 0 3 True
h 1 3 False
i 0 2 True
j 0 3 True
k 0 2 True

Uvedomte si, že poradie vypisovaných vrcholov sa u vás môže trochu zmeniť.

Definíciu triedy ParentTree uložte do súboru riesenie1.py a na začiatok pridajte tieto tri komentárové riadky (s vašim menom a dátumom):

# 1. zadanie: tree
# autor: Alan Turing
# datum: 18.10.2018

Súbor riesenie1.py odovzdávajte na úlohový server L.I.S.T. najneskôr do 23:00 7. novembra. Môžete zaň získať 10 bodov.



© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.