Chapter 9: Lists II

K vyjádření matic se často používají vnořené seznamy. Například, matice o rozměru 3x3 (3 řádky x 3 sloupce):

může být vyjádřena jako seznam s vnořenými seznamy stejné délky. Jednotlivé vnořené seznamy prezentují příslušné řádky matice:

V maticovém počtu lze tyto vnořené seznamy označit jako řádkové matice, neboli vektory.

Řádek matice vybereme jako prvek vnějšího seznamu (indexy počínají nulou):

Práce s maticemi vyžaduje specifické znalosti maticového počtu. Na rozdíl od algebry v něm například obecně neplatí komutativní zákon: A*B != B*A; platí ale C = A+B == B+A, kde c_i,j = a_i,j +b_i,j.

Násobení matice A o velikosti m (řádků) * n (sloupců) maticí B o velikosti n (řádků) * p (sloupců) je možné v případě, že počet sloupců (n) matice A souhlasí s počtem řádků (n) matice B. Rozměr výsledné matice je m x p.

Pokud je tato podmínka splněna, lze prvek c_i,j matice C = A*B určit jako algebraický součet součinů prvků z i-tého řádku matice A s prvky z i-tého sloupce matice B, jak je naznačeno v tomto schematu:

Rozměr výsledné matice ab je tedy dán počtem řádků matice a ( m rows = len(a)) a počtem sloupců matice b (p cols = len(b[0])).

Výpočet součinu matic lze provést trojím použitím idiomu for i in range(len(...)):

Sevřenější tvar má toto řešení s komprehencí seznamu a s vestavěnými funkcemi sum a zip:

9.2 Testem podnícený rozvoj

Testem podnícený rozvoj (Test-driven development - TDD) je způsob vyvíjení programu, při kterém se postupuje po malých, automaticky ověřovaných krocích.

Tento postup si ukážeme na sestavení funkce, která vytvoří matici m * n (rows krát columns). Při tomto postupu použijeme doctesty, které jsme poznali již v odstavci 3.8.

Nejprve pro tuto funkci sestavime doctestest bez programového kódu a uložíme do souboru ch09_matrices.py:

Test nebyl úspěšný proto, že tělo funkce obsahuje pouze dokumentační řetězec a žádný příkaz return, takže je vráceno Got nothing. Náš test nám naznačuje, že jsme chtěli vrátit matici se samými nulami ve třech řadách a pěti sloupcích.

Při použití TDD zpravidla píšeme ten nejjednodušší kód, který projde testem, v našem případě to je příkaz return:

Při provedení tohoto skriptu rovněž neobstojíme i když dostáváme semanticky stejný ale formálně různý výsledek, lišící se v tom, že citované seznamy jsou různě dlouhé, ten druhý je delší o mezery mezi jednotlivými položkami - doctesty se někdy chovají podivně.

Doplníme tedy mezery do seznamu v dokumentačním řetězci a spuštěním skriptu si ověříme, že tentokrát je všechno v pořádku (no response)
Rozteče argumentů příkazu return upravovat nemusíme, příkaz si je upraví sám.

Uvědomíme si ale, že funkce make_matrix vrací stále týž výsledek, což zajisté není to, co jsme zamýšleli. Ověříme si to přidáním dalšího testu:

Tato technika se nazývá testem podnícená, protože se snažíme upravovat kód tak, abychom prošli testem. Motivováni nezdařeným pokusem, můžeme nyní zkusit obecnější řešení:

Řešení formálně neuspokojí proceduru doctestu. Jevově jsou oba řádky stejné ale interně se budou zřejmě lišit počtem připojených (neviditelných) mezer. Řekněmež, že nám to nevadí.

Použití TDD nám při našem programátorském snažení přináší několik výhod:

Funkci make_matrix(r,c) můžeme použít v cvičení 9.7.2 pro vytvoření výchozí (nulové) matice při sčítání (odčítání) matic:

9.3 Náhodná čísla

Většina počítačových programů provádí při každém spuštění totéž, takže říkáme, že jsou deterministické.

Determinismus je obvykle dobrá věc, protože můžeme předpokládat, že stejný výpočet povede ke stejnému výsledku. U některých aplikacích si však přejeme, aby počítač byl nepředvídatelný. Hry jsou zřejmým příkladem, ale těch příkladů může být více.

Ukazuje se, že napsat program se skutečně nepředvídatelným chováním není snadné, ale jsou způsoby, kterak jej učinit alespoň zdánlivě nedeterministickým. Jedním ze způsobů je použití náhodných čísel. Python poskytuje vestavěnou funkci, která generuje pseudonáhodná čísla, která nejsou náhodná v přísně matematickém smyslu, ale pro naše účely postačí.

Modul random obsahuje funkci zvanou random, která vrací desetinné číslo v rozsahu [0.0 až 1.0). Pokaždé, když voláme funkci random, dostaneme "náhodnou" hodnotu mezi nulou včetně a méně než jedničkou. Více náhodných hodnot můžeme vygenerovat pomocí funkce se smyčkou:

Náhodná čísla mezi nulou a zadanou mezí high, získáme násobením generovaných čísel x hodnotou high.

Náhodný výběr

Podobným problémem jako vytvoření náhodného čísla je provedení náhodného výběru. Ten lze provést pomocí funkce choice z modulu random:

Jak vidno, prvky výběrové kolekce (list, tuple, string nebo set) mohou být různého typu. Samotný set však argumentem funkce choice přímo být nemůže, protože objekt set is not subscriptable.

9.4 Výskyty náhodných čísel

9.4.1 Seznam náhodných čísel

K vytvoření seznamu náhodných čísel, musíme od první chvíle vědět, v jakém rozsahu se generovaná náhodná čísla budou pohybovat [0 až 1) a kolik těch čísel má seznam obsahovat (zřejmě n). Jméno n bude parametrem funkce randomList, kterou si sestavíme.
Tělo funkce začíná vytvořením seznamu s n nulami. Při každém cyklu smyčky se jedna z nul nahradí náhodným číslem. Výstupní hodnotou je odkaz na dokončený seznam.

Voláním (invokací) této funkce pro n=6 vytvoříme seznam se šesti položkami:

Předpokládá se, že náhodná čísla, generovaná systémovou funkcí random jsou rovnoměrně rozdělena, to znamená, že výskyt každé hodnoty má (limitně) stejnou pravděpodobnost.

Tento předpoklad si zkusíme ověřit napsáním programu, který rozdělí hodnoty do úseků a určí počet výskytů v jednotlivých úsecích, neboli jejich četnost.

Rozdělíme-li celý interval možných náhodných hodnot do stejně velikých úseků, a spočítáme-li výskyt náhodných hodnot v jednotlivých úsecích, měl by tento výskyt být všude přibližně stejný.

9.4.2 Vytvoření úseků

Označíme-li počet úseků (buckets) jménem numBuckets a vyjdeme ze skutečnosti, že rozpětí hodnot náhodných čísel má interval 0.0 (inclusive) až 1.0 (exclusive), potom velikost jednoho úseku (bucketWidth) určíme jako podíl 1.0 / numBuckets.

K výpočtu mezí jednotlivých úseků použijeme smyčku. Pro každý úsek určíme jeho spodní (low) a horní (high) hodnotu. Proměnná i smyčky for ... počítá s rozpětím nula až (numBuckets - 1):

Při výpočtu dolní meze jednotlivého úseku (kyblíku) násobíme proměnnou smyčky podílem na jeden kyblík. Horní mez je o bucketWidth vyšší.

Pro numBuckets = 8 například, jsou (zde inkluzivní) rozsahy mezí následující:

9.5 Četnost výskytů

Chceme procházet vygenerovaným seznamem náhodných čísel [0.0 - 1.0) a určovat, kolik náhodných čísel zapadne do některého ze stanovených úseků (kyblíků, buckets). Řešení této úlohy si ukážeme ve dvou variantách. Pro první variantu si sestavíme funkci sami, pro druhou variantu je funkce již pro nás připravená.

9.5.1 Opakované traverzování seznamem

Pro tuto variantu si sestavíme funkci buckets_a(n,b), kterou vložíme do souboru buckets.py.

Vyjdeme z upravené sekvence příkazů ve cvičení 6.17.2, kde jména char, fruit nahradíme označením num a list (seznam všech náhodných čísel).

V dalším kroku změníme předmět prověřování. Nezajímá nás výskyt písmen v řetězci ale chceme vědět, zda se hodnota proměnné num (aktuálně prověřované náhodné číslo) nalézá mezi příslušnými hodnotami low a high (viz odst. 9.4.2) aktuálního úseku.
Za tím účelem doplníme smyčku for ... o podmínku if:

Následně zapouzdříme upravený kód do funkce zvané inBucket. Jejími parametry bude seznam všech náhodných čísel list a meze úseků low a high.

Právě odvozenou funkci možná použijeme jako pomocnou funkci v dalším výpočtu. Musíme ale dořešit, kterak operativně dosazovat meze low a high pro jednotlivé úseky.

Pro záznam výskytů náhodných čísel v jednotlivých úsecích vytvoříme seznam výskyty. Vypišme si, co všechno budeme v námi sestavované funkci buckets_a(n,b) potřebovat:

K hladkému provedení výše uvedeného skriptu musí mít interpret Pythonu k disposici importovaný modul random a definice funcí randomList a inBucket.
Nejlépe to zajistíme tak, že založíme soubor buckets.py, do něhož vše potřebné vložíme.

Z výše uvedeného skriptu vytvoříme funkci buckets_a(n,b), když jméno numBuckets vypustíme a v dalším kódu jej nahradíme jménem b.
Když v interaktivní konzole IDLE provedeme volání buckets_a (1000, 8), získáme přibližně takovýto seznam s četnostmi výskytů:

Tato čísla jsou docela blízká číslu 0.125*1000=125 (viz 'bucketWidth'), jak jsme si přáli. Generátor pseudonáhodných čísel nám tedy 'tak nějak' funguje.

9.5.2 Jednorázové řešení

I když nám náš program chodí, mohl by chodit ještě lépe. Pokaždé, když volá funkci inBucket, prochází opakovaně pro každý kyblík celým seznamem. S větším počtem kyblíků jde o značný počet cyklů.

Lepší by bylo projít seznamem jen jednou a pro každou hodnotu náhodného čísla určit rovnou index úseku (neboli index položky seznamu výskyty), do kterého náhodné číslo spadá.

Idea výhodnějšího řešení spočívá v tom, že náhodné číslo i násobíme počtem úseků b. Protože náhodná čísla jsou v rozpětí 0.0 až 1.0, je součin i*b v rozpětí 0.0 až b. Zaokrouhlíme-li každý součin na celé číslo ( int (i * b) ), získáme index položky seznamu výskyty, kam posuzovaná hodnota patří - této položce zvětšíme stav počítadla.

Výstupem z funkce buckets_b(n,b) je obdobný výpis jako v předchozím případě:

Dotazy pro zvídavé: Výraz int(i*b) zaokrouhluje dolů. Co se stane, když použijeme výraz round(i*b)? Co vlastně provádí naše smyčka for i in list:? Proč zvětšujeme index akumulátoru o hodnotu 1?

9.6 Glosář

9.7 Cvičení

Pro následující doctesty vytvořte záhlaví a těla funkcí, které přidají řádek, případně sloupec do zadané matice. Můžete vyzkoušet postup TDD z odstavce 9.3:

def add_row (matrix): 
    """
    >>> m = [[0,0], [0,0]] 
    >>> add_row(m)    
    [[0, 0], [0, 0], [0, 0]]
    >>> n = [[3, 2, 5], [1, 4, 7]]
    >>> add_row(n)
    [[3,2,5], [1,4,7], [0,0,0]]
    >>> n
    [[3,2,5], [1,4,7]]
    """
def add_column (matrix): 
    """
    >>> m = [[0,0], [0,0]] 
    >>> add_column(m)    
    [[0,0,0], [0,0,0]]
    >>> n = [[3,2], [5,1], [4,7]]
    >>> add_column(n)
    [[3,2,0], [5,1,0], [4,7,0]]
    >>> n
    [[3,2], [5,1], [4,7]]
    """

Všimněte si, že poslední doctesty v každé funkci ověřují, že add_row a add_column jsou funkce čisté.

Napište funkci add_matrices(m1, m2), která vrátí novou matici, jež je součtem matic m1 a m2. Sečíst dvě matice znamená sečíst hodnoty odpovídajících členů. Můžete předpokládat, že matice m1 a m2 mají stejnou velikost.

def add_matrices (m1, m2): 
    """
    >>> a = [[1,2], [3,4]]
    >>> b = [[2,2], [2,2]] 
    >>> add_matrices(a, b)    
    [[3,4], [5,6]]
    >>> c = [[8,2], [3,4], [5,7]]
    >>> d = [[3,2], [9,2], [10,12]]
    >>> add_matrices(c, d)
    [[11,4], [12,6], [15,19]]
    >>> c
    [[8,2], [3,4], [5,7]]
    >>> d
    [[3,2], [9,2], [10,12]]
    """

Poslední dva doctesty opět potvrzují, že add_matrices je čistá funkce.

Napište funkci scalar_mult(n, m), která násobí matici m skalárem n. Doplňte tělo funkce a ujistěte se, že projde doctesty.

def scalar_mult (n, m): 
    """
    >>> a = [[1,2], [3,4]]
    >>> scalar_mult(3, a)    
    [[3, 6], [9, 12]]
    >>> b = [[3,5,7], [1,1,1], [0,2,0], [2,2,3]]
    >>> scalar_mult(10, b)
    [[30, 50, 70], [10, 10, 10], [0, 20, 0], [20, 20, 30]]
    >>> b
    [[3, 5, 7], [1, 1, 1], [0, 2, 0], [2, 2, 3]] 
    """

Na základě získané zkušenosti zkuste násobit matici maticí.

def matrix_mult (m1, m2): 
    """
    >>> matrix_mult([[1,2], [3,4]], [[5,6], [7,8]])
    [[19, 22], [43, 50]]
    >>> matrix_mult([[1,2,3], [4,5,6]], [[7,8], [9,1], [2,3]])
    [[31, 19], [85, 55]]
    >>> matrix_mult([[7,8], [9,1], [2,3]], [[1,2,3], [4,5,6]])
    [[39, 54, 69], [13, 23, 33], [14, 19, 24]]
    """

Početní operace s maticemi v příkladech 1 až 4 proveďte i prostřednictvím aplikace Numpy.

Pro lepší porozumění booleovským výrazům jsou dobré pravdivostní tabulky. Dva booleovské výrazy jsou logicky rovnocenné tehdy a jen tehdy, mají-li stejné pravdivostní tabulky.
Následující skript vytiskne pravdivostní tabulku pro libovolný booleovský výraz s proměnnou p a q.
```
expression = input("Zadej booleovský výraz \ 
                    pro 'p' a 'q' : " )
print(" p    q    %s"   % expression)
delka = len(" p    q    %s"   % expression)
print(delka* "=")

for p in True, False:
    for q in True, False:
        print("%-7s %-7s %-7s" % (p, q, eval(expression)))
```
Tento skript použijeme pro osvojení booleovských výrazů. Uložte program do souboru bool_table.py, importujte jej do konzoly interpreta a zadejte 'p or q'. Měl byste dostat následující výstup:
```
  p       q      p or q
------------------------
True    True      True
True    False     True
False   True      True
False   False     False
```

Nyní, když víme že kód pracuje, zabalíme jej pro lepší použití do funkce (a uložíme do truth_table.py):

def truth_table(expression): 
    print(" p    q    %s"   % expression)
    delka = len(" p    q    %s"   % expression)
    print(delka* "=")

    for p in True, False:
        for q in True, False:
            print("%-7s %-7s %-7s" % (p, q, eval(expression)))

Funkci zavoláme z konzoly IDLE:

>>> truth_table ("p or q")
 
  p       q      p or q
------------------------
True    True      True
True    False     True
False   True      True
False   False     False

Vyzkoušejte si fci truth_table na následujících booleovských výrazech a zapište si pravdivostní tabulky:

not (p or q)
p and q
not (p and q)
not(p) or not(q)
not(p) and not(q)

Které výrazy jsou logicky eqvivalentní?

Napište fci is_divisible(num,f), která přijme celá čísla jako argument a podle situace vytiskne "Toto číslo je dělitelné číslem f" nebo "Toto číslo neni dělitelné číslem f".
Uložte ji do souboru isDivisible.py a řešte v IDLE. Výstup může vypadat takto:
```
>>> is_divisible(20,4)
Toto číslo je dělitelné číslem 4
>>> is_divisible(21,8)
Toto číslo neni dělitelné číslem 8
```
Při řešení použijete podmínky if ... :, else: a vyberete si jeden z existujících způsobů dělení: normální a/b, celočíselné a//b a dělení se zbytkem (modulo) a%b.

9. Seznamy II

9.1 Matice jako seznam