27. Spájané zoznamy

Predchádzajúca prednáška sa venovala spájanej dátovej štruktúre, v ktorej mal každý prvok svojho nasledovníka (okrem posledného). Takejto štruktúre sme hovorili spájaný zoznam (linked list).

Zhrňme z minulej prednášky najdôležitejšie funkcie, ktoré pracujú so spájanými zoznamami. Používali sme túto deklaráciu triedy Vrchol:

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

Pre spájané zoznamy, ktoré sú poskladané z takýchto vrcholov Vrchol sme definovali niekoľko funkcií:

def vypis(zoznam):                      # vypíše prvky zoznamu
    while zoznam is not None:
        print(zoznam.data, end=' -> ')
        zoznam = zoznam.next
    print(None)

def vyrob(postupnost):                  # z prvkov danej postupnosti vytvorí nový zoznam
    zoz = None
    for hodnota in reversed(postupnost):
        zoz = Vrchol(hodnota, zoz)
    return zoz

def pocet(zoznam):                      # zistí počet prvkov zoznamu
    vysl = 0
    while zoznam is not None:
        vysl += 1
        zoznam = zoznam.next
    return vysl

def zisti(zoznam, hodnota):             # zistí, či je prvok v zozname
    while zoznam is not None:
        if zoznam.data == hodnota:
            return True
        zoznam = zoznam.next
    return False

def pridaj_zaciatok(zoz, hodnota):      # pridaj prvok na začiatok zoznamu
    return Vrchol(hodnota, zoz)

def pridaj_koniec(zoz, hodnota):        # pridaj prvok na koniec zoznamu
    if zoz is None:
        return Vrchol(hodnota)
    posledny = zoz
    while posledny.next is not None:
        posledny = posledny.next
    posledny.next = Vrchol(hodnota)
    return zoz

V podobnom duchu boli aj ďalšie funkcie, ktoré ste programovali na cvičeniach. Keď sa vytvára nejaká nová dátová štruktúra, veľmi často sa všetky funkcie zapuzdria do jedného celku - do jednej triedy, pričom sa skryjú realizačné detaily a aj nejaké pomocné funkcie a atribúty (hovoríme tomu enkapsulácia).

Trieda spájaný zoznam

Navrhneme novú triedu SpajanyZoznam (v anglickej verzii by sme ju nazvali LinkedList), pre ktorú zadefinujeme najdôležitejšie metódy. Všimnite si, že definíciu pomocnej triedy Vrchol sme vnorili do triedy SpajanyZoznam. Tým, že sme definíciu tejto triedy vnorili, oznamujeme, že patrí do triedy SpajanyZoznam a zrejme sa bude využívať v metódach tejto triedy. Všetky funkcie, ktoré pracovali so spájaným zoznamom, mali prvý parameter referenciu na prvý prvok zoznamu. Teraz tento parameter zastúpi atribút zac, teda začiatok zoznamu. Už vieme, že si bude treba dať pozor, aby sme túto referenciu nepokazili. Tiež si všimnite, že funkciu vyrob(postupnost) sme zakomponovali priamo do inicializácie zoznamu:

class SpajanyZoznam:

    #----- vnorena trieda -----
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    #----- koniec vnorenej definicie triedy -----

    def __init__(self, postupnost=None):
        self.zac = None                   # začiatok zoznamu
        if postupnost is not None:
            for hodnota in reversed(postupnost):
                self.pridaj_zaciatok(hodnota)

    def vypis(self):                      # vypíše prvky zoznamu
        pom = self.zac
        while pom is not None:
            print(pom.data, end=' -> ')
            pom = pom.next
        print(None)

    def pocet(self):                      # zistí počet prvkov zoznamu
        vysl = 0
        pom = self.zac
        while pom is not None:
            vysl += 1
            pom = pom.next
        return vysl

    def zisti(self, hodnota):             # zistí, či je prvok v zozname
        pom = self.zac
        while pom is not None:
            if pom.data == hodnota:
                return True
            pom = pom.next
        return False

    def pridaj_zaciatok(self, hodnota):   # pridaj prvok na začiatok zoznamu
        self.zac = self.Vrchol(hodnota, self.zac)

    def pridaj_koniec(self, hodnota):     # pridaj prvok na koniec zoznamu
        if self.zac is None:
            self.zac = self.Vrchol(hodnota)
        pom = self.zac
        while pom.next is not None:
            pom = pom.next
        pom.next = self.Vrchol(hodnota)

Skôr ako to budeme testovať, všimnite si, že metódy pridaj_zaciatok() a pridaj_koniec() už nie sú také funkcie, ktoré vždy vracali novú referenciu na začiatok zoznamu - teraz túto referenciu už nepotrebujeme ako výsledok funkcie. Samotné metódy zmenia referenciu na začiatok v atribúte zac. Tiež vidíte použitie vnorenej triedy Vrchol: aby sme mohli vytvoriť nový vrchol, musíme zapísať self.Vrchol(hodnota). Zapíšme nejaký jednoduchý test, aby sme si zvykli na prácu s touto dátovou štruktúrou:

>>> zoz = SpajanyZoznam()
>>> zoz.pridaj_zaciatok(7)
>>> zoz.pridaj_koniec('abc')
>>> zoz.pridaj_zaciatok((1, 2))
>>> zoz.vypis()
(1, 2) -> 7 -> abc -> None
>>> zoz.pocet()
3
>>> zoz.zisti('abc')
True

Funguje to podľa očakávania dobre. Len by to mohlo byť viac pythonovské:

  • namiesto metódy vypis() by mohlo byť radšej __repr__() alebo __str__() a teda by fungovalo napr. print(zoz)

  • namiesto pocet() radšej __len__() a teda by fungovalo len(zoz)

  • namiesto pridaj_koniec() radšej append(), aby sa to podobalo pythonovskému pridávaniu na koniec pythonovského zoznamu

  • namiesto zisti() radšej __contains__() a teda by fungovalo hodnota in zoz

Budeme sa snažiť aj ďalšie metódy zapisovať tak, aby sa so spájaným zoznamom pracovalo podobne ako s inými dátovými typmi. Prepíšme triedu SpajanyZoznam:

class SpajanyZoznam:
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, postupnost=None):
        self.zac = None                   # začiatok zoznamu
        if postupnost is not None:
            for hodnota in reversed(postupnost):
                self.insert0(hodnota)

    def __repr__(self):
        vysl, pom = [], self.zac
        while pom is not None:
            vysl.append(repr(pom.data))
            pom = pom.next
        vysl.append('None')
        return ' -> '.join(vysl)

    def __len__(self):
        vysl, pom = 0, self.zac
        while pom is not None:
            vysl += 1
            pom = pom.next
        return vysl

    def __contains__(self, hodnota):
        pom = self.zac
        while pom is not None:
            if pom.data == hodnota:
                return True
            pom = pom.next
        return False

    def insert0(self, hodnota):
        self.zac = self.Vrchol(hodnota, self.zac)

    def append(self, hodnota):
        if self.zac is None:
            self.zac = self.Vrchol(hodnota)
        pom = self.zac
        while pom.next is not None:
            pom = pom.next
        pom.next = self.Vrchol(hodnota)

Pristavme sa na dvoch posledných metódach:

  • metóda insert0(), ktorá pridáva nový prvok na začiatok zoznamu, je veľmi rýchla, lebo obsahuje len jedno priradenie a bude trvať rovnaký čas bez ohľadu na to, či je doterajší zoznam krátky alebo obsahuje už veľa prvkov

  • metóda append(), ktorá pridáva nový prvok na koniec zoznamu, je v niektorých prípadoch veľmi pomalá: ak už doterajší zoznam obsahuje obrovské množstvo prvkov (napr. 100000), pridať nový prvok na koniec bude trvať už nejaký nezanedbateľný čas (napr. 0.01 sekundy); keď takéto pridávanie urobíme 1000 krát, už to môžu byť desiatky sekúnd.

Všimnite si, že v tejto metóde môže takto výrazne zdržovať len vnútorný while-cyklus. Ak by sme sa ho dokázali zbaviť, aj metóda append() by mohla byť dostatočne rýchla. Tento cyklus nerobí nič iné, len hľadá momentálne posledný vrchol v zozname. Ak by sme ale okrem referencie na začiatok zoznamu zabezpečili pamätanie aj referencie na posledný vrchol, všetko by sa vyriešilo.

Do triedy SpajanyZoznam k atribútu zac pridáme ďalší: kon, v ktorom si budeme ukladať referenciu na posledný vrchol zoznamu. Počiatočnú hodnotu (None) mu priradíme v inicializácii __init__(). Ďalej vo všetkých metódach, ktoré nejako modifikujú samotný spájaný zoznam, zabezpečíme, aby sa správne nastavila aj táto koncová referencia. V našom programe sa okrem inicializácie a metódy append() musí opraviť aj metóda insert0():

class SpajanyZoznam:
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, postupnost=None):
        self.zac = self.kon = None                   # začiatok a koniec zoznamu
        if postupnost is not None:
            for hodnota in postupnost:
                self.append(hodnota)

    ...

    def insert0(self, hodnota):
        self.zac = self.Vrchol(hodnota, self.zac)
        if self.kon is None:
            self.kon = self.zac

    def append(self, hodnota):
        if self.zac is None:
            self.kon = self.zac = self.Vrchol(hodnota)
        else:
            self.kon.next = self.Vrchol(hodnota)
            self.kon = self.kon.next

V tejto novej verzii v metóde append() už nie je žiaden cyklus a obsahuje len jeden test a niekoľko priradení. Môžete otestovať rýchlosť tejto metódy napr. takto:

>>> zoz = SpajanyZoznam(range(100000))
>>> for i in range(100000):
        zoz.append(i)
>>> len(zoz)
200000

Doplňme do tejto triedy SpajanyZoznam aj metódy pop0() a pop(), ktoré vyhodia 1. prvok, resp. posledný prvok zoznamu a vrátia príslušnú hodnotu vyhadzovaného prvku (podobne, ako to robia metódy list.pop(0) a list.pop()):

class SpajanyZoznam:
    ...

    def pop0(self):
        if self.zac is None:
            raise EmptyError
        vysl = self.zac.data
        self.zac = self.zac.next
        if self.zac is None:
            self.kon = None
        return vysl                   # hodnota vyhodeného prvku

    def pop(self):
        if self.zac is None:
            raise EmptyError
        if self.zac.next is None:     # jednoprvkový zoznam
            vysl = self.zac.data
            self.zac = self.kon = None
            return vysl
        self.kon = self.zac
        while self.kon.next.next is not None:
            self.kon = self.kon.next
        vysl = self.kon.next.data
        self.kon.next = None
        return vysl                   # hodnota vyhodeného prvku

Vidíme, že vyhodenie prvého prvku zoznamu (metóda pop0()) je veľmi jednoduché a rýchle (nezávisí od momentálnej veľkosti zoznamu). Metóda na vyhodenie posledného prvku je už náročnejšia a obsahuje while-cyklus na nájdenie predposledného vrcholu zoznamu. Preto je táto metóda veľmi pomalá a už nám tu nepomôže ani „finta“ s udržiavaním si referencie na posledný vrchol.

Otestujme:

>>> zoz = SpajanyZoznam(range(10000))
>>> for i in range(10000):
        x = zoz.pop()

Zhrňme základné metódy, ktoré pridávajú, resp. odoberajú prvok zo začiatku alebo konca zoznamu:

  • metóda insert0() vloží prvok na začiatok zoznamu - je veľmi rýchla

  • metóda append() vloží prvok na koniec zoznamu - je veľmi rýchla len ak využíva pomocnú referenciu na koniec zoznamu (inak je pomalá)

  • metóda pop0() vyberie prvok zo začiatku zoznamu - je veľmi rýchla

  • metóda pop() vyberie prvok z konca zoznamu - je veľmi pomalá a pre jednosmerný spájaný zoznam neexistuje spôsob, ako to urýchliť

Keď sa budete niekedy rozhodovať, ako budete pracovať s nejakým spájaným zoznamom, spomeňte si na toto porovnanie rýchlostí a ak sa bude dať, snažte sa vyhnúť odoberaniu prvku z konca zoznamu.

Mapovacie metódy

Zapíšme metódu, ktorá postupne prejde všetky vrcholy spájaného zoznamu a každému zmení hodnotu podľa zadanej funkcie:

class SpajanyZoznam:
    ...

    def mapuj(self, funkcia):
        pom = self.zac
        while pom is not None:
            pom.data = funkcia(pom.data)
            pom = pom.next

Otestujeme:

>>> def fun(x): return x * x
>>> zoz = SpajanyZoznam(range(5))
>>> zoz
0 -> 1 -> 2 -> 3 -> 4 -> None
>>> zoz.mapuj(fun)
>>> zoz
0 -> 1 -> 4 -> 9 -> 16 -> None

Funguje to aj s lambda konštrukciou, napr.

>>> zoz = SpajanyZoznam('Python')
>>> zoz
'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
>>> zoz.mapuj(lambda x: x.upper())
>>> zoz
'P' -> 'Y' -> 'T' -> 'H' -> 'O' -> 'N' -> None

Parametrom funkcie môže byť aj nejaká podmienka, napr. takáto verzia mapuj:

class SpajanyZoznam:
    ...

    def mapuj(self, podmienka, funkcia):
        pom = self.zac
        while pom is not None:
            if podmienka(pom.data):
                pom.data = funkcia(pom.data)
            pom = pom.next

napr.

>>> zoz = SpajanyZoznam(range(1, 20, 2))
>>> zoz
1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19 -> None
>>> zoz.mapuj(lambda x: x%3, lambda x: x*x)
>>> zoz
1 -> 3 -> 25 -> 49 -> 9 -> 121 -> 169 -> 15 -> 289 -> 361 -> None

Ďalšia metóda vytvorí obyčajný zoznam (typu list) prvkov z prvkov spájaného zoznamu, ktoré spĺňajú nejakú podmienku:

class SpajanyZoznam:
    ...

    def tolist(self, podmienka=None):
        lst = []
        pom = self.zac
        while pom is not None:
            if podmienka is None or podmienka(pom.data):
                lst.append(pom.data)
            pom = pom.next
        return lst

napr.

>>> zoz = SpajanyZoznam((1, 2, 'A', 4, 'B'))
>>> zoz.tolist(lambda x: isinstance(x, int))
[1, 2, 4]
>>> zoz.tolist()
[1, 2, 'A', 4, 'B']
>>> def podm(x): return type(x) == str
>>> zoz.tolist(podm)
['A', 'B']

Spájaný zoznam a for-cyklus

Už sme si zvykli, že prvky spájaného zoznamu môžeme prechádzať while cyklom, napr.

class SpajanyZoznam:
    ...

    def sucet(self):
        pom = self.zac
        vysl = 0
        while pom is not None:
            vysl += pom.data
            pom = pom.next
        return vysl

Žiaľ, prechádzať prvky spájaného zoznamu tak, ako to vie Python so zoznamom, n-ticou, množinou, atď. sa zatiaľ nedá. Ak by sme vyskúšali:

>>> zoz = SpajanyZoznam((2, 3, 5, 7, 11))
>>> for prvok in zoz:
        print(prvok)
...
TypeError: 'SpajanyZoznam' object is not iterable

alebo

>>> for prvok in zoz.zac:
        print(prvok.data)
...
TypeError: 'Vrchol' object is not iterable

Python vyhlási chybu TypeError, lebo nevie, akým spôsobom by mal postupne prechádzať (iterovať) všetky prvky spájaného zoznamu. Uvidíme, že Python to dokáže, ale bude potrebovať, aby sme mu niečo o našej štruktúre prezradili.

Rekurzia v metóde

Na predchádzajúcich cvičeniach ste zostavovali rekurzívnu funkciu (15. úloha), ktorá zisťovala počet prvkov spájaného zoznamu. Vaše riešenie mohlo vyzerať napr. takto:

def pocet(zoz):
    if zoz is None:
        return 0
    return pocet(zoz.next) + 1

Ak by sme túto rekurziu chceli zapísať ako metódu triedy SpajanyZoznam (problémom je parameter zoz), môžeme to urobiť niekoľkými spôsobmi. Najlepšie to ale urobíme ako vnorenú rekurzívnu funkciu do príslušnej metódy:

class SpajanyZoznam:
    ...

    def pocet(self):
        #----- vnorená funkcia
        def pocet_rek(zoz):
            if zoz is None:
                return 0
            return pocet_rek(zoz.next) + 1
        #----- koniec vnorenej funkcie

        return pocet_rek(self.zac)

Hoci táto rekurzívna funkcia nemá žiaden praktický význam (funguje len pre zoznamy kratšie ako 1000), ideu vnorených a hlavne rekurzívnych funkcií budeme neskôr používať veľmi často.

Realizácia zásobníka a radu

V prednáške 25. Zásobníky a rady sme sa zoznámili s dátovou štruktúrou zásobník. Využili sme ho hlavne pri spracovávaní aritmetických výrazov, ale aj ako mechanizmus, pomocou ktorého vieme nahradiť rekurziu zásobníkom.

Zásobník sme realizovali pomocou obyčajného zoznamu (typ list):

  • operácia push() pridávala nový prvok na koniec zoznamu pomocou metódy list.append()

  • operácia pop() odoberala zo zoznamu posledný prvok pomocou metódy list.pop()

  • operácia empty() zisťovala, či je zoznam prázdny

Zásobník sa dá veľmi elegantne realizovať aj pomocou spájaného zoznamu:

  • v tomto prípade bude vrch zásobníka na začiatku zoznamu

  • operácia push() pridá nový prvok na začiatok spájaného zoznamu

  • operácia pop() odoberie prvok zo začiatku spájaného zoznamu

  • operácia empty() zistí, či je spájaný zoznam prázdny

  • operácia top() vráti hodnotu prvého prvku spájaného zoznamu

  • opäť použijeme novú výnimku EmptyError

Zapíšme kompletný kód:

class EmptyError(Exception): pass

class Stack:
    class _Vrchol:                          # vnorená trieda
        def __init__(self, data, next):
            self.data, self.next = data, next

    def __init__(self):
        self._zac = None

    def push(self, hodnota):                # pridá na začiatok zoznamu
        self._zac = self._Vrchol(hodnota, self._zac)

    def pop(self):                          # odoberie zo začiatku zoznamu
        if self.empty():
            raise EmptyError
        vysl = self._zac.data
        self._zac = self._zac.next
        return vysl

    def top(self):                          # vráti hodnotu prvého prvku
        if self.empty():
            raise EmptyError
        return self._zac.data

    def empty(self):
        return self._zac is None

Vidíte, že táto trieda Stack je veľmi zjednodušená verzia triedy SpajanyZoznam. Mohli by sme ju použiť všade tam, kde sme doteraz pracovali so zásobníkom, ktorý bol realizovaný pomocou pythonovského zoznamu list.

Zamysite sa nad tým, ako by fungoval zásobník, ktorého vrch by bol na konci spájaného zoznamu (pridávame aj odoberáme prvky z konca spájaného zoznamu). Bol by rovnako rýchly ako táto verzia s vrchom zásobníka na začiatku spájaného zoznamu?

Realizácia radu (frontu)

V prednáške 25. Zásobníky a rady sme sa zoznámili aj s ďalšou dátovou štruktúrou rad. Aj rad sme realizovali pomocou obyčajného zoznamu (typ list):

  • operácia enqueue() pridávala nový prvok na koniec zoznamu pomocou metódy list.append()

  • operácia dequeue() odoberala zo zoznamu prvý prvok pomocou metódy list.pop(0)

  • operácia empty() zisťovala, či je zoznam prázdny

Pri realizovaní radu pomocou spájaného zoznamu sa musíme zamyslieť nad tým, či:

  1. bude začiatok radu na začiatku spájaného zoznamu

    • pridávať budeme na koniec zoznamu a odoberať budeme zo začiatku

  2. bude začiatok radu na konci spájaného zoznamu

    • pridávať budeme na začiatok zoznamu a odoberať budeme z konca

My už vieme, že pridávanie, resp. odoberanie zo začiatku spájaného zoznamu sú rýchle operácie. Ale pridávanie na koniec je rýchle len s pomocnou referencie na koniec zoznamu a odoberanie z konca je vždy pomalé. Preto si zvolíme variant (a), pri ktorom vieme rýchlo pridávať na koniec a rýchlo odoberať zo začiatku zoznamu:

  • operácia enqueue() pridá nový prvok na koniec spájaného zoznamu (použije referenciu na posledný vrchol zoznamu)

  • operácia dequeue() odoberie prvok zo začiatku spájaného zoznamu

  • operácia empty() zistí, či je spájaný zoznam prázdny

  • operácia front() vráti hodnotu prvého prvku spájaného zoznamu

  • opäť použijeme výnimku EmptyError

Zapíšme kompletný kód:

class EmptyError(Exception): pass

class Queue:
    class _Vrchol:                          # vnorená trieda
        def __init__(self, data):
            self.data, self.next = data, None

    def __init__(self):
        self._zac = self._kon = None

    def enqueue(self, hodnota):             # pridá na koniec zoznamu
        novy = self._Vrchol(hodnota)
        if self._zac is None:
            self._zac = self._kon = novy
        else:
            self._kon.next = novy
            self._kon = novy

    def dequeue(self):                      # odoberie zo začiatku zoznamu
        if self.empty():
            raise EmptyError
        vysl = self._zac.data
        self._zac = self._zac.next
        if self._zac is None:
            self._kon = None
        return vysl

    def front(self):                        # vráti hodnotu prvého prvku
        if self.empty():
            raise EmptyError
        return self._zac.data

    def empty(self):
        return self._zac is None

Vidíte, že aj trieda Queue je veľmi zjednodušená verzia triedy SpajanyZoznam.

Operátory indexovania

Pre pythonovský obyčajný zoznam (typ list) sú veľmi typické operácie indexovania, t.j. keď vieme zistiť hodnotu nejakého prvku podľa jeho indexu (pozície v zozname), resp. keď vieme zmeniť hodnotu prvku zadaného indexom. Zapíšme tieto dve operácie ako metódy triedy SpajanyZoznam:

class SpajanyZoznam:
    ...

    def _ity(self, index):                      # zistí referenciu i-teho prvku
        if index < 0:
            raise IndexError
        pom = self.zac
        while pom is not None and index > 0:
            pom = pom.next
            index -= 1
        if pom is None:
            raise IndexError
        return pom

    def daj_ity(self, index):                   # vráti hodnotu i-teho prvku
        return self._ity(index).data

    def zmen_ity(self, index, hodnota):         # zmení hodnotu i-teho prvku
        self._ity(index).data = hodnota

Vytvorili sme pomocnú (súkromnú) metódu _ity(), ktorá vráti referenciu na príslušný vrchol (alebo spadne na chybe IndexError). Opäť tu prvý znak mena _ označuje, že je to pomocná metóda, ktorú by sme radšej nemali používať mimo metód samotnej triedy.

Budeme to testovať takto - najprv si ukážme zápis pomocou obyčajného zoznamu list:

>>> lst = list(range(1, 20, 2))
>>> for i in range(len(lst)):
        lst[i] = lst[i] ** 2
>>> lst
[1, 9, 25, 49, 81, 121, 169, 225, 289, 361]

a prepíšeme to pre spájaný zoznam:

>>> zoz = SpajanyZoznam(range(1, 20, 2))
>>> for i in range(len(zoz)):
        zoz.zmen_ity(i, zoz.daj_ity(i) ** 2)
>>> zoz
1 -> 9 -> 25 -> 49 -> 81 -> 121 -> 169 -> 225 -> 289 -> 361 -> None

Vidíme, že v oboch prípadoch dostávame rovnakú postupnosť čísel, len zápis lst[i] = lst[i] ** 2 je výrazne lepšie čitateľný ako zoz.zmen_ity(i, zoz.daj_ity(i) ** 2).

Hodilo by sa nám, keby sme

  • namiesto volania zoz.daj_ity(i) mohli zapísať zoz[i] a Python by to pochopil ako vyhľadanie i-teho prvku zoznamu a vrátil by príslušnú hodnotu

  • namiesto volania zoz.zmen_ity(i, hodnota) mohli zapísať zoz[i] = hodnota a Python by to pochopil ako vyhľadanie i-teho prvku zoznamu a zmenu jeho hodnoty

Naozaj toto v Pythone funguje. Rovnako ako sme prekryli, teda preťažili (overload) operácie súčtu pomocou magickej metódy __add__(), ako sme preťažili operáciu in pomocou __contains__(), atď. môžeme preťažiť aj operácie indexovania. Funguje to takto:

  • keď v Pythone zapíšeme napr. lst[i], toto sa Pythonom prepíše na magické volanie lst.__getitem__(i) a až táto magická metóda vykoná výber hodnoty

  • keď v Pythone zapíšeme napr. lst[i] = hodnota, toto sa prepíše na magické volanie lst.__setitem__(i, hodnota) a až táto magická metóda vykoná zmenu hodnoty

  • keď v Pythone zapíšeme napr. del lst[i], toto sa prepíše na magické volanie lst.__delitem__(i) a až táto magická metóda vykoná zrušenie hodnoty

Môžete to otestovať na pythonovskom zozname list:

>>> lst = list(range(1, 20, 2))
>>> for i in range(len(lst)):
        lst.__setitem__(i, lst.__getitem__(i) ** 2)

Tomuto v programovacích jazykoch hovoríme syntaktický cukor a slúži len na uľahčenie zápisu a čitateľnosť kódu. Už sme sa s tým stretli pri aritmetických operáciách, keď a+b často označuje a.__add__(b).

Takže prepíšme naše dve metódy daj_ity() a zmen_ity() na magické __getitem__() a __setitem__():

class SpajanyZoznam:
    ...

    def _ity(self, index):                        # pomocná metóda
        if index < 0:
            raise IndexError
        pom = self.zac
        while pom is not None and index > 0:
            pom = pom.next
            index -= 1
        if pom is None:
            raise IndexError
        return pom

    def __getitem__(self, index):                 # vráti hodnotu i-teho prvku
        return self._ity(index).data

    def __setitem__(self, index, hodnota):        # zmení hodnotu i-teho prvku
        self._ity(index).data = hodnota

Samozrejme, že môžeme programy písať aj bez „syntaktického cukru“:

>>> zoz.__setitem__(i, zoz.__getitem__(i) ** 2)

ale určite čitateľnejšie to bude „osladené“:

>>> zoz[i] = zoz[i] ** 2

Treba si ale pri tomto zápise uvedomiť, že pre dlhé spájané zoznamy a pre veľký index toto nevinne vyzerajúce priradenie dvakrát prelieza spájaný zoznam, aby našiel (a zmenil) i-ty prvok. Už by sme si mohli pamätať, že napr. hľadanie posledného prvku v zozname môže naozaj trvať veľmi dlho.

Spájaný zoznam a for-cyklus

Python je pre programátora veľmi ústretový a snaží sa mu čo najviac vychádzať v ústrety. Keď zadefinujeme magickú metódu __getitem__(), Python z vlastnej iniciatívy „pochopí“, že takáto štruktúra by sa mohla dať prechádzať aj for-cyklom (iterovať). Veď zrejme mu stačí postupne indexovať s indexom 0, potom 1, potom 2, atď. až kým to nespadne na chybe a vtedy ukončí aj for-cyklus (bez chybovej správy). Otestujme:

>>> zoz = SpajanyZoznam(x**2 for x in range(1, 20, 2))
>>> for prvok in zoz:
        print(prvok, end=' -> ')
1 -> 9 -> 25 -> 49 -> 81 -> 121 -> 169 -> 225 -> 289 -> 361 ->

Teda to naozaj urobí presne to, čo sme očakávali. Ale pozor! Tento for-cyklus pre každý prvok zoznamu prelieza celý zoznam vždy od začiatku. Pre krátke zoznamy to asi vadiť nebude, ale pre dlhé to bude neprijateľne pomalé!

Na rovnakom princípe potom funguje aj rozbaľovací parameter, napr.

>>> print(*zoz)
1 9 25 49 81 121 169 225 289 361

A vy už teraz viete, že tento „syntaktický cukor“ za sebou skrýva veľmi neefektívny kód.

Dvojsmerný a cyklický spájaný zoznam

Zatiaľ sme sa zoznámili s tzv. jednosmerným spájaným zoznamom (Singly Linked List). Slovo „jednosmerný“ tu označuje, že v každom vrchole sa uchováva jedna referencia na nasledovný vrchol. Vďaka tejto vlastnosti, vždy keď potrebujeme zistiť predchodcu nejakého vrcholu (napr. predchodcu posledného), musíme prejsť zoznam od začiatku až po hľadaný vrchol. O tomto už vieme, že je to drahá operácia.

V situáciách, keď budeme často potrebovať pre nejaké vrcholy zisťovať ich predchodcov, využijeme alternatívnu organizáciu spájaných zoznamov, tzv. dvojsmerné spájané zoznamy (Doubly Linked List). Každý vrchol v takomto zozname si okrem referencie na nasledovníka uchováva aj referenciu na svojho predchodcu. A zrejme prvý vrchol má svojho predchodcu None (tak ako posledný svojho nasledovníka). Dvojsmerný spájaný zoznam by sme si mohli zakresliť, napr. takto:

sedemprvkový dvojsmerný spájaný zoznam

Zapíšme niekoľko metód:

class DvojsmernyZoznam:
    class Vrchol:
        def __init__(self, data, prev=None, next=None):
            self.data = data
            self.prev = prev
            self.next = next

    def __init__(self, postupnost):
        self.zac = self.kon = None
        for prvok in postupnost:
            self.append(prvok)

    def __repr__(self):
        vysl, pom = [], self.zac
        while pom is not None:
            vysl.append(repr(pom.data))
            pom = pom.next
        vysl.append('None')
        return ' <-> '.join(vysl)

    def insert0(self, hodnota):
        self.zac = self.Vrchol(hodnota, None, self.zac)
        if self.kon is None:
            self.kon = self.zac
        else:
            self.zac.next.prev = self.zac

    def append(self, hodnota):
        if self.zac is None:
            self.insert0(hodnota)
        else:
            novy = self.Vrchol(hodnota, self.kon)
            self.kon.next = novy
            self.kon = novy

V rámci cvičení si vyskúšate naprogramovať aj ďalšie metódy.

Cyklický spájaný zoznam

Spomenieme ešte jeden variant spájaných zoznamov, ktorý sa reálne využíva v niektorých špeciálnych situáciách. Cyklický spájaný zoznam (Circular Linked List) môže byť jednosmerný aj dvojsmerný - my sa tu budeme zaoberať len jednosmerným zoznamom. Označuje, že posledný vrchol v zozname nemá svojho nasledovníka označeného ako None ale nejaký iný vrchol v zozname. Najčastejšie to býva práve prvý vrchol zoznamu. Pri cyklickom zozname si musíte dať veľmi dobrý pozor na to, aby ste nevytvorili nekonečný cyklus. Cyklický spájaný zoznam by sme si mohli zakresliť, napr. takto:

sedemprvkový cyklický spájaný zoznam

Zapíšme na ukážku niekoľko metód:

class CyklickyZoznam:
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, postupnost=None):
        self.zac = self.kon = None
        if postupnost is not None:
            for hodnota in postupnost:
                self.append(hodnota)

    def __repr__(self):
        vysl, pom = [], self.zac
        while pom is not None:
            vysl.append(repr(pom.data))
            pom = pom.next
            if pom == self.zac:
                break
        vysl.append('...')
        return ' -> '.join(vysl)

    def __len__(self):
        vysl, pom = 0, self.zac
        while pom is not None:
            vysl += 1
            pom = pom.next
            if pom == self.zac:
                break
        return vysl

    def insert0(self, hodnota):
        if self.zac is None:
            self.zac = self.kon = self.Vrchol(hodnota)
            self.zac.next = self.zac
        else:
            self.kon.next = self.Vrchol(hodnota, self.zac)
            self.zac = self.kon.next

    def append(self, hodnota):
        if self.zac is None:
            self.insert0(hodnota)
        else:
            self.kon.next = self.Vrchol(hodnota, self.zac)
            self.kon = self.kon.next


Cvičenia

L.I.S.T.

  1. Poskladaj triedu SpajanyZoznam z prednášky s atribútmi zac a kon a s týmito metódami:

    • __repr__(), __len__(), __contains__(hodnota), insert0(hodnota), append(hodnota) (rýchla verzia), pop0() a pop()

    • najprv ručne bez počítača zisti, čo sa vypíše:

      zoz = SpajanyZoznam('python')
      for i in range(2):
          print(zoz.pop(), zoz.pop0())
      zoz.append('y')
      zoz.insert0('x')
      print(zoz)
      
    • potom to otestuj na počítači


  1. Metóda __len__ zisťuje veľkosť spájaného zoznamu pomocou while-cyklu (prechádza a počíta všetky prvky zoznamu). Prepíš túto metódu tak, aby neobsahovala cyklus. Zrejme v triede zadefinuješ ešte jeden atribút (počítadlo) a potom každá metóda, ktorá zvyšuje počet prvkov zoznamu (napr. append()) zvýši toto počítadlo o 1 a každá metóda, ktorá nejaké prvky zo zoznamu vyhadzuje (napr. pop()), zníži toto počítadlo.

    • otestuj napr.

      z = SpajanyZoznam(range(1000))
      for i in range(495):
          z.pop(); z.pop0()
      for i in range(5):
          z.append(i); z.insert0(i)
      print(len(z))
      
    • vedel by si ručne zistiť, aké prvky obsahuje výsledný 20-prvkový zoznam?

    • ak by si nemal túto rýchlu verziu __len__, nasledovný test by bežal veľmi dlho, otestuj:

      >>> zz = SpajanyZoznam()
      >>> pocet = 0
      >>> for i in range(100000):
              zz.insert0(i)
              pocet += len(zz)
      >>> pocet
      5000050000
      

  1. Len pomocou metód triedy SpajanyZoznam vymeň prvý a posledný prvok zoznamu

    • >>> zoz = SpajanyZoznam('PYTHON')
      >>> zoz
      'P' -> 'Y' -> 'T' -> 'H' -> 'O' -> 'N' -> None
      >>> ...
      >>> ...
      >>> ...
      >>> zoz
      'N' -> 'Y' -> 'T' -> 'H' -> 'O' -> 'P' -> None
      
    • tvoje riešenie by malo fungovať pre ľubovoľný spájaný zoznam, ktorý má aspoň 2 prvky

    • nepracuj priamo s atribútom zac


  1. Ručne bez počítača zisti čo robí nasledovná metóda corobi().

    • class SpajanyZoznam:
      
          ...
      
          def corobi(self):
              vysl = 0
              p = self.zac
              while p and p.next:
                  vysl += p.data == p.next.data
                  p = p.next
              return vysl
      
    • napr. by si mohol dostať takýto výstup:

      >>> z = SpajanyZoznam('abbacccaab')
      >>> print(z.corobi())
      4
      >>> z = SpajanyZoznam([abs(x%3-1) for x in range(100)])
      >>> print(z.corobi())
      33
      

  1. Do triedy SpajanyZoznam pridaj metódu clear(vzor=[0]), ktorá nahradí hodnoty v spájanom zozname prvkami postupnosti vzor. Tieto prvky berie z postupnosti postupne a keď sa minú, začne z nich brať od začiatku.

    • malo by fungovať napr. aj

      >>> zoz = SpajanyZoznam('pocitac')
      >>> zoz.clear()
      >>> zoz
      0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> None
      >>> zoz.clear('ab')
      >>> zoz
      'a' -> 'b' -> 'a' -> 'b' -> 'a' -> 'b' -> 'a' -> None
      >>> zoz.clear((1, 'a', 3.14))
      >>> zoz
      1 -> 'a' -> 3.14 -> 1 -> 'a' -> 3.14 -> 1 -> None
      >>> zoz.clear(range(1, 4))
      >>> zoz
      1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> None
      
  2. Do triedy SpajanyZoznam zapíš metódu count(hodnota), ktorá zistí počet výskytov nejakej hodnoty v spájanom zozname. Ak je niektorým prvkom zoznamu pythonovský list alebo tuple, bude počítať výskyty aj v týchto štruktúrach.

    • napr.

      >>> zoz = SpajanyZoznam((2, 5, 8, 6, 4, 5, 7, 6, 5, 2))
      >>> zoz.count(5)
      3
      >>> zoz.count(3)
      0
      >>> zoz = SpajanyZoznam((2, 5, 8, (6, 4, 5), [7, 6, 5], 2))
      >>> zoz.count(5)
      3
      

  1. Do triedy SpajanyZoznam dopíš metódy, ktoré vždy vrátia (return) nový SpajanyZoznam a pôvodný zoznam nechajú bez zmeny.

    • metóda copy() vráti presnú kópiu pôvodného zoznamu

    • metóda reversed() vráti prevrátenú kópiu pôvodného zoznamu

    • metóda filter(podmienka) vráti kópiu pôvodného zoznamu, ale len tie prvky, ktoré spĺňanú danú podmienku (parameter podmienka je logická funkcia)

    • metóda map(funkcia) vráti kópiu pôvodného zoznamu, ale na každý prvok aplikuje danú funkciu (parameter funkcia je nejaká funkcia, s jedným parametrom, napr. str)

    • metóda enumerate() vráti kópiu pôvodného zoznamu, ale z každého prvku vyrobí dvojicu (tuple), v ktorej prvým prvkom bude poradové číslo (od 0) a druhým prvkom bude samotná hodnota vo vrchole, malo by to fungovať podobne ako štandardná funkcia enumerate()

    • napr.

      >>> z = SpajanyZoznam('Python')
      >>> z
      'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
      >>> z1 = z.copy()
      >>> z1
      'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
      >>> z2 = z.reversed()
      >>> z2
      'n' -> 'o' -> 'h' -> 't' -> 'y' -> 'P' -> None
      >>> z3 = z.filter(lambda x: x in 'aeiouy')
      >>> z3
      'y' -> 'o' -> None
      >>> z4 = z.map(lambda x: x.upper()+'!')
      >>> z4
      'P!' -> 'Y!' -> 'T!' -> 'H!' -> 'O!' -> 'N!' -> None
      >>> z5 = z.enumerate()
      >>> z5
      (0, 'P') -> (1, 'y') -> (2, 't') -> (3, 'h') -> (4, 'o') -> (5, 'n') -> None
      >>> z
      'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
      

  1. Inicializácia __init__ môže dostať ako parameter nejakú postupnosť. Z tejto postupnosti potom pomocou reversed a insert0 poskladá samotný spájaný zoznam. Lenže pre niektoré postupnosti sa nedá urobiť reversed.

    • otestuj (pre nejaký textový súbor 'p.py'):

      with open('p.py') as subor:
          z = SpajanyZoznam(subor)
      
    • zrejme túto inicializáciu treba prepísať bez volania reversed, ale tak, aby vznikol správny spájaný zoznam, otestuj napr.

      with open('p.py') as subor:
          z = SpajanyZoznam(subor)
      while True:
          print(repr(z.pop0()))
      
    • tento program by po správnom vypísaní všetkých riadkov súboru mal spadnúť na chybe EmptyError


  1. Do triedy SpajanyZoznam dopíš magickú metódu __eq__(druhy), pomocou ktorej sa dajú porovnať dva zoznamy. Parametrom tejto metódy (okrem self) je druhý porovnávaný zoznam (objekt typu SpajanyZoznam). Python potom zo zápisu z1==z2 vyrobí volanie z1.__eq__(z2).

    • malo by teraz fungovať napr.

      >>> z1 = SpajanyZoznam(range(2, 7))
      >>> z2 = SpajanyZoznam((3, 4, 5, 6, 7))
      >>> z2.pop(); z2.insert0(2)
      7
      >>> z1 == z2
      True
      >>> z1.pop()
      6
      >>> z1 == z2
      False
      

  1. Doplň metódy __getitem__() a __setitem__() z prednášky.

    • odmeraj čas pre obe verzie zvyšovania hodnôt prvkov zoznamu o 1:

      >>> zoz1 = SpajanyZoznam(range(10000))
      >>> z = zoz1.zac
      >>> while z is not None:
              z.data += 1
              z = z.next
      >>> zoz2 = SpajanyZoznam(range(10000))
      >>> for i in range(len(zoz2)):
              zoz2[i] = zoz2[i] + 1
      
    • zamysli sa, prečo je rôzna rýchlosť pre vytvorenie týchto dvoch zoznamov l1 a l2:

      l1 = list(SpajanyZoznam(range(10000)))
      
      zoz = SpajanyZoznam(range(10000))
      l2 = []
      z = zoz.zac
      while z:
          l2.append(z.data)
          z = z.next
      print(l1 == l2)
      

  1. Metóda __delitem__(index) by mala umožniť vyhodiť zo zoznamu prvok s príslušným indexom. Dopíš ju do triedy SpajanyZoznam

    • teraz by malo fungovať, napr.

      >>> z = SpajanyZoznam(range(3, 22, 4))
      >>> z
      3 -> 7 -> 11 -> 15 -> 19 -> None
      >>> del z[2]
      >>> z
      3 -> 7 -> 15 -> 19 -> None
      

  1. Napíš metódu extend(), ktorá bude fungovať podobne ako metóda extend pre pythonovský zoznam list: parametrom je postupnosť alebo iný spájaný zoznam. Metóda pridá prvky postupnosti, resp. iného spájaného zoznamu na koniec pôvodného zoznamu. Metóda nič nevracia.

    • napr.

      >>> z = SpajanyZoznam(range(3, 8))
      >>> z.extend('hello')
      >>> z.extend(SpajanyZoznam([1, 'a', 3.14]))
      >>> z
      3 -> 4 -> 5 -> 6 -> 7 -> 'h' -> 'e' -> 'l' -> 'l' -> 'o' -> 1 -> 'a' -> 3.14 -> None
      

  1. Do triedy SpajanyZoznam dopíš magickú metódu __add__(druhy), vďaka ktorej sa budú dať veľmi elegantne zreťazovať spájané zoznamy podobne ako sa zreťazujú znakové reťazce. Parametrom tejto metódy (okrem self) je druhý spájaný zoznam (objekt typu SpajanyZoznam). Python potom zo zápisu z1+z2 vyrobí volanie z1.__add__(z2). Metóda teda vráti nový spájaný zoznam, ktorý vznikne spojením pôvodných dvoch zoznamov (tieto nepokazí).

    • otestuj:

      >>> z1 = SpajanyZoznam('abc')
      >>> z2 = SpajanyZoznam(range(2, 10, 2))
      >>> z3 = z1 + z2
      >>> z3
      'a' -> 'b' -> 'c' -> 2 -> 4 -> 6 -> 8 -> None
      >>> z1
      'a' -> 'b' -> 'c' -> None
      >>> z2
      2 -> 4 -> 6 -> 8 -> None
      >>> z2 + z1
      2 -> 4 -> 6 -> 8 -> 'a' -> 'b' -> 'c' -> None
      

  1. Zisti, čo sa stane so spájaným zoznamom

    • >>> z = SpajanyZoznam('abc')
      >>> z
      'a' -> 'b' -> 'c' -> None
      >>> z.zac.next.next.next = z.zac.next
      >>> z
      
    • ručne bez počítača zisti, čo sa vypíše:

      >>> p = z.zac
      >>> for i in range(10):
              print(p.data, end='')
              p = p.next
      

  1. Implementuj metódy tried Stack a Queue pomocou cyklického spájaného zoznamu: udržiavaj jedinú referenciu a to na posledný vrchol (jeho nasledovníkom je začiatok zoznamu)

    • otestuj rýchlosť práce s takýmito zásobníkmi a radmi v porovnaní s realizáciou pomocou obyčajného zoznamu (typ list)

    • najprv vytvor n prvkovú štruktúru (zásobník alebo rad) a potom z neho postupne všetky prvky vyberaj - testuj aj pre veľké n, napr. 100000



4. Domáce zadanie

L.I.S.T.

Napíšte modul s menom riesenie4.py, ktorý bude obsahovať jedinú triedu s ďalšou vnorenou podtriedou a týmito metódami:

class SpajanyZoznam2:
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, postupnost=None):
        self.zac = self.kon = None
        ...

    def append(self, hodnota):
        ...

    def count(self, hodnota):
        ...
        return 0

    def tolist(self):
        ...
        return []

    def totuple(self):
        ...
        return ()

Trieda SpajanyZoznam2 implementuje jednosmerný spájaný zoznam. Oproti podobnej triede z prednášky táto bude tie prvky, ktoré sú typu list alebo tuple, automaticky prerábať opäť na spájaný zoznam, t.j. na typ SpajanyZoznam2. Takže prvkami spájaného zoznamu môžu byť hodnoty ľubovoľných typov okrem list a tuple, pričom tieto budú nahradené spájanými zoznamami.

Metódy triedy SpajanyZoznam2 by mali mať takúto funkčnosť (môžete si dodefinovať aj ďalšie pomocné metódy):

  • metóda __init__() okrem inicializácie atribútov zac a kon pre referencie na začiatok a koniec zoznamu, bude inicializovať samotný zoznam hodnotami vstupnej postupnosti, použije na to metódu append();

  • metóda append() pridá na koniec zoznamu nový prvok, ak je táto hodnota typu list alebo tuple, tak z nej najprv urobí zoznam (typu SpajanyZoznam2) a až túto prerobenú hodnotu vloží na koniec zoznamu;

  • metóda count() zistí počet výskytov zadanej hodnoty v celom zozname, pričom, ak sú nejakými prvkami opäť spájané zoznamy, tak prvky počíta aj v týchto zoznamoch;

  • metóda tolist() vráti všetky prvky zoznamu ako obyčajný zoznam (typu list), ak je niektorým prvkom spájaný zoznam (typu SpajanyZoznam2), tak aj tento sa do výstupného zoznamu prerobí na typ list;

  • metóda totuple() vráti všetky prvky zoznamu ako pythonovskú n-ticu typu tuple, ak je niektorým prvkom spájaný zoznam, tak aj tento sa do výstupnej n-tice prerobí na typ tuple.

Obmedzenia

  • vaše riešenie odovzdajte v súbore riesenie4.py, pričom sa v ňom bude nachádzať len jedna definícia triedy SpajanyZoznam2, trieda Vrchol bude vnorená v triede SpajanyZoznam2

  • prvé tri riadky tohto súboru budú obsahovať:

    # 4. zadanie: spajany zoznam
    # autor: Janko Hrasko
    # datum: 17.3.2019
    
  • zrejme ako autora uvediete svoje meno

  • atribúty zac a kon v triede SpajanyZoznam2 musia obsahovať referencie na začiatok a koniec zoznamu

  • váš program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())

Testovanie

Keď budete spúšťať vaše riešenie na svojom počítači, môžete do súboru riesenie4.py pridať testovacie riadky, ktoré ale testovač vidieť nebude, napr.

if __name__ == '__main__':
    z1 = SpajanyZoznam2('abc')
    print(z1.totuple())
    data = [2, z1, 'xy', [0, 1], 1]
    z = SpajanyZoznam2(data)
    print(z.tolist())
    print(z.totuple())
    print(z.count(0), z.count(1), z.count(3))

Tento test by vám mal vypísať:

('a', 'b', 'c')
[2, ['a', 'b', 'c'], 'xy', [0, 1], 1]
(2, ('a', 'b', 'c'), 'xy', (0, 1), 1)
1 2 0

Projekt riesenie4.py odovzdávajte na úlohový server https://list.fmph.uniba.sk/ najneskôr do 23:00 27. marca. Za tento projekt môžete získať 10 bodov.