8. Seznamy

1. Vytvoření seznamu
   1. Taxativním výčtem
   2. Funkcí list()
2. Přístup k položkám
3. Traverzování seznamem
4. Smazání položek
5. Operace se seznamy
   1. Operace pro seznamy a řetězce
   2. Metody a funkce pro seznamy
   3. Příslušnost položky
   4. Vyhlazení seznamu
6. Úseky seznamu
7. Seznamy jsou měnitelné
8. Seznamy a smyčky 'for'
9. Testem podnícený rozvoj
10. Náhodná čísla
11. Výskyty náhodných čísel
    1. Seznam náhodných čísel
    2. Vytvoření úseků
12. Četnost výskytů
    1. Traverzování seznamem výskytů
    2. Jednorázové řešení
13. Glosář
14. Cvičení

Seznam (list) je uspořádaná (tudíž indexovatelná) kolekce hodnot stejného i rozdílného typu. Jednotlivým hodnotám říkáme položky a tyto položky jsou měnitelné - na rozdíl od jejich pořadí, které měnitelné není; lze však měnit počet položek v seznamu.
Položkou seznamu může být i další seznam. Takový seznam se nazyvá vnořený seznam.

8.1 Vytvoření seznamu

8.1.1   Taxativním výčtem

Nový seznam vytvoříme nejjednodušeji uzavřením položek do hranatých závorek:

[10, 20, 30, 40]                 # seznam se 4 čísly               
["spam", "bungee", "swallow"]    # 3 řetězce 
["hello", 2.0, 5, [10, 20]]      # řetězec, 2 čísla, seznam     

Při práci se seznamem je důležité si uvědomit, že numerické typy (Kap. 2.2) představují jedinou hodnotu (singleton), složené datové typy (string, list, ...) mohou obsahovat žádnou, jednu, či více hodnot.

Seznamu uvnitř jiného seznamu říkáme, že je vnořený (nested). Vnořených seznamů může být v seznamu i více a to i nestejné délky, případně může seznam obsahovat prvky různých typů:

mli = [("a", 5.2), [7, True], range(5), "pešek", {2.5, 2},
        b'R\xc5\xaf\xc5\xbe']

Konečně, existuje speciální seznam, který neobsahuje žádné položky. Nazývá se prázdný seznam a značí se [ ].

Stejně jako číselná hodnota 0 a prázdný řetězec, je prázdný seznam nepravdivý v booleovských výrazech:.

>>> bool(["hello", 2.0])
True
>>> bool([])
False

Vytvořený seznam můžeme samozřejmě přiřadit k proměnné nebo zadat jako parametr či argument funkce.

>>> vocabulary = ["ameliorate", "castigate", "defenestrate"]
>>> numbers = [17, 123]
>>> empty = []
>>> print(vocabulary, numbers, empty)
['ameliorate', 'castigate', 'defenestrate'] [17, 123] []

8.1.2   Funkcí list()

Funkce list(~) vytvoří seznam z argumentů typu string, bytes, bytearray, tuple, range, dict, set, frozenset, jejichž společnou vlastností je to, že to jsou všechno iterábly - viz Kap. 3.1.

>>> list("osel")                         # typ str
['o', 's', 'e', 'l']
>>> list(b"osel")                        # typ bytes
[111, 115, 101, 108]
>>> list(("a", 5, True))                 # typ tuple
['a', 5, True]
>>> list(range(4))                       # typ range
[0, 1, 2, 3]
>>> list({"a", 5, True})                 # typ set
[True, 5, 'a']
>>> list({"a":2, "b":False, "c":"d"})    # typ dict
['a', 'b', 'c']  

Při práci se seznamem s výhodou použijeme komprehenci seznamu (potažmo iteráblu) - viz odstavec 3.5.

8.2 Přístup k položkám

Syntaxe pro přístup k položkám seznamu je stejná jako syntaxe pro přístup ke znakům řetězce – pomocí hranatých závorek s indexem. Nezapomeňte, že indexy začínají nulou:

>>> nested = ["hello", 123, [10,20]]
>>> nested[1]
123

Jako index lze použít jakýkoli celočíselný výraz (integer):

>>> nested[9-8]              #  == 1
123
>>> nested[1.0]              # lze zapsat: nested[int(1.0)] 
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
TypeError: list indices must be integers

Pokusíme-li se číst nebo psát položku, která neexistuje, dostaneme chybu při běhu programu:

>>> nested[3]
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
IndexError: list index out of range   

Má-li index zápornou hodnotu, počítá se od konce seznamu:

>>> nested[-1]
[10, 20]
>>> nested[-3]
'hello'
>>> nested[-4]
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
IndexError: list index out of range    

nested[-1] je poslední položka seznamu, nested[-4] je mimo rozsah (range).

Pro prvek vnořeného seznamu uvedeme rovněž jeho index:

>>> nested[2][1]
20

Je obvyklé použít proměnnou jako index seznamu:

horsemen = ["war", "famine", "pestilence", "death"]

i = 0                  # proměnná pro smyčku - počítadlo
while i < 4:
    print(horsemen[i], end=" ")
    i = i + 1

Tato smyčka počítá od 0 do 4. Jakmile má proměnná hodnotu 4, podmínka nevyhoví a smyčka končí. Takže tělo smyčky je provedeno pro i = 0, 1, 2 a 3.

Při každém cyklu smyčky je proměnná i použita jako index položky, která se tiskne. Tento způsob výpočtu se nazývá traverzování seznamem.

8.3 Traverzování seznamem

Vestavěná funkce len vrací délku seznamu, což je počet jeho položek. Tato hodnota se výhodně používá jako horní mez smyčky místo konstanty. Tím si zajistíme, že pokaždé, když se změní velikost seznamu, nemusíme procházet programem, abychom opravili všechny dotčené smyčky:

>>> horsemen = ["war", "famine", "pestilence", "death"]
>>> i = 0
>>> while i < len(horsemen):
        print(horsemen[i], end=" ")
        i = i + 1
 war famine pestilence death		

I když jeden seznam může obsahovat další seznam, ten vnořený se stále počítá jako jedna položka. Délka tohoto seznamu je 4:

['spam!', 1, ['Brie', 'Roquefort', 'Pol le Veq'], [1, 2, 3]]

Traverzování i vnořeným seznamem popisuje text kap. 11.1.4

8.4 Smazání položek

K výmazu položky ze seznamu použijeme příkaz del. Nepřekvapí nás, že del manipuluje také se zápornými indexy a vyvolá chybu při běhu programu, je-li index mimo dovolený rozsah:

>>> a = ['one', 'two', 'three']
>>> del a[1]; a
['one', 'three']
>>> del a[-1]; a
['one'] 

Jako indexy pro del můžeme použít také úseky:

>>> a_list = ['a', 'b', 'c', 'd', 'e', 'f']
>>> del a_list[1:5]
>>> print(a_list)
['a', 'f']

Jako obvykle, úseky vyberou všechny položky zadaného rozsahu, kromě horní meze.

8.5 Operace se seznamy

8.5.1   Operace pro seznamy a řetězce

Operátor + zřetězí seznamy:

>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> c = a + b
>>> print( c )
[1, 2, 3, 4, 5, 6]

Podobně, operátor * opakuje seznam v zadaném počtu:

>>> [0]*4
[0, 0, 0, 0]
>>> [1, 2, 3]*3
[1, 2, 3, 1, 2, 3, 1, 2, 3]

První příklad opakuje [0] čtyřikrát. Druhý příklad opakuje seznam [1, 2, 3] třikrát.

8.5.2   Metody a funkce pro seznamy

Pro seznamy neexistuje modul list jako existuje modul string pro řetězce.

Metody - viz text Python List Methods:

append, clear, copy, count, extend, index, insert, pop,
remove, reverse, sort     

Funkce

filter(), list(), range(), slice(), sorted()
len(), max(), min()     # společné pro všechny iterábly 

8.5.3   Příslušnost položky

Klíčové slovo in je booleovský operátor, který testuje příslušnost prvku k sekvenci. Použili jsme jej už u řetězců a pracuje také se seznamy a s jinými uspořádanými množinami:

>>> horsemen = ['war', 'famine', 'pestilence', 'death']
>>> 'pestilence' in horsemen
True
>>> 'debauchery' in horsemen
False

Protože pestilence je částicí seznamu horsemen, vrátí operátor in hodnotu True. Jelikož debauchery v seznamu není, vrátí False.

Můžeme použít slovo not ve spojení s in, abychom ověřili, že položka není částicí seznamu:

>>> 'debauchery' not in horsemen
True

8.5.4   Vyhlazení seznamu

Nejúčinější způsob je použití metody .chain z modulu itertools:

>>> from itertools import chain

>>> mli = [(2.5, 12, 3+2j), ("a", 5.2), [7, True], range(5), "pešek", {2.5, 2}, b'R\xc5\xaf\xc5\xbe']

>>> flat_list = list(itertools.chain(*mli))
>>> print('Flat_list =', flat_list)

Flat_list = [2.5, 12, (3+2j), 'a', 5.2, 7, True, 0, 1, 2, 3, 4, 
'p', 'e', 'š', 'e', 'k', 2.5, 2,  82, 197, 175, 197, 190]

Jak vidno z ukázky, tento postup odstraní vložené seznamy, entice a sety, jakož i převede sekvenci bajtů na sekvenci kódových bodů utf-8.
Nevýhodou je, že při výskytu solitérních numerických hodnot v základním seznamu je hlášena chyba TypeError: 'float' (int, complex) object is not iterable.
Tuto nevýhdu lze eliminovat vložením 'závadných' prvků do seznamu či entice, tak jak jsme právě učinili.

Pokud stojíme o zachování sekvence bajtů, můžeme použít tento postup:

>>> def flatten(obj):
        if isinstance(obj, list):
            for item in obj:
                yield from flatten(item)
        else: yield obj

>>> print(list(flatten(mli)))
[2.5, 12, (3+2j), ('a', 5.2), 7, True, range(0, 5), 'pešek', {2.5, 2}, b'R\xc5\xaf\xc5\xbe']

Jak vidno, tento postup zvládne solitérní numerické hodnoty a rozbalí vložený list ale to je vlastně všechno, co umí.

8.6 Úseky seznamu

Operace s úseky, které jsme poznali u řetězců, platí také u seznamů:

>>> a_list = ['a', 'b', 'c', 'd', 'e', 'f']
>>> a_list[1:3]
['b', 'c']
>>> a_list[:4]
['a', 'b', 'c', 'd']
>>> a_list[3:]
['d', 'e', 'f']
>>> a_list[:]
['a', 'b', 'c', 'd', 'e', 'f']

8.7 Seznamy jsou měnitelné

Na rozdíl od řetězců jsou seznamy měnitelné, což znamená, že můžeme měnit jejich položky. Použitím závorkového operátoru [ ] můžeme měnit hodnotu položek:

>>> fruit = ["banana", "apple", "quince"]
>>> fruit[0] = "pear"
>>> fruit[-1] = "orange"
>>> print(fruit)
['pear', 'apple', 'orange']

Přiřazení hodnoty položce seznamu se nazývá položkové přiřazení (item assignment).:

>>> my_list = ['T', 'E', 'S', 'T']
>>> my_list[2] = 'X'
>>> my_list
['T', 'E', 'X', 'T']

Úsekovým operátorem můžeme změnit několik položek najednou:

>>> a_list = ['a', 'b', 'c', 'd', 'e', 'f']
>>> a_list[1:3] = ['x', 'y']
>>> print(a_list)
['a', 'x', 'y', 'd', 'e', 'f']

Můžeme také odstranit položky ze seznamu tím, že je nahradíme prázdným seznamem:

>>> a_list = ['a', 'b', 'c', 'd', 'e', 'f']
>>> a_list[1:3] = []
>>> print(a_list)
['a', 'd', 'e', 'f']

A můžeme také přidat položky do seznamu v zadaném místě:

>>> a_list = ['a', 'd', 'f']
>>> a_list[1:1] = ['b', 'c']
>>> print(a_list)
['a', 'b', 'c', 'd', 'f']
>>> a_list[4:4] = ['e']
>>> print(a_list)
['a', 'b', 'c', 'd', 'e', 'f']

8.8 Seznamy a smyčky 'for'

Interní mechanizmus smyčky for - viz kap 5.3. Použití smyčky for je velmi rozmanité, např.:

fruit = ["banana", "apple", "quince"]     # proveďte v IDLE
for ovoce in fruit:
    print("I like to eat " + ovoce + "s!") 

Měnitelnost seznamu nám umožňuje při jeho procházení (traverzování) upravit každou jeho položku. Následující kód vytvoří druhé mocniny čísel od 1 do 3:

numbers = [1, 2, 3]
for elem in range(len(numbers)):
  print(numbers[elem], "-->", numbers[elem]**2, end =", ")

Výstup v IDLE:

======== RESTART: F:/Codetest/HowTo/trump_one.py ========
1 --> 1, 2 --> 4, 3 --> 9, 

Zamyslete se nad příkazem range(len(numbers)) a snažte se pochopit, jak tento příkaz pracuje. Uvnitř seznamu nás zajímá jak původní hodnota položky, tak i její změněná hodnota.

Funkce enumerate generuje při traverzování seznamem jak index, tak i odpovídající hodnotu. Pro lepší pochopení práce příkazu enumerate si vyzkoušejte následující příklad:

>>> for index, value in enumerate(['banana', 'apple', 'pear']):
...     print(index, value )
...
0 banana
1 apple
2 pear
>>>    

Jiné příklady využití funkce enumerate() - viz kap. 5.7.

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

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()
	
Poznámka: záhlaví a závěr skriptu nejsou v dalších úkázkách
z úsporných důvodů uváděny.	

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

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

Ř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í.

Alternativní řešení téže úlohy má tuto skladbu:

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]]
    """
    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:

• pomáhá nám konkrétně přemýšlet o problému před tím, než se jej pokusíme řešit
• pobízí nás k rozložení složitého problému do menších, jednodušších úloh, postupně řešitelných
• vhodně rozvinutý testovací aparát usnadňuje pozdější přídavky a vylepšení

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

def add_matrices (m1, m2):
    mx = make_matrix(len(m1), len(m1[0]))

8.10 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.

>>> import random
>>> x = random.random(); print(x)
0.6046175579100934            # jedno pseudo-náhodné číslo 

Více náhodných hodnot můžeme vygenerovat pomocí funkce se smyčkou:

import random
def rand(high):              # high je celé číslo
    for i in range(high):    
        x = random.random()  # náhodné číslo v rozsahu [0.0, 1.0)
        print(x*high, end=' ')

>>> rand(5)
4.161282917198089 0.2165885838598547 4.654892519196209 0.03348629706460993 3.686099655738407 

Náhodná čísla mezi nulou a zadanou mezí high, jsme získali 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
Každá invokace choice(~) vrátí jeden prvek ze zadané kolekce:

>>> from random import choice

>>> fokus = [("a"*3), "verpánek", {12, sum, True}]
>>> choice(fokus), choice(fokus), choice(fokus)
('verpánek', 'aaa', {<built-in function sum>, 12, True})
                               # 'aaa' je rozbalené ("a"*3)
>>> pokus = ("a"*3), "verpánek", {12, sum, True}
choice(pokus), choice(pokus), choice(pokus)
('aaa', 'aaa', {True, <built-in function sum>, 12})

Jak vidno, výběrová kolekce je typu list a tuple. Typem set být nemůže, protože objekt typu set není indexovatelný (subscriptable).

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

8.11.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.

import random
def randomList(n):    
    s = [0] * n                    # počáteční seznam s nulami
    for i in range(n):             
        s[i] = random.random()     # náhrada nuly za náhodné číslo
    return s                       # seznam 'n' náhodných čísel

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

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

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ý.

8.11.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):

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

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

8.12 Č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á.

8.12.1   Traverzování seznamem výskytů

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.13.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. 8.12.2) aktuálního úseku.
Za tím účelem doplníme smyčku for ... o podmínku if:

count = 0
for num in list:         # list vytvoříme funkcí randomList(n)
    if low < num < high:
        count = count + 1
print(count)

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.

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

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:

list = randomList(n)                 # seznam náhodných čísel
numBuckets                           # alias b: počet úseků 
výskyty = [0] * numBuckets           # počáteční seznam s nulami
bucketWidth = 1.0 / numBuckets       # číselný rozsah jednoho intervalu
for i in range(numBuckets):          
    low = i * bucketWidth            # dolní mez intervalu
    high = low + bucketWidth         # horní mez intervalu
    výskyty[i] = inBucket(list, low, high)    
print(výskyty)     

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

[138, 124, 128, 118, 130, 117, 114, 131]      # SUMA = 1000

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.

8.12.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.

Vytvořenou funkci buckets_b(n,b) rovněž přidáme do souboru buckets.py.

def buckets_b(n,b):
    výskyty = [0] * b                         # akumulátor
    list = randomList(n)                      # volání funkce
    for i in list:
        index = int(i * b)                    # zaokrouhlení dolů          
        výskyty[index] = výskyty[index] + 1
    print(výskyty)

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

[111, 132, 144, 127, 114, 123, 130, 119]      # SUMA = 1000

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?

8.13 Glosář

8.14 Cvičení