comment up next how to end end

9. Seznamy II

  1. Vnořené seznamy
  2. Matice
  3. Testem podnícený rozvoj
  4. Náhodná čísla
  5. Seznam náhodných čísel
  6. Četnost
  7. Mnoho kyblíků
  8. Jednorázové řešení
  9. Glosář
  10. Cvičení

9.1 Vnořené seznamy

Vnořený seznam je seznam, kteý se vyskytuje jako položka jiného seznamu. V naší ukázce je vnořeným seznamem položka s indexem 3 :

>>> nested = ["hello", 2.0, 5, [10,20]]

Zadáme-li nested[3], dostaneme [10,20]. Abychom vyjmuli položku z vnořeného seznamu, můžeme postupovat ve dvou krocích:

>>> elem = nested[3]
>>> elem[0]
10

Nebo tyto kroky můžeme zkombinovat:

>>> nested[3][1]
20

Operátory s hranatými závorkami jsou vyhodnocovány zleva doprava, takže tento výraz dává nejprve tři-tou položku seznamu nested a z ní vyjme položku s indexem 1.

9.2 Matice

Vnořené seznamy se často používají k vyjádření matic. Například, matice:

může být vyjádřena takto:

>>> matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

matrix je seznam se třemi položkami, kde každá položka je řadou matice. Můžeme vybrat celou řadu matice obvyklým způsobem:

>>> matrix[1]
[4, 5, 6]

Nebo můžeme vyjmout jedinou položku z matice s použitím dvojitého indexu:

>>> matrix[1][1]
5

První index vybere řadu, druhý index vybere sloupec. I když tento způsob prezentace matic je obvyklý, není jediný. Malou obměnou je použití seznamu sloupců místo seznamu řad. Později poznáme radikálnější alternativu s použitím slovníku.

9.3 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 5.8.

Nejprve pro tuto funkci sestavime test a uložíme do souboru ch09_matrices.py:

def make_matrix (rows, columns):
    """ 
    >>> make_matrix(3,5)
    [[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]       
    """ 

if  __name__ == '__main__':
    import doctest 
    doctest.testmod()  

Provedení skriptu skončí neúspěchem:

********************************************************
File "matrices.py", line 3, in __main__.make_matrix
Failed example:
    make_matrix(3, 5)
Expected:
    [[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]
Got nothing
********************************************************
1 items had failures:
   1 of   1 in __main__.make_matrix
***Test Failed*** 1 failures.

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:

def make_matrix (rows, columns):
    """ 
    >>> make_matrix(3,5)
    [[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]       
    """ 
    return [[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]

Při provedení tohoto skriptu rovněž neobstojíme i když dostáváme nominálně 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).

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:

def make_matrix (rows, columns):
    """ 
    >>> make_matrix(3,5)
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]      
    >>> make_matrix(4,2)
    [[0, 0], [0, 0], [0, 0], [0, 0]]
    """ 
    return [[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]

Vida:

*********************************************************
File "matrices.py", line 5, in __main__.make_matrix
Failed example:
    make_matrix(4, 2)
Expected:
    [[0, 0], [0, 0], [0, 0], [0, 0]]
Got:
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
*********************************************************
1 items had failures:
   1 of   2 in __main__.make_matrix
***Test Failed*** 1 failures.

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

def make_matrix (rows, columns):
    """ 
    >>> make_matrix(3,5)
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]       
    >>> make_matrix(4,2)
    [[0, 0], [0, 0], [0, 0], [0, 0]]  
    """ 
    return [[0]* columns]* rows

Zdá se, že toto řešení chodí a můžeme si myslet, že jsme hotovi, ale později objevíme chybu:

 
>>> from ch09_matrices import *
>>> m = make_matrix(4, 3)
>>> m
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>>m[1][2] = 7
>>>m
[[0, 0, 7], [0, 0, 7], [0, 0, 7], [0, 0, 7]]
>>>

Chtěli jsme přiřadit hodnotu 7 položce ve druhé řadě a třetím sloupci a místo tohtoho mají všechny položky ve třetím sloupci hodnotu 7!

To zcele určitě není to, co jsme chtěli a proto se pustíme do nápravy problému nejprve tím, že napíšeme test, o kterém předem víme, že neprojde:

def make_matrix (rows, columns):
    """ 
    >>> make_matrix(3,5)
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]       
    >>> make_matrix(4,2)
    [[0, 0], [0, 0], [0, 0], [0, 0]]
    >>> m = make_matrix(4,2)
    >>> m[1][1] = 7
    >>> m
    [[0,0], [0,7], [0,0], [0,0]] 
    """ 
    return [[0]* columns]* rows

Maje co napravovat, jsme hnáni k lepšímu řešení:

def make_matrix (rows, columns):
    """ 
    >>> make_matrix(3,5)
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]       
    >>> make_matrix(4,2)
    [[0, 0], [0, 0], [0, 0], [0, 0]]
    >>> m = make_matrix(4, 2)
    >>> m[1][1] = 7
    >>> m
    [[0, 0], [0, 7], [0, 0], [0, 0]] 
    """ 
    matrix = []
    for row  in range(rows):
        matrix += [[0]* columns]
    return matrix

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

9.4 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 mezi 0.0 a 1.0. Pokaždé, když voláme funkci random, dostaneme jednu "náhodnou" hodnotu mezi nulou a jednou. Více náhodných hodnot můžeme vygenerovat pomocí funkce se smyčkou:

import random
def rand(high):   # high is an integer
    for i in range(high): 
        x = random.random()
    print(x*high)

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

9.5 Seznam náhodných čísel

V prvním kroku vygenerujeme seznam náhodných čísel funkcí randomList. Funkce přijme jako argument celé číslo n a vrátí seznam náhodných čísel. Začíná se seznamem s n nulami. Při každém cyklu smyčky se jedna z položek nahradí náhodným číslem. Výstupní hodnotou je odkaz na dokončený seznam.
Parametr n je požadovaný počet náhodných čísel v intervalu od nuly do jedné.

def randList(n):    
    s = [0] * n
    for i in range(n):
        s[i] = random.random()
    return s

Pomocí této funkce vytvoříme seznam se šesti položkami:

>>> randList(6)
[0.5199466739572948, 0.452751456638563,
 0.41454566096564627,
 0.7953941766158702, 0.3872848065377861,
 0.9080198286105817]  

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

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

Tuto teorii si můžeme ověřit napsáním programu, který rozdělí hodnoty do úseků a určí počet výskytů v jednotlivých úsecích, neboli četnost.

9.6 Četnost

Dobrým přístupem pro řešení problémů jako je tento, je rozdělit problém na menší úlohy a rozhlédnout se, zda pro ně neexistují hotová řešení.

V tomto případě chceme procházet seznamem čísel a počítat, kolikrát hodnota zapadne do stanoveného rozsahu. To nám je povědomé. Napsali jsme již program (kap. 8.9), který procházel řetězcem a počítal kolikrát se vyskytlo zadané písmeno.

Můžeme tedy postupovat tak, že opíšeme starý program a přizpůsobíme jej novému problému. Původní program byl:

count = 0
for char in fruit:
    if char == 'a':
        count = count + 1
print(count)

V prvním kroku nahradíme fruit označením list a char označením num. Program to nezmění, bude však čitelnější.

V druhém kroku změníme prověřování. Nezajímá nás výskyt písmen. Chceme vědět, zda se num nalézá mezi hodnotami low a high.

count = 0
for num in list:
    if low < num < high:
        count = count + 1
print(count)

V posledním kroku zapouzdříme upravený kód do funkce zvané inBucket. Jejími parametry budou seznam a hodnoty low a high.

def inBucket(list, low, high):
    count = 0
    for num in list:
        if low < num < high:
            count = count + 1
    return count

Kopírováním a úpravou existujícího programu jsme byli schopni napsat tuto funkci rychle a ušetřit si spoustu času laděním. Této vývojové strategii říkáme srovnávání vzorů (pattern matching). Řešíme-li problém, který jsme již jednou vyřešili, použijeme staré řešení.

9.7 Mnoho kyblíků

Jak roste počet úseků alias kyblíků, tak se program inBuckets stává neohrabanější. Se dvěma kbelíčky to ještě jde:

low = inBox(a, 0.0, 0.5)
high = inBox(a, 0.5, 1)

Se čtyřmi to už je těžkopádnější:

box1 = inBox(a, 0.0, 0.25)
box2 = inBox(a, 0.25, 0.5)
box3 = inBox(a, 0.5, 0.75)
box4 = inBox(a, 0.75, 1.0)

Máme dva problémy. První spočívá v tom, že musíme vytvořit novou proměnnou pro každý výsledek. Druhý v tom, že musíme určit rozsah pro každý kyblík.

Nejprve vyřešíme druhý problém. Je-li numBuckets počet kyblíků, potom podíl pro každý kyblík určíme jako 1.0 / numBuckets.

K výpočtu rozsahu pro jednotlivý kyblík použijeme smyčku. Proměnná smyčky i počítá od 1 do numBuckets-1:

bucketWidth = 1.0 / numBuckets
for i in range(numBuckets):
    low = i * bucketWidth
    high = low + bucketWidth
    print(low, "to", high)

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

Pro numBuckets = 8 je výstup následující:

0.0 to 0.125
0.125 to 0.25
0.25 to 0.375
0.375 to 0.5
0.5 to 0.625
0.625 to 0.75
0.75 to 0.875
0.875 to 1.0

Můžeme se přesvědčit, že každý kyblík má stejné rozpětí čísel, která se nepřekrývají a pokrývají celý rozsah od 0.0 do 1.0.

Nyní přejdeme k prvnímu problému. Potřebujeme uložit osm celých číslel s použitím proměnné smyčky, která je jednu po druhé označí. Asi už nás napadlo: "Seznam!".

Potřebujeme vytvořit seznam košíků mimo smyčku, protože jej budeme potřebovat jenom jednou. Uvnitř smyčky budeme opakovaně volat funkci inBucket a aktualizovat i-tou položku seznamu.

numBuckets = 8
buckets = [0] * numBuckets
bucketWidth = 1.0 / numBuckets
list = randomList(n)
for i in range(numBuckets):
    low = i * bucketWidth
    high = low + bucketWidth
    buckets[i] = inBucket(list, low, high)
print(buckets)

Je docela možné, že nám to nebude chodit. Náprava je docela snadná. Založme soubor count.py a přepišme do něho definice funkcí randomList a inBucket včetně posledního kódu, ze kterého vytvoříme funkci náhradou řádku numBuckets = 8 záhlavím def count(n,b): a provedeme patřičné odsazení následujících řádků. V těle funkce nahradíme název numBuckets parametrem b. Na první řádek skriptu ještě musíme napsat: import random. Soubor uložíme a když v interaktivním módu překladače provedeme volání count(1000, 8), získáme obdobný seznam výskytů:

[138, 124, 128, 118, 130, 117, 114, 131]

Tato čísla jsou docela blízká číslu 125 jak jsme si přáli. Generátor náhodných čísel nám tedy funguje.

9.8 Jednorázové řešení

I když nám tento program chodí, není tak efektivní, jak by mohl být. Pokaždé, když volá funkci inBucket, prochází celým seznamem. S větším počtem kyblíků jde o značný počet cyklů.

Lepší by bylo projít seznamem jednou a pro každou hodnotu spočítat rovnou index kyblíku, do kterého spadá. Až potom zvětšit příslušné počítadlo o 1.

V předchozím odstavci jsme vzali index i a násobili jej rozpětím bucketWidth, abychom zjistili dolní mez pro daný kyblík. Nyní chceme vzít hodnotu v rozsahu od 0.0 do 1.0 a nalézt index kyblíku, kam tato hodnota patří.

Protože tento problém je opačný k předchozímu problému, budeme patrně muset dělit rozpětím bucketWidth místo násobit.

Jelikož bucketWidth =1.0 / numBuckets, bude dělení výrazem bucketWidth stejné jako násobení hodnotou numBuckets. Násobíme-li číslo v rozsahu od 0.0 do 1.0 počtem kyblíků, dostaneme číslo v rozsahu od 0.0 do numBuckets. Po zaokrouhlení na celé číslo dolů dostaneme přesně to, co hledáme – index kyblíku:

numBuckets = 8
buckets = [0] * numBuckets
list = randomList(n)
for i in list:
    index = int(i * numBuckets)    (float to integer)
    buckets[index] = buckets[index] + 1
print(buckets)

Opět vytvoříme soubor, třeba index.py a vložíme do něj kód funkce randomList a opět nahradíme numBuckets záhavím def index(n,b): a příslušně upravíme kód poslední ukázky.

Seznam typu buckets, který obsahuje četnost hodnot v zadaných intervalech, se nazývá histogram.


9.9   Glosář

operátor modulo (modulus operator)
Operátor označovaný znakem % který poskytne zbytek dělení jednoho čísla druhým.
booleovská hodnota (boolean value)
Jsou pouze dvě, True a False. Mají typ bool a jsou výsledkem booleovského výrazu.
booleovský výraz (boolean expression)
Výraz, který je buď pravdivý nebo nepravdivý.
relační operátor (comparison operator)
Jeden z operátorů, který porovnává dvě hodnoty: ==, !=, >, <, >= a <= .
logický operátor (logical operator)
Jeden z operátorů, který spojuje booleovské výrazy: and, or, is a is not.
podmíněný příkaz (conditional statement)
Příkaz, který řídí tok výpočtu v závislosti na nějaké podmínce. V Pythonu se pro podmíněné příkazy používají klíčová slova if, elif a   else.
podmínka (condition)
Booleovský výraz v podmíněném výrazu, který rozhoduje o tom, která větev se provede.
blok (block)
Skupina po sobě jsoucích příkazů se stejným odsazením.
tělo (body)
Blok příkazů ve složeném příkazu pod záhlavím.
větev (branch)
Jedna z možných cest výpočtu určená vyhodnocením podmínky.
řetězená podmínka (chained conditional)
Podmíněné větvení s více než dvěma toky výpočtu. V Pythonu se řetězené podmínky píší pomocí příkazů if ... elif ... else.
vnoření (nesting)
Jedna programová struktura vnořená do druhé, jako je podmíněný příkaz ve větvi jiného podmíněného příkazu.

9.10   Cvičení

  1. Následující číselné výrazy vypočítejte z hlavy a výsledky si ověřte v IPP.

    1. >>>  5 % 2
    2. >>>  9 % 5
    3. >>>  15 % 12
    4. >>>  12 % 15
    5. >>>  6 % 6
    6. >>>  0 % 7
    7. >>>  7 % 0

    Co se stalo s posledním příkladem a proč? Měl-li jste všechny výsledky kromě posledního správně, můžete jít dál. Pokud ne, sestavte si vlastní příklady a pohrávejte si s modulo operátorem tak dlouho, dokud mu zcela neporozumíte.

  2. 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)))
    
    Skladbu skriptu si vysvětlíme v pozdějších kapitolách. Nyní jej použijeme pro osvojení booleovských výrazů. Uložte program do souboru p_and_q.py, importujte jej do IPP a zadej "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)))
    
    Provedeme import do IPP a zadáme booleovský výraz jako řetězec:
     >>>  from truth_table import *
     >>>  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:
    1.   not (p or q)
    2.   p and q
    3.   not (p and q)
    4.   not(p) or not(q)
    5.   not(p) and not(q)

    Které výrazy jsou logicky eqvivalentní?

  3. Následující výrazy zapisujte na příkazovou řádku IPP:
    True or False
    True and False
    not(False) and True
    True or 7
    False or 7
    True and 0
    False or 8
    "happy" and "sad"
    "happy" or "sad"
    "" and "sad"
    "happy" and ""
    
    Analýzujte výstupy. Uměl byste shrnout výsledky pozorování do jednoduchých zásad o používání booleovských výrazů and a or?
  4. Zabalte následující kód do funkce:  dispatch (choice)
    if choice == 'a':
        function_a()
    elif choice == 'b':
        function_b()
    elif choice == 'c':
        function_c()
    else: 
        print("Neplatná volba")
    
    Potom definujte fci function_a, function_b a function_c tak, aby vytiskly zprávu že byly volány. Například:
    def function_a():
        print("function_a was called ...")
    
    Všechny čtyři funkce (dispatch, function_a, function_b, function_c) uložte do souboru ch4e5.py. Na konec skriptu přidejte volání fce dispatch('b'). Výstupem by mělo být:
    function_b was called ...
    Nakonec skript upravte tak, aby uživatel mohl přímo zadávat 'a, b' nebo 'c'. Skript otestujte importem do IPP.
  5. Napište fci is_divisible_by_3, která přijme celé číslo jako argument a podle situace vytiskne "Toto cislo je delitelné tremi" nebo "Toto cislo neni delitelné tremi".

    Nyní napište podobnou fci is_divisible_by_5.

  6. Generalizujte fce, které jste napsal v předchozím cvičení ve funkci is_divisible_by_n(x,n), která přijme dva argumenty a vytiskne zprávu, že první je/není dělitelný druhým. Uložte ji do souboru ch4e7.py. Importujte ji do IPP a vyzkoušejte. Výstup může vypadat takto:
    >>> from ch4e7 import *
    >>> is_divisible_by_n(20,4)
    Yes, 20 is divisible by 4
    >>> is_divisible_by_n(21,8)
    No, 21 is not divisible by 8
    
  7. Jaký bude výstup následujcího kódu?
    if "Ni!":
        print("We are the Knights who say, 'Ni!'")
    else:
        print("Stop it! No more of this!")
    if 0:
        print("And now for something completely different...")
    else:
        print("What´s all this, then?")
    
    Zamyslete se nad výstupy a pokuste se je vysvětlit.

comment up next how to end end