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(repr(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).

Tieto funkcie môžeme ešte otestovať:

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

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 self.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:

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

    #----- koniec vnorenej definície 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(repr(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 self.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 mohlo fungova5, napríklad print(zoz)

  • namiesto pocet() by mohlo byť radšej __len__() a teda by vďaka tomu fungovalo nielen zoz.__len__() ale aj len(zoz)

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

  • namiesto zisti() by mohlo byť 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 (podobná list.insert(0, hodnota)), 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íklad 100000), pridať nový prvok na koniec bude trvať už nejaký nezanedbateľný čas (napríklad, 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íklad 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 vtedy, 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íklad:

>>> 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íklad 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íklad:

>>> 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ý pythonovský zoznam prvkov (typu list) 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íklad:

>>> 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íklad:

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 neskôr, ž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íklad 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 vtedy realizovali pomocou pythonovské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 is_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 is_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.is_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.is_empty():
            raise EmptyError
        return self._zac.data

    def is_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.

Zamyslite 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 is_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 is_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.is_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.is_empty():
            raise EmptyError
        return self._zac.data

    def is_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íklad 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íklad 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íklad 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íklad 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íklad:

>>> 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íklad 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íklad 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íklad 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()

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

    zoz = SpajanyZoznam('abcdefg')
    for i in range(2):
        print(zoz.pop(), zoz.pop0())
    zoz.append('x')
    zoz.insert0('y')
    print(zoz)
    

    Otestuj to 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íklad append()) zvýši toto počítadlo o 1 a každá metóda, ktorá nejaké prvky zo zoznamu vyhadzuje (napríklad pop()), zníži toto počítadlo. Otestuj, napríklad:

    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 bez počítača zistiť, aké prvky obsahuje tento 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(20000):
        zz.insert0(i)
        pocet += len(zz)
    print(pocet)
    
    200010000
    

  1. Len pomocou metód triedy SpajanyZoznam vymeň prvý a posledný prvok zoznamu (zrejme využiješ niektoré z metód append, insert0, pop, pop0). Napríklad:

    >>> 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. Samozrejme, že nebudeš pracovať 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íklad, po otestovaní, by si mohol dostať takýto výstup:

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

  1. Do triedy SpajanyZoznam pridaj metódu clear(vzor=[0]), ktorá nahradí hodnoty v spájanom zozname prvkami postupnosti vzor. Tieto prvky berie z neprázdnej postupnosti postupne a keď sa minú, začne z nich brať od začiatku. Postupnosťou by mohol byť zoznam, n-tica, reťazec alebo range. Malo by fungovať, napríklad aj toto:

    >>> 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(2, 6))
    >>> zoz
    2 -> 3 -> 4 -> 5 -> 2 -> 3 -> 4 -> None
    

  1. Do triedy SpajanyZoznam zapíš metódu count(retazec), ktorá zistí počet výskytov daného reťazca v spájanom zozname. Funkcia prehľadáva tie prvky spájaného zoznamu, ktoré sú reťazcami (iné ignoruje) a spočíta celkový počet výskytov vo všetkých prvkoch zoznamu. Napríklad:

    zoz = SpajanyZoznam('anicka dusicka kde si bola'.split())
    for r in 'a', 'ic', 'kde si':
        print(repr(r), zoz.count(r))
    print(SpajanyZoznam(('123', 232, '321', 433)).count('3'))
    
    'a' 4
    'ic' 2
    'kde si' 0
    2
    

  1. Do triedy SpajanyZoznam dopíš metódy, ktoré vždy vrátia (pomocou 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 tých prvkov, 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íklad str) - metóda sa podobá na funkciu mapuj z prednášky, ale teraz nemodifikuje samotný zoznam, ale vyrába kópiu

    • 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íklad:

    >>> 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. Do triedy SpajanyZoznam zapíš metódu opakuje_sa(), ktorá v danom zozname nájde taký prvok, ktorý sa tam opakuje aspoň raz. Rieš to dvomi vnorenými while-cyklami: postupne pre každý prvok zoznamu prejdeš celý zvyšok až do konca a hľadáš prvok s rovnakou hodnotou. Napríklad:

    a = SpajanyZoznam((*range(100), *range(90, 200)))
    print(a.opakuje_sa())
    b = SpajanyZoznam('mama ma emu a ema Ma mamu'.split())
    print(b.opakuje_sa())
    
    90
    None
    

  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íklad:

    >>> 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. Do triedy SpajanyZoznam doplň metódy __getitem__() a __setitem__() z prednášky. Potom odmeraj čas pre obe verzie zvyšovania hodnôt prvkov zoznamu o 1:

    import time
    
    start = time.time()
    zoz1 = SpajanyZoznam(range(10000))
    z = zoz1.zac
    while z is not None:
        z.data += 1
        z = z.next
    print(...)
    
    ...
    zoz2 = SpajanyZoznam(range(10000))
    for i in range(len(zoz2)):
        zoz2[i] = zoz2[i] + 1
    ...
    

    Prečo je taký veľký rozdiel v čase vytvárenia týchto zoznamov?

    Tiež sa zamysli, prečo je rôzna rýchlosť pre vytvorenie týchto dvoch pythonovských zoznamov list1 a list2:

    list1 = list(SpajanyZoznam(range(10000)))
    print('list1 hotovo')
    zoz = SpajanyZoznam(range(10000))
    list2 = []
    z = zoz.zac
    while z:
        list2.append(z.data)
        z = z.next
    print('list2 hotovo')
    print(list1 == list2)
    

  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íklad:

    >>> 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 (typu 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íklad:

    >>> 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(repr(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). Potom otestuj rýchlosť práce s takýmito zásobníkmi a radmi v porovnaní s realizáciou pomocou obyčajného pythonovského zoznamu (typ list):

    • najprv vytvor n prvkovú štruktúru (zásobník alebo rad)

    • potom z neho postupne vyberaj všetky prvky - testuj aj pre veľké n, napríklad 100000


4. Domáce zadanie

L.I.S.T.


Toto domáce zadanie bude riešiť takúto úlohu:

  • v súbore sa nachádzajú informácie o študentoch nejakej školy (osobné číslo, meno a priezvisko, zoznam udelených známok);

  • tento súbor treba prečítať a vytvoriť z neho jednosmerný spájaný zoznam (metoda citaj), v ktorom bude v každom vrchole informácia o jednom študentovi; vrcholy budú v spájanom zozname v tom poradí, v akom boli v súbore;

  • z tohto zoznamu budeme vedieť nájsť študenta (metóda __getitem__) podľa zadaného osobného čísla

  • tento zoznam bude treba vedieť zapísať späť do súboru (metóda zapis), ale v inom poradí:

    • metóda vyhod_min nájde študenta s najmenším osobným číslom, tento vrchol zo spájaného zoznamu odstráni a vráti ho ako výsledok funkcie

    • údaje tohto študenta zapíše v požadovanom formáte do súboru

    • toto opakuje, kým nebude spájaný zoznam prázdny

Formát súboru so študentmi nebude textový, ale binárny. To znamená, že informácie v ňom nie sú uložené ako postupnosti znakov a riadkov, ale ako postupnosti bajtov. Už vieme, že do jedného bajtu sa dá uložiť celé číslo od 0 do 255, pričom toto číslo môže obsahovať aj jeden znak ASCII kódu. Pre každého študenta bude v súbore postupnosť takýchto bajtov:

  • najprv 4 bajty s osobným číslom (osobné číslo je celé číslo z intervalu <0, 4294967295>, teda 256**4-1), kde najnižší bajt je prvý v štvorici, napríklad číslo 74565 bude v štyroch bajtoch ako (69, 35, 1, 0), alebo v šestnástkovej sústave ako (0x45, 0x23, 0x01, 0x00); pripomeň si úlohu 16. z cvičení k 24. prednáške

  • potom nasleduje postupnosť znakov (postupnosť bajtov s ASCII-kódmi, znaky nebudú obsahovať diakritiku), pričom prvý bajt postupnosti obsahuje dĺžku reťazca, napríklad meno a priezvisko 'Abc Def', bude uložené v 8 bajtoch: (7, 65, 98, 99, 32, 68, 101, 102), čo vieme zapísať aj v 16-ovej sústave: (0x07, 0x41, 0x62, 0x63, 0x20, 0x44, 0x65, 0x66); zrejme takéto reťazce môžu mať maximálnu dĺžku 255 znakov; ASCII-kódy znakov budú len z intervalu <32, 126>

  • na záver je to postupnosť známok v tvare čísel od 1 do 6, ktorá je ukončená číslom 0, pričom 1 zodpovedá známke A, 2 zodpovedá B, atď. až 6 zodpovedá Fx, 0 tu označuje koniec postupnosti a nereprezentuje známku, napríklad postupnosť (3, 1, 6, 4, 0) popisuje 4 známky (C, A, Fx, D); ak budeme niekedy potrebovať vypočítať priemer, tak použijeme prepočet, v ktorom známka A má hodnotu 1, známka B má hodnotu 1.5, známka C má hodnotu 2, atď. až známka Fx má hodnotu 4; potom priemer známok je (2+1+4+2.5)/4, teda 2.375

  • ak sa v súbore hneď na začiatku objaví táto postupnosť bajtov (zapísali sme ju v 16-ovej sústave):

    0x45, 0x23, 0x01, 0x00, 0x07, 0x41, 0x62, 0x63, 0x20, 0x44, 0x65, 0x66, 0x03, 0x01, 0x06, 0x04, 0x00
    

    týchto 17 bajtov reprezentuje informácie o jednom študentovi s osobným číslom 74565, s menom a priezviskom 'Abc Def' a so známkami (C, A, Fx, D); za týmito bajtami môže v súbore nasledovať ďalšia postupnosť bajtov, ktorá popisuje ďalšieho študenta

Binárny súbor

Binárny súbor je postupnosť bajtov. V Pythone budeme zapisovať do binárneho súboru a čítať z neho nie znakové reťazce, ale nový typ bytes. Tento typ je nemeniteľnou (immutable) postupnosťou bajtov, teda celých čísel z intervalu <0, 255>. V Pythone zapisujeme takéto postupnosti v tvare znakového reťazca, pred ktorým je prilepený znak b:

>>> b'+ A'                         # trojbajtová postupnosť
b'+ A'
>>> list(b'+ A')                   # tento zápis reprezentuje ASCII-hodnoty týchto znakov
[43, 32, 65]
>>> bytes((45, 49, 70, 100))       # postupnosť bajtov vieme skonštruovať aj zo zoznamu čísel
b'-1Fd'
>>> bytes()                        # prázdna postupnosť bajtov
b''
>>> bytes('Python', 'utf8')        # postupnosť bajtov vieme skonštruovať aj zo znakového reťazca
b'Python'                          # vtedy musíme uviesť aj kódovanie
>>> tuple(b'Python')
(80, 121, 116, 104, 111, 110)

Takto vidíme zobrazené bajty, ktoré majú v ASCII svoju reprezentáciu. Ak potrebujeme zadať bajt, ktorý nemá v ASCII svoje zobrazenie, použije sa zadávanie kódu bajtu v šestnástkovej sústave:

>>> b'A\x05B'                      # trojbajtová postupnosť
b'A\x05B'
>>> tuple(b'A\x05B')               # '\x05' označuje jeden bajt s hodnotou 5
(65, 5, 66)
>>> b = bytes(range(130, 250, 10)) # dvanásť bajtová postupnosť čísel
>>> b
b'\x82\x8c\x96\xa0\xaa\xb4\xbe\xc8\xd2\xdc\xe6\xf0'  # čísla sú v šestnástkovej sústave
>>> tuple(b)
(130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240)
>>> for i in b:                    # postupnosť vieme prechádzať for-cyklom
        print(i, end=' ')

130 140 150 160 170 180 190 200 210 220 230 240

S binárnym súborom pracujeme veľmi podobne ako s textovým. Zápis do súboru:

with open('subor.dat', 'wb') as subor:     # 'wb' označuje zápis do binárneho súboru
    subor.write(b'student')
    subor.write(bytes(range(10)))

Zapíše 17 bajtov, najprv 7 bajtov ASCII kodov reťazca 'student' a za tým 10 bajtov s hodnotami 0, 1, 2, …, 9.

Čítanie zo súboru:

with open('subor.dat', 'rb') as subor:     # 'rb' označuje čítanie z binárneho súboru
    prvy = subor.read(7)
    bajt = subor.read(1)
    druhy = b''
    while bajt != b'':                     # kým nie je koniec súboru
        druhy += bajt
        bajt = subor.read(1)

Tento program najprv prečíta prvých 7 bajtov do premennej prvy (zrejme bude obsahovať postupnosť b'student') a do premennej druhy prečíta zvyšné bajty súboru (zrejme b'\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09', čo sa môže zobraziť ako b'\x00\x01\x02\x03\x04\x05\x06\x07\x08\t'). Dalo by sa to zapísať aj takto jednoducho:

with open('subor.dat', 'rb') as subor:
    prvy = subor.read(7)               # prvých 7 bajtov
    druhy = subor.read()               # celý zvyšok súboru až do konca

Na stránke Bytes Objects v Pythonovom helpe si môžete prečítať ďalšie možnosti práce s týmto typom (napríklad, užitočnú metódu decode), ale užitočné môžu byť aj niektoré metódy s celočíselným typom (napríklad, to_bytes a from_bytes). Preštudujte si nasledovné ukážky:

  • ako prerobiť postupnosť bajtov (typ bytes) na obyčajný znakový reťazec (typ str):

    >>> bajty = b'Kovac Igor'
    >>> ''.join(chr(i) for i in bajty)   # pomocou chr pre každý bajt a potom join
    'Kovac Igor'
    >>> ''.join(map(chr, bajty))         # pomocou mapovania každého bajtu na znak a join
    'Kovac Igor'
    >>> bajty.decode()                   # pomocou metódy decode
    'Kovac Igor'
    
  • ako z celého čísla vyrobiť postupnosť štyroch bajtov (na začiatku je najnižší bajt):

    >>> cislo = 1234567
    >>> bajty = b''
    >>> for i in range(4):               # pomocou for-cyklu a postupným delením 256
            bajty += bytes((cislo%256,))
            cislo //= 256
    
    >>> bajty
    b'\x87\xd6\x12\x00'
    

    alebo pomocou metódy:

    >>> cislo = 1234567
    >>> cislo.to_bytes(4, 'little')   # parameter 'little' označuje, že začína najnižším bajtom
    b'\x87\xd6\x12\x00'
    
  • ako z postupnosti štyroch bajtov vyrobiť celé číslo:

    >>> bajty = b'\xb1\x7f\x39\x05'
    >>> cislo = 0
    >>> for bajt in reversed(bajty):
         cislo = cislo*256 + bajt
    
    >>> cislo
    87654321
    

    alebo pomocou metódy:

    >>> bajty = b'\xb1\x7f\x39\x05'
    >>> int.from_bytes(bajty, 'little') # parameter 'little' označuje, že začína najnižším bajtom
    87654321
    

Trieda SpajanyZoznam

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

class SpajanyZoznam:
    class Student:
        def __init__(self, cislo, meno, znamky):  # osobné číslo, meno a priezvisko, zoznam známok
            self.cislo = cislo                    # celé číslo z <0, 4294967295>
            self.meno = meno                      # znakový reťazec
            self.znamky = znamky                  # n-tica (tuple) celých čísel z <1, 6>
            self.next = None

        def __repr__(self):
            return f'Student({self.cislo}, {self.meno!r}, {self.znamky})'

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

    def citaj(self, meno_suboru):
        ...

    def zapis(self, meno_suboru):
        ...

    def vyhod_min(self):
        ...
        return ...

    def __getitem__(self, cislo):
        ...
        return None

    def __len__(self):
        ...
        return 0

Trieda SpajanyZoznam implementuje jednosmerný spájaný zoznam študentov, pričom metódy triedy by mali mať takúto funkčnosť (môžeš si dodefinovať aj ďalšie pomocné metódy):

  • metóda __init__() inicializuje atribúty zac a kon pre referencie na začiatok a koniec zoznamu;

  • metóda citaj(meno_suboru) otvorí binárny súbor a informácie o študentoch pridá na koniec momentálneho spájaného zoznamu; zrejme takto môže z viacerých súborov vyrobiť jeden spájaný zoznam;

  • metóda zapis(meno_suboru) zapíše kompletný spájaný zoznam do binárneho súboru; použije na to metódu vyhod_min, pomocou ktorej získa študenta s najmenším osobným číslom, študenta zapíše do súboru; ak túto metódu bude volať, kým nebude spájaný zoznam prázdny, zapíše do súboru všetkých študentov v usporiadanom poradí;

  • metóda vyhod_min() vyhľadá študenta s najmenším osobným číslom, tohto študenta vyhodí zo spájaného zoznamu a samotný vrchol (typu self.Student) vráti ako výsledok funkcie; ak bol zoznam už prázdny, funkcia vráti None;

  • metóda __getitem__(cislo) vráti informácie o študentovi s daným osobným číslom v tvare dvojice (meno, priemer), kde meno je znakový reťazec s menom a priezviskom študenta, priemer je priemer jeho známok; ak je zoznam študentových známok prázdny, jeho priemer je 0; ak študenta s daným osobným číslom nenajde, funkcia vráti None;

  • metóda __len__() vráti aktuálny počet prvkov zoznamu.

Obmedzenia

  • svoje riešenie odovzdaj v súbore riesenie.py, pričom sa v ňom bude nachádzať len jedna definícia triedy SpajanyZoznam, trieda Student bude vnorená v triede SpajanyZoznam

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

    # 4. zadanie: spajany zoznam a binarny subor
    # autor: Janko Hrasko
    # datum: 22.3.2020
    
  • zrejme ako autora uvedieš svoje meno

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

  • tvoj program by nemal počas testovania testovačom nič vypisovať (žiadne testovacie print())

Testovanie

Keď budeš spúšťať svoje riešenie na počítači, môžeš do súboru riesenie.py pridať testovacie riadky, ktoré ale testovač vidieť nebude, napríklad, ak subor1.dat obsahuje takúto postupnosť bajtov (zapísali sme ich v 16-ovej sústave a rozsekali sme ich tak, aby bolo lepšie vidieť informácie o štyroch študentoch):

4523010007416263204465660301060400
0004000007476820496A6B6C0200
B17F3905094D204E6F707172737400
87D61200075576777879205A0101010300

môžeme zapísať takýto test:

if __name__ == '__main__':
    zoz = SpajanyZoznam()
    zoz.citaj('subor1.dat')
    print('pocet =', len(zoz))
    p = zoz.zac
    while p:
        print(p)
        p = p.next
    for cislo in 74565, 87654321, 8765432:
        print(f'student[{cislo}] =', zoz[cislo])
    print('min =', zoz.vyhod_min())
    print('pocet po vyhod_min =', len(zoz))
    zoz.zapis('subor2.dat')
    print('pocet po zapise =', len(zoz))

Tento test by mal vypísať:

pocet = 4
Student(74565, 'Abc Def', (3, 1, 6, 4))
Student(1024, 'Gh Ijkl', (2,))
Student(87654321, 'M Nopqrst', ())
Student(1234567, 'Uvwxy Z', (1, 1, 1, 3))
student[74565] = ('Abc Def', 2.375)
student[87654321] = ('M Nopqrst', 0)
student[8765432] = None
min = Student(1024, 'Gh Ijkl', (2,))
pocet po vyhod_min = 3
pocet po zapise = 0

Projekt riesenie.py odovzdávaj na úlohový server https://list.fmph.uniba.sk/ najneskôr 3. apríla do 23:00. Za tento projekt môžeš získať 10 bodov.