previous up next hi end end

13. Rekurze a iterace

  1. Rekurzivní datové struktury
  2. Rekurze II
  3. Memoizace
  4. Iterátory
  5. Generátory
  6. Chyby a výjimky
  7. Glosář
  8. Cvičení

13.1 Rekurzivní datové struktury

Všechny dosud poznané datové typy mohou být v seznamech a enticích uspořádány přerůzným způsobem. Seznamy a entice mohou být také vnořené.

Povšimněme si, že termín seznam s vnořenými seznamy je použit ve své vlastní definici. Rekurzivní definice jako tato jsou zcela obvyklé v matematice a v programování. Poskytují stručný a účinný způsob popisu rekurzivních datových struktur, které jsou částečně složeny z menších a jednodušších výskytů sebe sama. Nejedná se o definici v kruhu, neboť v jisté úrovni dospějeme k seznamu, který nemá žádné položky, jež by byly seznamem.

Předpokládejme, že našim úkolem je napsat funkci, která sečte všechny hodnoty v seznamu s vnořenými seznamy. Python má vestavěnou funkci, která vytvoří součet řady čísel:

>>> sum([1, 2, 8])
11
>>> sum((3, 5, 8.5))
16.5
>>>

Pro náš seznam s vnořenými seznamy však funkce sum nepracuje:

>>> sum([1, 2, [11, 13], 8])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'list'
>>> 

Problém spočívá v tom, že třetí položka seznamu je také seznam [11, 13], který nemůže být přičten k 1, 2, a 8.


13.2 Rekurze II

Tento text je pokračováním části 4.5 - Rekurze I.

K vytvoření součtu všech čísel v našem rekurzivním seznamu s vnořeným seznamem potřebujeme traverzovat seznamem, navštívit každou číselnou položku uvnitř vnořené struktury a připočítávat číselné hodnoty k našemu součtu.

Potřebný program pro vytvoření součtu čísel v seznamu s vnořeným seznamem je díky rekurzi překvapivě krátký:

def recursive_sum(nested_num_list):
    sum = 0
    for element in nested_num_list:
        if type(element) == type([]):        # je-li položkou seznam
            sum = sum + recursive_sum(element)
        else:
            sum = sum + element
    return sum

Tělo fce se skládá hlavně ze smyčky for, která traverzuje seznamem nested_num_list. Je-li položkou seznamu numerická hodota nikoliv seznam (větev else), přičte se číslo jednoduše k proměnné sum. Je-li položkou seznam, potom je opět volána fce recursive_sum pro argument, jímž je vnořený seznam. Příkaz uvnitř těla funkce, jímž je volána táž funkce, se nazývá rekurzivní volání.

Poněkud komplikovanější úlohou je nalezení největší hodnoty v seznamu s vnořeným seznamem. Následující definice funkce obsahuje doctest (viz kap. 5.10), kterým si jednak ilustrujeme řešený problém a zároveň ověříme správnost naší funkce:

def recursive_max(nested_num_list):
    """
    >>> recursive_max([2, 9, [1, 13], 8, 6])
    13
    >>> recursive_max([2, [[100, 7], 90], [1, 13], 8, 6])
    100
    >>> recursive_max([2, [[13, 7], 90], [1, 100], 8, 6])
    100
    >>> recursive_max([[[13, 7], 90], 2, [1, 100], 8, 6])
    100
    """
    largest = nested_num_list[0]
    while type(largest) == type([]):
        largest = largest[0]

    for element in nested_num_list:
        if type(element) == type([]):
            max_of_elem = recursive_max(element)
            if largest < max_of_elem:
                largest = max_of_elem
        else:            # element is not a list
            if largest < element:
                largest = element

    return largest

Čertovým kopýtkem tohoto problému je určení numerické hodnoty pro inicializaci proměnné largest. Nemůžeme jednoduše zadat, že je to nested_num_list[0], protože by touto položkou mohlo být jak číslo, tak seznam. Problém je řešen použitím smyčky while, která přiřadí proměnné largest první číselnou hodnotu bez ohledu na hloubku jejího vnoření.

Nekonečná rekurze

Při rekurzivním volání téže funkce se generuje řada výsledků, z nichž jeden má být určen jako výstup volání posledního. Takový výsledek se nazývá základní případ (base case). Bez základního případu dostaneme nekonečnou rekurzi. Tato situace je technicky ošetřena tak, že se Python zastaví po dosažení implicitně nastavené hloubky rekurze (1000 cyklů) a vrací chybu při běhu programu.

Ve funkci recursive_sum je počet rekurzivních volání určen počtem prvků v seznamu. Základní případ zde poskytuje skrytá funkce next() idiomu FOR i IN iterable (viz odst. 13.4 Iterátory). Ve funkci countdown(n) (s koncovou rekurzí) je základním případem hodnota n = 0.

Příkladem nekonečné rekurze budiž tato funkce:

#
# infinite_recursion.py
#
def recursion_depth(number):
    print("Recursion depth number {}." .format(number))
    recursion_depth(number + 1)

recursion_depth(0)

Ve stejném adresáři, ve kterém máte uložený svůj program, zapište na příkazový řádek:

python infinite_recursion.py

Po bezmocném sledování ubíhajících řádků na monitoru se po chvíli dočkáte následujícího konce záznamu:

  ...
  File "infinite_recursion.py", line 3, in recursion_depth
    recursion_depth(number + 1)
RuntimeError: maximum recursion depth exceeded

Nekonečná rekurze může být těžko něčemu prospěšná, takže si při každé deklaraci rekurzivního volání bedlivě ohlídáme okrajové podmínky, vytvářející základní případ.

Koncová rekurze

Když se rekurzivní volání objeví na posledním řádku těla funkce, označujeme jej jako koncovou rekurzi.

Zde je koncová rekurze použita u funkce countdown:

def countdown(n):
    if n == 0:
        print("Blastoff!")
    else:
        print(n)
        countdown(n-1)

Mnohé dobře známé matematické funkce jsou definovány rekurzivně. Například Fibonacciho číslo, nebo fibonacciho sekvence, definovaná:

fibonacci(0) = 1
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

To lze také snadno přepsat do Pythonu:

def fibonacci (n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Kód pro fibonacci je příkladem koncové rekurze.

Koncová rekurze je však v Pythonu považována za špatnou techniku, protože používá více systémových zdrojů než ekvivalentní iterativní řešení.

Volání fibonacci(500) uvede interpreta Pythonu do rozpaků.

Mnohem rychlejší než rekurzivní verze je verze iterační, která by mohla vypadat takto:

def fiboiter (n):
    old, new = 0, 1
    if n == 0:
        return 0 
    for i in range(n-1):
	old, new = new, old + new
    return  new

Vyzkoušejte volání fibointer(500) a budete příjemně překvapeni.
Při cvičení si zkusíte napsat iterační verzi funkce factorial a v dalším odstavci si ukážeme memoizovanou alternativu funkce fibonacci, která je ze všech tří verzí nejrychlejší.


13.3 Memoizace

Když jsme si v předchozím odstavci pohrávali s funkcí fibonacci, mohli jsme si všimnout, že čím větší argument jsme použili, tím déle trvalo provádění funkce. Se zvětšujícím se argumentem časové nároky velmi rychle rostly. Na jednom z našich počítačů končí fibonacci(20) okamžitě, fibonacci(30) zabere asi vteřinu a fibonacci(40) trvá zhruba věčnost.

Abychom pochopili proč, pohleďme na toto schéma volání funkce fibonacci(4):

Schéma zobrazuje sadu funkcí v rámečcích se šipkami, ukazujícími na volané funkce. Nejvýše umístěná fce, fibonacci(4) volá fibonacci(3) a fibonacci(2). Fce fibonacci(3) zas volá fibonacci(2) a fibonacci(1). A tak dále.

Spočítejme, kolikrát je voláno fibonacci(0) a fibonacci(1). Je to řešení neefektivní a rychle se zhoršuje při zvětšujícím se argumentu.

Dobrým řešením, zvaným memoizace (memoization), je ukládat si záznamy (hints) o spočítaných hodnotách do slovníku pro potřebu dalšího použití. Takovýmto záznamům říkejme třeba náznaky. Zde vidíme realizaci funkce fibonacci s podporou náznaků:

memo = {0:0, 1:1}
def fibomem(n):
    if n not in memo:
        memo[n] = fibomem(n-1) + fibomem(n-2)
    return memo[n]
Slovník memo zaznamenává fibonacciho čísla, která již známe. Začínáme pouhými dvěma páry: 0 ukazuje na 0, 1 na 1.

Kdykoli je funkce fibomem volána, prozkoumá svůj slovník, zda neobsahuje výsledek. Jestliže ano, vrací výsledek bez dalších okolků. Jestliže ne, počítá novou hodnotu. Tato hodnota je přidána do slovníku před tím, než se funkce vrátí k rekurzivnímu volání.

S použitím této verze náš počítač spočítá fibonacci(50) v jednom oka mžiku.

>>> fibomem(100)
354224848179261915075

Alternativní způsob výpočtu Fibbonacciho čísla pomocí memoizace představuje výpočet s podporou dekorátorů (viz kap.3.11 a kap. 12.12):

def memoize(fun):                # dekorátorová funkce
    memo = {}
    def wrapper(x):
        if x not in memo:            
            memo[x] = fun(x)
        return memo[x]
    return wrapper
    
@memoize                         # dekorace funkcí
def fibomem(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibomem(n-1) + fibomem(n-2)

# >>> fibomem(100) ==> 354224848179261915075
class Memoize:                    # dekorátorová třída
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if args not in self.memo:
            self.memo[args] = self.fn(*args)
        return self.memo[args]

@Memoize                         # dekorace třídou
def fibomem(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibomem(n-1) + fibomem(n-2)

# >>> fibomem(100) ==> 354224848179261915075

Všechny tři způsoby používají slovník memo a podmínku if x not in memo:.


13.4 Iterátory

Iterátor je interní objekt, jenž vlastní metody __iter__() a __next__(), které vracejí hodnotu následného elementu při každé své invokaci.

Iterátor se vytváří čtverým způsobem:

  1. Použitím funkce iter - viz kap. 4.6.
  2. Skrytě, pro interní potřebu idiomu for... či funkce open(...), min(), max(), map(), filter(), zip(), enumerate() a reversed().
  3. Pomocí generátorové funkce a generátorového výrazu, jejichž výstupem jsou iterátory, které provádějí takzvaný líný výpočet (lazy evaluation).
  4. Vytvořením třídy s definovanými metodami __iter__() a next(). Takto definovaný iterátor líný výpočet neprovádí.

Iterátory definované třídou

Iterátorem v tomto případě je instance třídy s definovanými metodami __iter__()  a next().

Jako příklad si uvedeme skript, který si poté pustíme v konzole:

class CountTo: 
    def __init__(self, m):
        self.m = m-1
        self.n = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.n <= self.m:
            cur, self.n = self.n, self.n + 1
	    return cur
        else:
            raise StopIteration() 
>>> cnt = CountTo(5)     # instance třídy a zároveň iterátor
>>> next(cnt)            # první iterace
0 
>>> for i in cnt: print(i, end=" ") 
1 2 3 4                  # opakovaná iterace pro zbytek členů
>>> for in cnt: print(i, end=" ") 
...                      # zdvořilé mlčení, iterátor je prázdný

Alternativa funkce squares(start, stop) ve tvaru uživatelského iterátoru může mít tento tvar:

class Squares(object): 
    def __init__(self, start, stop):
        self.start = start
        self.stop = stop
    def __iter__(self):
        return self
    def __next__(self):
        if self.start >= self.stop:
            raise StopIteration
        current = self.start * self.start
        self.start += 1
        return current 
>>> sqr = Squares(4,8)          # instance třídy a zároveň iterátor
>>> 
>>> for i in sqr: print(i, end=" ") 
16 25 36 49                     # dychtivá (eager) iterace
>>> for in sqr: print(i, end=" ") 
...                             # zdvořilé mlčení, iterátor je prázdný

13.5 Generátory

Generátor je objekt, vytvořený aplikací generátorového výrazu, případně voláním generátorové funkce. Generátor je iterátor, který místo hotových objektů ukládá instrukce pro jejich individuální vytvoření při iteraci.

Generátorový výraz

Generátorový výraz je vytvořen komprehenci entice (viz 8.10).

>>> st = "abakus"                     # iterovatelný řetězec - iteráble 
>>> stv = (i for i in st)             # generátorový objekt - iterátor
>>> for i in st: print (i, end=" ")   # dychtivá (eager) iterace iteráblu
a b a k u s 
>>> for i in stv: print (i, end=" ")  # líná (lazy) iterace iterátoru
a b a k u s 

Generátorový výraz lze vytvořit i s použitím idiomu for pro funkci range(~). Zde funkce range() vytvoří iterovatelný objekt, který se komprehencí přemění na iterátor:

>>> gv = (i*i for i in range(5))        # generátorový objekt - iterátor 
>>> for i in gv: print (i, end=", ")    # líná (lazy) iterace 
0, 1, 4, 9, 16 

Generátorová funkce

Generátorová funkce musí obsahovat alespoň jeden příkaz yield. Volání generátorové funkce vrací generátorový objekt, jenž je iterátorem s přímo použitelnou funkcí next(~) či metodou __next__() - stejně jako v předchozím případě:

def count_to(m):
   n = 0
   while n <= m:
      yield n              # poskytuje elementy iterátoru
      n += 1
========== RESTART: F:\Codetest\HowTo\trump.py ==========

>>> ct = count_to(5)                  # generátorový objekt, iterátor
>>> next(ct)                          # 1. krok dychtivé iterace
0
>>> ct.__next__()                     # 2. krok dychtivé iterace
1
>>> for i in ct: print (i, end=" ")   # líná (lazy) iterace
2 3 4 5
>>> next(ct)
StopIteration                         # iterátor je prázdný

Generátorový objekt vytvoří i tato generátorová funkce:

def squares(start, stop): 
    for i in range(start, stop):
        yield i * i

Výpočet řady Fibonacciho čísel můžeme provést pomocí následujícího generátoru:

def fibonacci():
    a, b = 0, 1 
    while True:  # nekonečná smyčka! 
        yield a
        a, b = b, a+b 

Generátor s nekonečnou smyčkou voláme pro konkretní mez:

>>> f = fibonacci() 
>>> type(f)        # -->  <class 'generator'> 
>>> f.__next__()   # -->  0
>>> next(f)        # -->  1    alternativní verze
...
>>> for i in range(7): print(next(f), end=" ")
1 2 3 5 8 13 21
>>> f.__next__()   # -->  34 

Generátorový výraz a generátorová funkce vrací generátorový objekt, který je pomalu (líně) vyhodnocovaným iterátorem.

Líný výpočet

Generátorové objekty podporují líný výpočet (lazy evaluation), při kterém se odkládá výpočet výrazu až do chvíle jeho potřeby. Důsledkem je zmenšená potřeba zdrojů (paměti) při zvýšeném výkonu procedury.

Lze sestavit potenciálně nekonečné struktury, např. smyčky - viz fibonacci().

Líný výpočet se obtížně kombinuje s imperativními strukturami jako je ošetření výjímek nebo vstup/výstup; může vytvářet "space leaks" (viz).

Příkladem procedury, uplatňující líný výpočet, je použití slovníku v kapitole 11.7 Switch case, kde u funkce kalkul(oprerátor, x,y) je řešeno částečné ošetření výjimek.


13.6 Chyby a výjimky

Jak už bylo uvedeno v první kapitole, mohou se při kompilaci kódu vyskytnout chyby skladebné (syntaktické) a chyby za běhu programu takzvané "run-time errors". Oba typy chyb jsou události, které Python umí ošetřit.

Syntaktické chyby

Při výskytu skladebné chyby se zastaví běh kompilace a zobrazí se informace s uvedením inkriminovaného řádku a označením místa na řádku, kde k chybě došlo (celé slovo před znakem ^ - zde za slovem True má být dvojtečka):

>>> while True print ("Nazdar!")
   File "<stdin>", line 1
     while True print ("Nazdar!")
	            ^
 SyntaxError: invalid syntax     

Výjimky

Výjimka (exception) je systemizovaná chyba, k níž dojde při běhu programu. Výjimky jsou definovány jako třídy, odvozené od třídy BaseException. Úplný výpis těchto tříd lze nalézt v Built-in Exceptions.

Kromě vestavěných (built-in) výjimek (např. TypeError, IndexError, ZeroDivisionError, ... ) je možné používat vlastní typ výjimky vytvořením třídy, odvozené od třídy Exception - viz User defined exceptions.

Při výskytu systemizované chyby (např. dělení nulou) zastaví Python běh programu a zobrazí informaci o vzniklé chybě:

>>> print(55/0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: division by zero
>>>

Chybové hlášení na poslední řádce se skládá ze dvou částí: název chyby (neboli třídy-výjimky) před dvojtečkou a podrobnosti o chybě za dvojtečkou.

Ošetření výjimek

Chceme-li zařídit aby po výskytu určité chyby pokračovalo provádění programu, provedeme takzvané "ošetření výjimky" (exception handling).

To zpravidla spočívá v použití příkazu try ... except (případně také else či finally ) dle následujícího schematu:

try: 
    do_something()
except:
    handle_exception()
... 

Klauzulí except může být v případě potřeby více, případně se jedna klauzule může vztahovat na více výjimek:

... except(RuntimeError, TypeError, NameError):
... pass        # some activity

Pro klauzuli except s určitou standardní výjimkou platí, že tato klauzule se vztahuje také na všechny výjimky, které jsou z uvedené výjimky (třídy) odvozené.

Neuvedeme-li v klauzuli žádnou výjimku, pak tato klauzule platí pro všechny vestavěné výjimky, což nemusí být zrovna to pravé ořechové:

def bad_example(number):
    try:
	return number / 0
    except: # slabá klauzule
	print("Máme chybu, nevíme jakou")
>>> bad_example("aleš")
Máme chybu, nevíme jakou	

Příklad s try, except, else:

# Určení přítomnosti či nepřítomnosti souboru

def exists(filename):   # název souboru v uvozovkách
    try:
        f = open(filename)
    except OSError:		
        print ("Soubor nenalezen")
    else:  
        f.close() 
	print ("Soubor existuje a byl zavřen")

Sémantická výhrada: Zjišťovat přítomnost souboru tím, že jej dokážeme otevřít, je poněkud nemotorné. Jednak může dojít k aktualizaci časového razítka, druhak můžeme dostat nesprávnou odpověď jenom proto, že je soubor někde otevřen nebo že k němu nemáme oprávnění.

Vybranější způsob je pomocí metody isfile z modulu os.path:

if os.path.isfile("c:/temp/testdata.txt"):
...

Záměrné vyvolání výjimek

Když program narazí na omezující podmínku, můžeme pro případ jejího nesplnění přinutit program, aby vyvolal (raise) standardní výjimku. Následuje příklad, ve kterém se zkoumá zda uživatelem zadané číslo je nezáporné. Pokud je záporné, oznámí se výjimka.

# learn_exceptions.py

def get_age():
    age = int(input('Uveďte svůj věk: '))
    if age < 0:
       	raise ValueError("{0} není platná hodnota".format(age))
    return age

>>> get_age()
Uveďte svůj věk: -15
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "learn_exceptions.py", line 10, in get_age
    raise ValueError("{0} není platná hodnota".format(age)
ValueError: -15 není platná hodnota
>>>

Nebo lze raise použít i pro ošetření vlastní výjimky:

class MyExcept(Exception):
    def: __init__(self, length, atleast)
	Exception.__init__(self)
	self.length = length
	self.atleast = atleast
	
try:
    s = input("Zadej heslo: ")
    if len(s) < 7:
        raise MyExcept(len(s), 7)
except MyExcept as x:
    print ("MyExceptError: Heslo je krátké ({0}<{1})" 
	           .format(x.length, x.atleast))
else:
    print ("Heslo je v pořádku")	

13.7 Glosář

datová struktura (data structure)
Uspořádání dat pro jejich snadnější použití.
rekurzivní definice (recursive definition)
Definice, která se odkazuje sama na sebe. Aby byla smysluplná, musí obsahovat nerekurzivní základní případ. Tímto se liší od definice v kruhu. Rekurzivní definice často skýtají elegantní způsob vyjádření složitých datových struktrur.
rekurze (recursive call)
Příkaz v rekurzivní funkci, který je volá právě prováděnou funkci (to jest samu sebe).
základní případ (base case)
Větev podmíněného příkazu v rekurzivní funkci, který nevede k rekurzivnímu volání.
nekonečná rekurze (infinite recursion)
Funkce, která rekurzivně volá sama sebe, aniž by dospěla k základnímu případu. Způsobí chybu při běhu programu.
koncová rekurze (tail recursion)
Rekurzivní volání umístěné na konci definice funkce. Tato metoda se příliš nedoporučuje, protože bývá méně účinná než iterativní funkce (see the Wikipedia article on tail recursion for more information).
výjimka (exception)
Chyba při běhu programu, pro níž je k dispozici definice třídy.
ošetřit výjimku (handle an exception)
Zabránit registrované chybě (výjimce) aby ukončila běh programu s použitím příkazů try a except.
vyvolat výjimku (raise)
Aktivovat výjimku s použitím příkazu raise.

13.8 Cvičení

  1. Napište funkci recursive_min, která vrátí nejmenší číselnou hodnotu seznamu s vnořenými seznamy:
    def recursive_min(nested_num_list):
        """
        >>> recursive_min([2, 9, [1, 13], 8, 6])
        1
        >>> recursive_min([2, [[100, 1], 90], [10, 13], 8, 6])
        1
        >>> recursive_min([2, [[13, -7], 90], [1, 100], 8, 6])
        -7
        >>> recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6])
        -13
        """
    
    Funkce by měla vyhovět všem doctestům.
  2. Napište funkci recursive_count, která vrátí počet výskytů číselné hodnoty target v seznamu nested_number_list:
    def recursive_count(target, nested_num_list):
        """
        >>> recursive_count(2, [2, 9, [2, 1, 13, 2], 8, [2, 6]])
        4
        >>> recursive_count(7, [[9, [7, 1, 13, 2], 8], [7, 6]])
        2
        >>> recursive_count(15, [[9, [7, 1, 13, 2], 8], [2, 6]])
        0
        >>> recursive_count(5, [[5, [5, [1, 5], 5], 5], [5, 6]])
        6
        """
    
    Funkce vyhoví všem doctestům?
  3. Napište funkci flatten, která vrátí jednoduchý seznam, obsahující všechny honoty z nested_number_list:
    def flatten(nested_num_list):
        """
        >>> flatten([2, 9, [2, 1, 13, 2], 8, [2, 6]])
        [2, 9, 2, 1, 13, 2, 8, 2, 6]
        >>> flatten([[9, [7, 1, 13, 2], 8], [7, 6]])
        [9, 7, 1, 13, 2, 8, 7, 6]
        >>> flatten([[9, [7, 1, 13, 2], 8], [2, 6]])
        [9, 7, 1, 13, 2, 8, 2, 6]
        >>> flatten([[5, [5, [1, 5], 5], 5], [5, 6]])
        [5, 5, 1, 5, 5, 5, 5, 6]
        """
    
  4. Napište funkci readposint, která vyzve uživatele k zadání kladného celého čísla a vstup ověří. Ukázka průběhu může vypadat takto:
    >>> num = readposint()
    Please enter a positive integer: yes
    yes is not a positive integer.  Try again.
    Please enter a positive integer: 3.14
    3.14 is not a positive integer.  Try again.
    Please enter a positive integer: -6
    -6 is not a positive integer.  Try again.
    Please enter a positive integer: 42
    >>> num
    42
    >>> num2 = readposint("Now enter another one: ")
    Now enter another one: 31
    >>> num2
    31
    >>>
    
    Pro ověření správnosti uživatelského vstupu použijte mechanizmus ošetření výjimky.
  5. Přepište funkci factorial s použitím iterace místo rekurze. Volejte svou funkci pro argument 1000 a změřte jak rychle vrátí výsledek.

previous up next hi end end