2. Polia, iterátory

Polia v počítači

V Pythone sú 3 sekvenčné typy, ktoré sú vnútorne reprezentované ako dynamické polia:

  • str - pole znakov - nemeniteľný typ (immutable)
  • tuple - pole referencií na objekty - nemeniteľný typ (immutable)
  • list - pole referencií na objekty - meniteľný typ (mutable)

Idea polí v počítači:

  • RAM (random access memory, pamäť s náhodným prístupom) - rovnaký čas na prístup k ľubovoľnému pamäťovému miestu na základe indexu = O(1) (na rozdiel od sekvenčného prístupu, keď O(1) je len pre nasledovníka, napr. spájané zoznamy, súbory, …)
  • prvky poľa sú postupne uložené v pamäťových miestach tak, aby sa dala čo najjednoduchšie vypočítať adresa ľubovoľného prvku
    • adresa A[i] = adresa začiatku A + i * počet_bajtov_prvku
  • typ str je v Pythone realizovaný ako kompaktné pole znakov - každý znak je v Unicode a pre celé pole je vyhradené buď 1 bajt na každý prvok, 2 bajty na prvok alebo 4 bajty (zrejme podľa prvku, ktorý zaberá najviac bajtov)
  • typy tuple a list sú poľami referencií na objekty (smerníky)

Môžeme si zjednodušiť pohľad na pamäť: všetky hodnoty, ktoré sú uložené v premenných (t.j. sú prístupné pomocou referencií v premenných), sa nachádzajú v jednom pamäťovom priestore. Tento priestor je vlastne jedno veľké pole pamäťových jednotiek rovnakej veľkosti (napr. bajtov = 8 bitov). Do takéhoto poľa sa potom ukladajú všetky hodnoty: aj celé čísla, ktoré môžu byť aj niekoľko 1000-bitové, aj desatinné, ktoré sú 64-bitové, aj znakové reťazce, ktoré môžu zaberať len niekoľko bajtov, ale aj milióny bajtov. Správca pamäti sa potom stará o to, aby táto pamäť bola čo najefektívnejšie využitá a pritom, aby sa s týmito hodnotami v pamäti pracovalo prijateľne rýchlo.

Problémom dynamických polí je to, že môžu veľmi často meniť svoju veľkosť a tým môžu veľmi zaťažovať správcu pamäte: ten musí nájsť dostatočne veľký súvislý úsek, do ktorého sa zmestí nová veľkosť takéhoto poľa. Zrejme bude potom treba aj zabezpečiť, aby sa pôvodný obsah poľa presunul na novú pozíciu.

Kompaktné pole v Pythone

Okrem typu str, ktorý je kompaktným poľom znakov (pole obsahuje priamo znaky a nie referencie na iné pamäťové miesta so znakmi), Python poskytuje možnosť vytvárať kompaktné pole aj iných typov. Tieto polia musia mať všetky prvky rovnakého (číselného) typu, aby sa mohol zabezpečiť RAM (náhodný) prístup k prvkom. Zrejme všetky prvky jedného poľa musia zaberať rovnaký počet bajtov.

Pythonovský modul array umožňuje definovať takéto kompaktné číselné pole (ktoré sa líši od poľa referencií na objekty čísla). Takto definované pole poskytuje komfort operácií a metód triedy list. Môže sa využiť napr. pri práci s binárnymi súbormi. Na tejto ukážke môžete vidieť jednoduché použitie kompaktných polí dvoch rôznych bajtových typov:

>>> import array
>>> a = array.array('b', [2,3,5,7,11,13,17,19])      # pole bajtov so znamienkom, t.j. hodnôt od -128 do 127
>>> a
array('b', [2, 3, 5, 7, 11, 13, 17, 19])
>>> a = a + a
>>> a
array('b', [2, 3, 5, 7, 11, 13, 17, 19, 2, 3, 5, 7, 11, 13, 17, 19])
>>> b = array.array('B', [1]*10)                     # pole bezznamienkových bajtov, t.j. hodnôt od 0 do 255
>>> b
array('B', [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
>>> for i in range(1, len(b)):
        b[i] = 2 * b[i-1]
...
OverflowError: unsigned byte integer is greater than maximum
>>> b
array('B', [1, 2, 4, 8, 16, 32, 64, 128, 1, 1])
>>>

Pri vytváraní kompaktného poľa (pomocou array.array()) musíme určiť konkrétny typ prvkov, na základe čoho sa bude dať vyhradiť súvislá pamäť 1-bajtových, 2-bajtových, alebo 4-bajtových, … čísel.

Definované typy pre kompaktné pole
kód C-typ Python-typ bajty  
'b' signed char int 1  
'B' unsigned char int 1  
'h' signed short int 2  
'H' unsigned short int 2  
'i' signed int int 2  
'I' unsigned int int 2  
'l' signed long int 4  
'L' unsigned long int 4  
'q' signed long long int 8  
'Q' unsigned long long int 8  
'f' float float 4  
'd' double float 8  

Dynamické pole a amortizácia

Zameriame sa na efektívnosť metódy append(), ktorá sa v Pythonovských algoritmoch využíva veľmi frekventovane, napr.

a = []
for i in range(1000000):
    a.append(i)

V tejto ukážke vidíme, že dané pole sa v cykle 1000000-krát zväčšuje stále o 1 prvok a teda aj správa pamäti musí nejako zabezpečiť, aby sa takéto pole mohlo stále nafukovať až dosiahne 1 milión prvkov. Zrejme dopredu netuší, aké veľké pole budeme potrebovať. Asi vám napadne, že stačí v pamäti len zväčšovať existujúci vyhradený priestor pre toto jedno pole, veď v programe sa so žiadnymi ďalšími údajmi nerobí, takže celá pamäť je k dispozícii na toto jediné pole. Lenže Python to dobre zvláda aj vtedy, keď bude pracovať napr. s dvoma poľami:

a, b = [], []
for i in range(1000000):
    a.append(i)
    b.append(i)

Asi za tým bude nejaký dobrý nápad, aby sa nemuselo sťahovať celé pole na novú pozíciu v pamäti pri každom volaní metódy append(). Pravdepodobne si Python vyhradí niekoľko prvkov do rezervy tak, aby nie po každom volaní append() musel robiť drahé upratovanie. Poďme teraz skúmať, koľko pamäti naozaj zaberá nejaká konkrétna dátová štruktúra. Využijeme funkciu getsizeof() z modulu sys, ktorá vráti počet bajtov, ktoré sú vyhradené pre nejakú hodnotu. Najprv poexperimentujme (je možné, že na vašom počítači dostanete trochu iné výsledky - závisí od toho, či máte 32 alebo 64 bitový systém, či máte Windows, alebo Linux, …):

>>> sys.getsizeof(1)
14
>>> sys.getsizeof(2**1000)
146
>>> sys.getsizeof(1.)
16
>>> sys.getsizeof(1e300)
16

Podľa veľkosti celého čísla sa vyhradzuje rôzne veľká pamäť. Desatinné čísla zaberajú stále rovnaký počet bajtov. Uvedomte si, že okrem samotnej hodnoty si Python musí pamätať aj nejaké ďalšie informácie, napr. konkrétny typ, momentálny rozsah (napr. aké veľké číslo sa sem zmestí), …

Podobne aj pre zložené typy:

>>> sys.getsizeof([])
36
>>> sys.getsizeof([1])
40
>>> sys.getsizeof([1, 2])
44
>>> sys.getsizeof([1, 2, 3])
48
>>> sys.getsizeof([1] * 100)
436
>>> sys.getsizeof('')
25
>>> sys.getsizeof('a')
26
>>> sys.getsizeof('aa')
27
>>> sys.getsizeof('a' * 100)
125

Môžeme tu odsledovať, že na mojom počítači je pre pole (typ list) vyhradená pamäť tak, že 36 bajtov je pre všeobecné informácie a 4 bajty (zrejme mám 32 bitový systém) na každý prvok poľa. Podobne je to so znakovými reťazcami, kde sa k číslu 25 pripočítava toľko bajtov, aký je počet prvkov. Zrejme sú zatiaľ všetky znaky v reťazci jednobajtové (ak by sme skladali reťazec, ktorý obsahuje napr. 'č', vyhradili by sa po 2 bajty na každý znak v reťazci).

Otestujme teraz, ako je to s metódou append():

import sys

def zisti(n):
    pole = []
    for i in range(n):
        size = sys.getsizeof(pole)
        print(f'len: {len(pole):3} sizeof: {size:5}')
        pole.append(None)

zisti(12)

Už vieme, že Python si pre list vyhradí vždy aj nejakú priestor pre základnú informáciu (36 bajtov) plus k tomu aj pamäť pre samotné prvky. Vidíme ale, že append() nezväčšuje vyhradenú pamäť o 1 prvok, ale vyhradí aj nejakú rezervu navyše:

len:   0 sizeof:    36
len:   1 sizeof:    52
len:   2 sizeof:    52
len:   3 sizeof:    52
len:   4 sizeof:    52
len:   5 sizeof:    68
len:   6 sizeof:    68
len:   7 sizeof:    68
len:   8 sizeof:    68
len:   9 sizeof:   100
len:  10 sizeof:   100
len:  11 sizeof:   100

Keďže každá referencia na hodnotu v poli zaberá u nás 4 bajty, upravíme testovací program tak, aby sme priamo videli, koľko prvkové pole sa momentálne vyhradilo. Tiež to upravíme tak, aby sme nevypisovali tie volania append(), ktoré nemenia vyhradenú pamäť:

import sys

def zisti(n):
    pole = []
    size0 = 0
    for i in range(n):
        size = sys.getsizeof(pole)
        if size != size0:
            size0 = size
            print(f'len: {len(pole):3} sizeof: {size:5} {(size-36)//4:3}')
        pole.append(None)

zisti(300)

Interval medzi nafukovaním poľa sa stále zväčšuje:

len:   0 sizeof:    36    0
len:   1 sizeof:    52    4
len:   5 sizeof:    68    8
len:   9 sizeof:   100   16
len:  17 sizeof:   136   25
len:  26 sizeof:   176   35
len:  36 sizeof:   220   46
len:  47 sizeof:   268   58
len:  59 sizeof:   324   72
len:  73 sizeof:   388   88
len:  89 sizeof:   460  106
len: 107 sizeof:   540  126
len: 127 sizeof:   628  148
len: 149 sizeof:   728  173
len: 174 sizeof:   840  201
len: 202 sizeof:   968  233
len: 234 sizeof:  1112  269
len: 270 sizeof:  1272  309

Python nielenže, nenafukuje pole pri každom volaní append(), ale nejako mení veľkosť nafukovanej časti.

Aby sme lepšie pochopili, ako to v Pythone funguje, definujme vlastné dynamické pole referencií na pythonovské objekty. Nebudeme pritom využívať štandardný typ list (ten chceme predsa naprogramovať) a tiež nevyužijeme žiadne kompaktné pole (array.array()) čísel - my potrebujeme pole referencií, t.j. pole smerníkov na ľubovoľné pythonovské hodnoty. Využijeme nízkoúrovňové (na úrovni jazyka C) definovanie poľa pomocou modulu ctype. Naprogramujeme aj metódu append(), v ktorej (ak bude treba) budeme naše pole nafukovať vždy o dvojnásobok jej momentálnej dĺžky:

import ctypes

class DynamickePole:
    def __init__(self):
        self.n = 0
        self.vyhr = 1
        self.pole = self.vyrob_pole(self.vyhr)

    def __len__(self):
        return self.n

    def __repr__(self):
        res = ''
        for i in range(self.n):
            res += ', ' + repr(self.pole[i])
        return 'dyn[' + res[2:] +']'

    def append(self, prvok):
        if self.n == self.vyhr:
            self.resize(2 * self.vyhr)
        self.pole[self.n] = prvok
        self.n += 1

    def resize(self, velkost):
        pole2 = self.vyrob_pole(velkost)
        for i in range(self.n):
            pole2[i] = self.pole[i]
        self.pole = pole2
        self.vyhr = velkost

    def vyrob_pole(self, d):
        return (d * ctypes.py_object)()

a = DynamickePole()
for i in range(20):
    a.append(i)
print(a)

po spustení:

dyn[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

otestujeme metódu append():

def zisti(n):
    pole = DynamickePole()
    size0 = 0
    for i in range(n):
        size = pole.vyhr
        if size != size0:
            size0 = size
            print(f'len: {len(pole):3} sizeof: {size:5}')
        pole.append(None)

zisti(300)

naozaj sa v prípade nutnosti veľkosť poľa zdvojnásobuje:

len:   0 sizeof:     1
len:   2 sizeof:     2
len:   3 sizeof:     4
len:   5 sizeof:     8
len:   9 sizeof:    16
len:  17 sizeof:    32
len:  33 sizeof:    64
len:  65 sizeof:   128
len: 129 sizeof:   256
len: 257 sizeof:   512

Vďaka tomuto mechanizmu má „priemerný“ čas operácie append() zložitosť O(1), hovoríme tomu amortizovaná zložitosť:

  • ak by sme zisťovali zložitosť metódy append() postupne pre prázdny zoznam, jednoprvkový, dvojprvkový, … až po n, a celkovú zložitosť (týchto n volaní append()) vydelíme n, dostaneme „priemernú“ zložitosť

  • v našej realizácii sa pole nafukuje len pri mocninách 2 a medzi tým je veľakrát zložitosť O(1) - jednu časovo náročnú operáciu, vieme rozložiť k rýchlym (pri rýchlych operáciách si vieme ušetriť toľko, aby sme si mohli raz začas dovoliť jednu časovo náročnú operáciu, splácame z našetreného - amortizujeme)

  • ak by sme nezdvojnásobovali veľkosť poľa ale ju len zväčšovali o konštantu, napr. 2, amortizovaná zložitosť bude O(n)

  • amortizovaná zložitosť O(1) bude aj vtedy, keď interval zväčšovania veľkosti poľa nebude konštantný ale nejaká geometrická postupnosť

  • ak by sme nakreslili graf, ako závisí čas každej jednej operácie append() v závislosti od veľkosti poľa, vyzeralo by to približne takto:

    |                   *
    |                   *
    |           *       *
    |           *       *
    |           *       *
    |           *       *
    |      *    *       *
    |      *    *       *
    |   *  *    *       *
    | * *  *    *       *
    |***********************************
    |___________________________________
    
    • teda zložitosť je skoro stále O(1) len veľmi zriedkakedy vyskočí dosť vysoko a závisí to od momentálneho n, lebo taký veľký úsek treba v pamäti vyhradiť a presťahovať sem starý obsah poľa
    • ak by sme ale všetky vyčnievajúce stĺpiky v tomto grafe sklopili do nasledujúcich stĺpcov (kde je momentálne po jednej hviezdičke), tak v každom stĺpci budú práve dve hviezdičky a teraz už nikde nič netrčí - vyzerá to, akoby v každom stĺpci (pre každé n) bolo priemerne O(2)
    • teraz je jasné, že ak by sme pole nezväčšovali so stále rastúcim prírastkom (dvojnásobok, alebo nejaký geometrický rad), nemohli by sme to takto ľahko spriemerovať a takýto append() by mal v konečnom dôsledku zložitosť O(n)

Otestujme, ako je to s časom pre pythonovskú metódu append():

import time

def priemer(n):
    pole = []
    start = time.time()
    for i in range(n):
        pole.append(None)
    cas = time.time() - start
    return cas * 1e6 / n

for n in 100, 1000, 10000, 100000, 1000000, 10000000, 100000000:
    print(f'{n:10} {priemer(n):10.5f}')

Zdá sa, že append v Pythone má (amortizovanú) zložitosť O(1) - dostávame skoro rovnaké výsledky:

      100      0.000
     1000      0.000
    10000      0.150
   100000      0.140
  1000000      0.175
 10000000      0.177
100000000      0.186

V testovacom programe sme nameraný čas ešte vynásobili konštantou 1000000. Inak by boli namerané čísla príliš malé a Python by to zaokrúhlil na 0. Takže vidíme, že jedno volanie append() trvá (na mojom počítači) priemerne 0.17 milióntiny sekundy.

Zložitosť pythonovských operácií na sekvenčných typoch

Operácie, ktoré nemenia obsah list, resp. tuple (sú immutable):

Zložitosť operácií
operácia zložitosť  
len(pole) O(1)  
pole[j] O(1)  
pole.count(obj) O(n)  
pole.index(obj) O(k+1)  
obj in pole O(k+1)  
pole1 == pole2 (tiež !=, <, <=, >, >=) O(k+1)  
pole[j:k] O(k-j+1)  
pole1 + pole2 O(n1+n2)  
c * pole O(cn)  

Operácie, ktoré menia obsah list (sú mutable):

Zložitosť operácií
operácia zložitosť  
pole[j] = obj O(1)  
pole.append(obj) O(1)*  
pole.insert(k, obj) O(n-k+1)*  
pole.pop() O(1)*  
pole.pop(k) O(n-k)*  
del pole[k] O(n-k)*  
pole.remove(obj) O(n)*  
pole1.extend(pole2) O(n2)*  
pole1 += pole2 O(n2)*  
pole.reverse() O(n)  
pole.sort() O(nlog n)  

(* amortizovaná, n2 označuje veľkosť pole2)

Z týchto dvoch tabuliek je vidieť, že pri práci s poľom sa oplatí rozmýšľať, ktoré operácie použijeme. Napr. ak by sme posledný testovací program volania metódy pole.append(None) zmenili na testovanie pole = pole + [None], dostali by sme približne takéto výsledky:

    100      0.000
   1000      3.000
  10000     23.103
 100000    229.964
1000000   4284.291

čo naznačuje, že už to nie je O(1) ale naskôr O(n)

Tiež si všimnite rozdiel medzi pole1 + pole2 a pole1 += pole2. Preto:

pole = pole + [x]     # zložitosť O(n)
pole += [x]           # zložitosť O(1)* amortizovaná

Znakové reťazce

Keďže znakové reťazce (typ str) sú v Pythone immutable, vždy sa konštruuje nový reťazec:

s1 = '... dlhý reťazec ...'
s2 = ''
for znak in s1:
    if 'A' <= znak <= 'z':
        s2 += znak

Zložitosť je O(n**2) lebo s2 sa stále zväčšuje o 1 znak a pritom sa stále kopíruje pôvodný reťazec do nového reťazca; jeho dĺžka (ktorá sa kopíruje) je postupne 1, 2, 3, …, n

Ak by sme využili pole a operáciu append():

s1 = '... dlhý reťazec ...'
pom = []
for znak in s1:
    if 'A' <= znak <= 'z':
        pom.append(znak)
s2 = ''.join(pom)

Dostávame zložitosť O(n). Samozrejme, že tvorcovia Pythonu o tomto probléme s rýchlosťou reťazcových operácií vedia, preto sú naprogramované v jazyku C čo najefektívnejšie. Takže, ak by sme merali reálnu rýchlosť oboch algoritmov, zistili by sme, že skutočná rýchlosť nemá s použitím polí až také zrýchlenie.

Aj prácu s reťazcami môžeme ešte urýchliť aj týmito zápismi:

s2 = ''.join([znak for znak in s1 if 'A' <= znak <= 'z'])

alebo ešte lepšie:

s2 = ''.join(znak for znak in s1 if 'A' <= znak <= 'z')

Iterovateľný typ

Už vieme, že v Pythone sú niektoré základné typy iterovateľné - môžeme prechádzať ich prvky napr. pomocou for cyklu:

  • list, tuple, str, dict, set
  • postupnosť celých čísel range(...), otvorený súbor na čítanie open(...)
  • výsledky funkcií map() a filter() aj generátorová notácia [... for ...]

Aj pre vlastný definovaný typ môžeme zabezpečiť iterovateľnosť. Možností je niekoľko, ukážeme dve z nich:

  • v triede zadefinujeme magickú metódu __getitem__(): v prípade prechádzania pomocou for-cyklu, Python zabezpečí postupné generovanie indexov od 0 vyššie a pri prvom neexistujúcom prvku, skončí
  • v triede zadefinujeme dvojicu magických metód __iter__() a __next__(), ktoré zabezpečia iterovateľnosť

Pozrime sa najprv na 2. spôsob vytvorenia iterovateľnosti a to pomocou štandardných funkcií iter() a next() (pomocou metód __iter__() a __next__() vieme zabezpečiť funkčnosť aj pre našu novú triedu). Aby sme lepšie pochopili ich princíp fungovania, vysvetlime, ako Python „vidí“ obyčajný for-cyklus. Python ho vnútorne realizuje pomocou while-cyklu a iterátora. Napr. takýto for-cyklus:

pole = [2, 3, 5, 7, 11, 13, 17]
for i in pole:
    print(i, i*i)

v skutočnosti Python realizuje pomocou iterátora približne takto:

iterator = iter(pole)
while True:
    try:
        i = next(iterator)
        print(i, i*i)
    except StopIteration:
        break

Funguje to takto:

  • Python si najprv z daného typu vyrobí špeciálny objekt (tzv. iterátor), pomocou ktorého bude neskôr postupne prechádzať všetky prvky
  • iterátor sa vytvára štandardnou funkciou iter(), ktorá by pre neiterovateľný typ spadla s chybovou hláškou
  • ďalšia štandardná funkcia next() z iterátora vráti nasledovnú hodnotu, alebo vyhlási chybu StopIteration, ak už ďalšia neexistuje

Môžete to vidieť aj na tomto príklade s iterovaním znakového reťazca:

>>> it = iter('ahoj')
>>> next(it)
'a'
>>> next(it)
'h'
>>> next(it)
'o'
>>> next(it)
'j'
>>> next(it)
...
StopIteration

Zadefinujme vlastnú triedu s metódou __getitem__():

class Moj:
    def __init__(self):
        self.p = []

    def append(self, x):
        self.p.append(x)

    def __getitem__(self, i):
        return self.p[i]

Otestujme:

>>> a = Moj()
>>> for i in 'Python':
        a.append(i)
>>> a
<__main__.Moj object at 0x02AD0F70>
>>> for i in a:
        print(i, end=' ')
P y t h o n
>>> len(a)
...
TypeError: object of type 'Moj' has no len()
>>> list(a)
['P', 'y', 't', 'h', 'o', 'n']
>>> len(list(a))
6

Ak v nejakej našej triede zadefinujeme metódy __iter__() a __next__(), tieto metódy sa automaticky zavolajú zo štandardných funkcií iter() a next(). Metóda __iter__() najčastejšie obsahuje vrátenie seba ako svojej hodnoty return self, lebo predpokladáme, že samotná inštancia je potom iterátor a teda tento iterátor musí obsahovať aj definíciu metódy __next__(). Táto druhá metóda sa automaticky zavolá pri volaní štandardnej funkcie next(). Preto musí metóda __next__() skontrolovať, či má ešte nasledovnú hodnotu (vtedy ju vráti) alebo vyvolá výnimku StopIteration.

Vyskúšajte:

class Moj2:
    def __init__(self):
        self.p = []

    def append(self, x):
        self.p.append(x)

    def __iter__(self):
        self.ix = 0
        return self

    def __next__(self):
        if self.ix >= len(self.p):
            raise StopIteration
        self.ix += 1
        return self.p[self.ix-1]

Otestujeme:

>>> a = Moj2()
>>> for i in 2, 3, 5, 7, 11:
              a.append(i)
>>> for i in a:
              print(i, end=', ')
2, 3, 5, 7, 11,
>>> print(*a)
2 3 5 7 11

Poznámka: táto verzia iterátora je veľmi zjednodušená a niekedy nepracuje úplne korektne. Napr. pre obyčajné polia funguje:

a = [2, 3, 5, 7, 11]
for i in a:
    for j in a:
        print(i, j)

sa vypíše 25 dvojíc čísel. Pre náš iterovateľný objekt:

a = Moj2()
for i in 2, 3, 5, 7, 11:
    a.append(i)
for i in a:
    for j in a:
        print(i, j)

sa vypíše len 5 dvojíc. Zamyslite sa nad tým, ako by sa to dalo opraviť.




Cvičenia

L.I.S.T.

  1. Upravte testovanie vyhradzovanej pamäti (funkcia zisti() z prednášky) pre pythonovský list.append() (kde sa sleduje, pri akých hodnotách sa nafukuje vnútorné pole)

    • funkciu upravte pre váš počítač (možno budete musieť zmeniť konštanty 36 a 4)

      def zisti(n):
          pole = []
          size0 = 0
          for i in range(n):
              size = sys.getsizeof(pole)
              if size != size0:
                  size0 = size
                  print(f'len: {len(pole):3} sizeof: {size:5} {(size-36)//4:3}')
              pole.append(None)
      
    • údaje vložte do excelovskej tabuľky a graficky znázornite priebeh funkcie, na základe ktorej Python určuje veľkosť pridávanej pamäti pri metóde append() aj pre väčšie polia


  1. V prednáške je aj príklad so spracovaním dlhého znakového reťazca

    • so zložitosťou O(n**2):

      s1 = '... dlhý reťazec ...'
      s2 = ''
      for znak in s1:
          if 'A' <= znak <= 'z':
              s2 += znak
      
    • pomocou pomocného poľa sa úloha rieši so zložitosťou O(n):

      s1 = '... dlhý reťazec ...'
      pom = []
      for znak in s1:
          if 'A' <= znak <= 'z':
              pom.append(znak)
      s2 = ''.join(pom)
      
      #s2 = ''.join([znak for znak in s1 if 'A' <= znak <= 'z'])
      #s2 = ''.join(znak for znak in s1 if 'A' <= znak <= 'z')
      
    • otestujte reálnu rýchlosť pre reťazce rôznych dĺžok (100000, 1000000, …, 10000000) - nezahrňte do tohto času načítanie (alebo vygenerovanie) reťazca

    • porovnajte všetky 3 rôzne rýchle verzie (ďalšie dve sú s generátorovou notáciou)


  1. V prednáške sme skúmali použitú pamäť (pomocou sys.getsizeof()) a rýchlosť metódy append() (amortizovaná zložitosť)

    • zistite, ako sa mení použitá pamäť a priemerný čas pre operáciu list.pop() (pop() bez parametra), skúmajte pre veľké polia

      import time
      
      def priemer(n):
          pole = [... veľké pole ...]
          start = time.time()
          ...
      

  1. Do triedy DynamickePole dodefinujte metódu pop() - navrhnite vlastnú stratégiu, kedy a o koľko sa bude pole zmenšovať (napr. vtedy, keď je vyhradená pamäť n využitá len na n/4, tak sa zmenší na n/2)

    • otestujte ju rovnakými testami ako v úlohe (3)

      class DynamickePole:
          ...
          def pop(self):
              ...
      

  1. Otestujte, či je trieda DynamickePole iterovateľná (či sa dajú vypísať prvky takéhoto poľa pomocou for-cyklu)

    • napr.

      pole = DynamickePole()
      pole.append(13)
      for i in pole:
          print(i)
      
    • pridajte metódu __getitem__() a otestujte iterovateľnosť:

      class DynamickePole:
          ...
          def __getitem__(self, index):
              ...
      
    • namiesto metódy __getitem__() pridajte metódy __iter__() a __next__() a otestujte iterovateľnosť:

      class DynamickePole:
          ...
          def __iter__(self):
              ...
          def __next__(self):
              ...
      

  1. Použite triedu spájaný zoznam z prvého ročníka:

    • zistite, či funguje napr. for data in Zoznam(range(10)):

      class Zoznam:
          class Vrchol:
              def __init__(self, data, next=None):
                  self.data, self.next = data, next
      
          def __init__(self, pole=None):
              self.zac = self.kon = None
              if pole is not None:
                  for data in pole:
                      self.pridaj_kon(data)
      
          def __repr__(self):
              z = self.zac
              vysl = '('
              while z is not None:
                  vysl += repr(z.data) + '->'
                  z = z.next
              return  vysl + ')'
      
          def __len__(self):
              z = self.zac
              vysl = 0
              while z is not None:
                  vysl += 1
                  z = z.next
              return vysl
      
          def pridaj_zac(self, data):
              self.zac = self.Vrchol(data, self.zac)
              if self.kon is None:
                  self.kon = self.zac
      
          def pridaj_kon(self, data):
              if self.zac is None:
                  self.zac = self.kon = self.Vrchol(data)
              else:
                  self.kon.next = self.Vrchol(data)
                  self.kon = self.kon.next
      
    • definujte __getitem__() a otestujte iterovateľnosť - odmerajte čas pre väčší spájaný zoznam, napr.

      zoz = Zoznam(range(10000))
      print('pocitam...')
      sucet = 0
      for p in zoz:
          sucet += p
      print(p)
      
    • namiesto __getitem__() definujte metódy __iter__() a __next__() tak, aby sa prvky zoznamu dali prechádzať for-cyklom, otestujte funkčnosť a porovnajte rýchlosť s predchádzajúcim testom

    • zdôvodnite výrazný rozdiel v čase behu oboch testov


  1. Naprogramujte tri rekurzívne verzie funkcie, ktorá počíta n-ty člen fibonacciho postupnosti (0,1,1,2,3,5,8,13,…):

    1. funkcia fib1(n), ktorá rekurzívne volá samu seba pre (n-1) aj pre (n-2) člen
    2. funkcia fib2(n), ktorá rekurzívne volá samu seba, ale vždy vracia dvojicu hodnôt (n-tý člen, n-1-člen), môže fungovať výrazne efektívnejšie ako fib1()
    3. funkcia fib3(n), ktorá pracuje skoro rovnako ako funkcia fib1(n), ale pamätá si v nejakej globálnej tabuľke všetky doterajšie vypočítané hodnoty a ak by nejakú mala znovu počítať, tak ju len vyberie z tabuľky; zrejme na začiatku je táto tabuľka prázdna a vždy keď nejakú ďalšiu hodnotu vypočíta, skôr ako ju vráti ako výsledok funkcie, zapamätá si ju aj v tabuľke
    • odhadnite zložitosť všetkých verzií, odmerajte beh aj pre väčšie n (asi fib1() na niektorých vstupoch už nepobeží)

  1. Zapíšte funkciu, ktorá zisťuje, či sú všetky prvky poľa navzájom rôzne (funkcia vráti True alebo False):

    • rôzne verzie funkcie:

      def zisti1(pole):
          '''pre každý prvok poľa prejde zvyšok poľa a hľadá, či sa tam nenachádza rovnaký'''
      
      def zisti2(pole):
          '''rekurzívne:
                 (1) zistí (rekurzívne), či sú všetky rôzne, ak sa vynechá prvý prvok
                 (2) potom zistí (rekurzívne), či sú všetky rôzne, ak sa vynechá len posledný prvok
                 ak platí (1) aj (2), ešte porovná prvý a posledný prvok'''
      
      def zisti3(pole):
          '''z poľa skonštruuje množinu a zistí či má táto rovnaký počet prvkov ako samotné pole
              - môžete predpokladať, že zložitosť vytvorenia množiny z n-prvkov je O(n)
          '''
      
    • odhadnite zložitosť a porovnajte rýchlosť všetkých troch algoritmov



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

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