8. Seznamy

1. Vytvoření seznamu
   1. Taxativním výčtem
   2. Funkcí list()
   3. Rekurzí (cap. 11.1.4 - Vnořené seznamy)
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. Náhodná čísla
10. Výskyty náhodných čísel
    1. Seznam náhodných čísel
    2. Vytvoření úseků
11. Četnost výskytů
    1. Traverzování seznamem výskytů
    2. Jednorázové řešení
12. 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 - viz také odst. 11.1.5.

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([])     # kulaté závorky ohraničují argument funkce
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ří objekt typu 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]]         # proměnná     
>>> nested[1]                                # proces
123

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

>>> nested[9-8]                        #  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

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                                 # počítadlo
>>> while i < len(horsemen):
        print(horsemen[i], end=" ")
        i = i + 1
 war famine pestilence death	          # výstup ze smyčky

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

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

Vyhlazením (flatten) seznamu rozumějme eliminaci vložených sekvencí převodem jejich prvků do základního seznamu.
Vyhlazení lze provést s použitím vnořených smyček, komprehence seznamu, rekurze a vestavěných či importovaných funkcí či metod.

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\xbee']
>>> flat_list = list(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, 101]

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: 'int'(or 'float or '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.

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']       # [inclusive : exclusive]
>>> 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 Thonny
>>> for ovoce in fruit:
        print("I like to eat " + ovoce + "s!")
 I like to eat bananas!
 I like to eat apples!
 I like to eat quinces!		

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 zadaných čísel:

>>> numbers = [3, 4, 5]                   # proveďte v Thonny
>>> for elem in range(len(numbers)):
        print(numbers[elem], "-->", numbers[elem]**2, end =", ")
 3 --> 9, 4 --> 16, 5 --> 25,

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

8.9 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í "jednotkové" desetinné číslo j v rozsahu 0 <= j < 1.

>>> import random
>>> x = random.random()
print(x); print(x*3)
 0.4359029716422217              # náhodné číslo   0 <= x < 1   
 1.307708914926665               # náhoené číslo   0 <= x < 3 
            

Více náhodných hodnot můžeme vygenerovat opakovaným voláním funkce random():

no_name.py
import random
def rand(high):                   # high určuje počet volání
    for i in range(high):    
        x = random.random()       # náhodná čísla   0 <= x < 1
        print(x*high, end=' ')    # náhodná čísla   0 <= x < 3*high  

>>> rand(3)
 1.7262996561032347 0.11591785822094725 2.292141024033198

Náhodná čísla mezi nulou a zadanou mezí high, jsme získali násobením generovaných "jednotkový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 v této skladbě:

>>> from random import choice

>>> fokus = 'Petra', 'Pavla', 'Maruš', 'Alenka', 'Věrka'
>>> volba = choice(fokus); volba
 'Alenka'

Každá invokace choice(~) vrátí jeden (náhodně vybraný) prvek ze zadané sekvence (zde fokus).

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

8.10.1   Seznam náhodných čísel

K vytvoření výčtu náhodných čísel, musíme od první chvíle vědět, v jakém rozsahu se generovaná náhodná čísla budou pohybovat 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 n náhodných čísel daného rozsahu (0 inklusive - 1 exclusive).

rand_list.py
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 (frequency).

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.10.2   Vytvoření úseků

Označíme-li počet úseků jménem buckets 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 / buckets.

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

def bucket_witdth(buckets):
    bucketWidth = 1.0 / buckets              # počet úseků
    for i in range(buckets):
        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 buckets = 8 například, jsou (zde inkluzivní) rozsahy mezí následující:

>>> bucket_witdth(8)
 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

Těmto hodnotám by se ideálně měly blížit hodnoty, zastižené dalším zkoumáním v jednotlivých úsecích.

8.11 Četnost výskytů

Chceme procházet vygenerovaným seznamem n náhodných čísel (0 <= x < n) 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.11.1   Traverzování seznamem výskytů

Sestavíme si funkci buckets_a(n,b), kterou vložíme do souboru filled_buckets.py.

Inspirujeme se upravenou sekvencí 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 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) - viz 8.10.1
    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,n_b) potřebovat:

list = randomList(n)                 # seznam náhodných čísel
numBuckets                           # alias n_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 nb.
Když v interaktivní konzole (IDLE, Thonny) 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 1000/8 = 125 (viz 'bucketWidth'), jak jsme si přáli. Generátor pseudonáhodných čísel nám tedy 'tak nějak' funguje.

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

8.12 Cvičení