Subsections

 
5. Datové struktury

Tato kapitola bude věnována dalším datovým typům jazyka Python. Jmenovitě si budeme povídat o seznamech, tuple a slovnících, přičemž si dále rozšíříme znalosti syntaxe různých příkazů.

 
5.1 Seznamy

O seznamech jsme se již zmínili ve čtvrté kapitole, nyní si naše znalosti poněkud rozšíříme. Následuje popis všech metod všech seznamů, metoda je de facto funkce, která se určitým způsobem váže na určitý objekt, při svém zavolání modifikuje pouze tento objekt:

append(x)
Přidá prvek na konec seznamu. Tato metoda je ekvivalentní zápisu a[len(a):] = [x].

extend(L)
Na konec seznamu přidá všechny prvky seznamu L, je ekvivalentní zápisu a[len(a):] = L.

insert(i, x)
Vloží prvek x na pozici i. Argument i znamená index prvku, před který se má nová položka vložit, tudíž a.insert(0, x) vloží prvek na začátek seznamu, zatímco a.insert(len(a), x) na konec (jde o totéž jako a.append(x).

remove(x)
Ze seznamu odstraní daný prvek x, pokud prvků rovných x se v seznamu nachází více, odstraní se první jeho výskyt. Nenajde-li metoda prvek x, dojde k výjimce.

pop([i])
Odstraní prvek na pozici i a vrátí jeho hodnotu. Argument i je nepovinný, jeho vynecháním dojde k odstranění posledního prvku seznamu.

index(x)
Vrátí index prvního prvku seznamu, jehož hodnota je rovna x. Není-li prvek nalezen, dojde k výjimce.

count(x)
Vrátí počet všech výskytů prvků, jejichž hodnota je rovna x. Není-li nalezen žádný prvek, vrátí nulu.

sort()
Seřadí prvky seznamu podle velikosti, přičemž modifikuje původní seznam.5.1

reverse()
Zrevertuje seznam -- první prvek se stane posledním, druhý předposledním atd. Změna se děje opět na původním seznamu.

Následuje příklad ukazující použití jednotlivých metod seznamu.

>>> a = [66.6, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.6), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.6, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.6, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.6]
>>> a.sort()
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]

 
5.1.1 Zásobníky

Pomocí metod append() a pop() lze ze seznamů vytvořit zásobníky. Zásobník je fronta typu LIFO5.2 -- poslední přidaný prvek bude odebrán jako první. Pro přidání prvku na vrchol zásobníku použijeme metodu append(), pro odebrání prvku metodu pop(). Připomeňme si, že metoda pop() bez dalších argumentů vrátí poslední prvek seznamu, čili prvek na vrcholu zásobníku:

>>> zasobnik = [3, 4, 5]
>>> zasobnik.append(6)
>>> zasobnik.append(7)
>>> zasobnik
[3, 4, 5, 6, 7]
>>> zasobnik.pop()
7
>>> zasobnik
[3, 4, 5, 6]
>>> zasobnik.pop()
6
>>> zasobnik.pop()
5
>>> zasobnik
[3, 4]

 
5.1.2 Fronty

Obdobou zásobníků jsou i fronty FIFO5.3 -- první vložený prvek je odebrán jako první. Pro přidání prvku na konec fronty použijeme opět metodu append(), pro odebrání prvního prvku pak metodu pop(), které předáme index 0 (ta tudíž odstraní a vrátí první prvek celého seznamu):

>>> fronta = ["Python", "Perl", "PHP"]
>>> fronta.append("Ruby")
>>> fronta.append("Lisp")
>>> fronta.pop(0)
'Python'
>>> fronta.pop(0)
'Perl'
>>> fronta
['PHP', 'Ruby', 'Lisp']

 
5.1.3 Funkcionální programování v jazyce Python

Python se snaží maximálně ulehčit práci programátorovi, proto již od samého začátku obsahuje některé rysy funkcionálních programovacích jazyků. Jde především o lambda funkce a stručné seznamy.

Lambda funkce lze velmi výhodně používat v součinnosti s funkcemi pro manipulaci se seznamy. Tyto funkce přebírají několik argumentů, z nichž jeden je vždy funkce (většinou lambda funkce) a další seznam.

Začněme funkcí filter(). Její definice vypadá takto: "filter(funkce, sekvence)". Po zavolání s těmito argumenty vrátí sekvenci5.4 stejného typu jako je sekvence. Tato vrácená sekvence bude obsahovat pouze ty prvky původní sekvence, pro které má volání "funkce(prvek)" pravdivou hodnotu. Takto lze třeba napsat konstrukci, která vybere čísla, která nejsou dělitelná dvěma ani třemi:

>>> def f(x): return x % 2 != 0 and x % 3 != 0
...
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]

Naproti tomu funkce "map(funkce, sekvence)" vrátí seznam prvků. Tento seznam je vytvořen z návratových hodnot volání "funkce(prvek)". Funkce map()vlastně přemapuje prvky původní sekvence na nové hodnoty (od tud pochází i její název). Pro výpočet třetích mocnin lze tedy napsat tuto konstrukci:

>>> def cube(x): return x*x*x
...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

Funkci map() můžeme předat i více sekvencí, funkce pak musí mít tolik argumentů, kolik je sekvencí. Během jediného volání pak dostane prvky všech sekvencí najednou. Pokud je jedna sekvence kratší než druhá, předá se místo jejího prvku hodnota None.

Další variantou volání funkce map() je vynechání funkce. To se provede použitím hodnoty None. V tomto případě je použita interní funkce vracející všechny své argumenty jako n-tici.

Pokud zkombinujeme tyto dva speciální případy, získáme volání "map(None, seznam1, seznam2)", které převede dvojici seznamů na seznam dvojic.

>>> seq = range(8)
>>> def mocnina(x): return x*x
...
>>> map(None, seq, map(mocnina, seq))
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49)]

Konečně poslední funkce reduce() s hlavičkou "reduce(funkce, sekvence)", která vrací jedinou hodnotu určitým způsobem reprezentující celou sekvenci. Tuto hodnotu ovlivňuje právě předaná funkce. Té jsou nejprve předány první dva prvky sekvence, ona pro ně vrátí výsledek a následně je opět zavolána tato funkce, předá se jí návratová hodnota předchozího volání spolu s následujícím prvkem atd. Poslední návratová hodnota funkce je použita jako návratová hodnota celé funkce reduce(). Jako příklad může sloužit konstrukce pro součet všech čísel 1 až 10:

>>> def add(x,y): return x+y
...
>>> reduce(add, range(1, 11))
55

Funkce reduce() ošetřuje ještě dva speciální stavy -- obsahuje-li sekvence jediný prvek, je vrácena hodnota tohoto prvku. Je-li sekvence dokonce prázdní dojde k výjimce.

Nakonec si povíme ještě o nepovinném argumentu funkce reduce(), hodnota tohoto argumentu je totiž použita jako počáteční hodnota a funkce je poprvé volána s argumenty počáteční hodnota a první prvek a následuje obvyklý postup. Pokud je sekvence prázdná, je vrácena ona počáteční hodnota:

>>> def sum(seq):
...     def add(x,y): return x+y
...     return reduce(add, seq, 0)
... 
>>> sum(range(1, 11))
55
>>> sum([])
0

5.1.4 Stručný seznam

Aby se Python vyhnul nadměrnému používání funkcí map() a filter(), zavedla se konstrukce nazývaná stručný seznam.

Pomocí stručného seznamu je možné definovat seznam mnohem čistěji, než je tomu v případě výše uvedených funkcí. Každý stručný seznam se skládá z výrazu následovaného klíčovým slovem for a sekvencí. Při vyhodnocení stručného seznamu se prochází sekvencí a její prvky se dosazují do výrazu. Prvky nového seznamu pak tvoří hodnoty tohoto výrazu:

>>> ovoce = ['  banán', '  rajče ', 'protlak  ']
>>> [zbran.strip() for zbran in ovoce]
['banán', 'rajče', 'protlak']
>>> vec = [2, 4, 6]
>>> [x*3 for x in vec]
[6, 12, 18]

Za sekvencí je možné uvést ještě klauzuli if následovanou podmínkou. Pak jsou ze sekvence použity pouze ty prvky, které vyhovují podmínce.

>>> [x*3 for x in vec if x > 3]
[12, 18]
>>> [x*3 for x in vec if x < 2]
[]
>>> [{x: x**2} for x in vec]
[{2: 4}, {4: 16}, {6: 36}]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> [x, x**2 for x in vec]	# CHYBA - jsou vyžadovány závorky
  File "<stdin>", line 1, in ?
    [x, x**2 for x in vec]
               ^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

 
5.2 Příkaz del

Na začátku této kapitoly jsme se dověděli od metodě remove(), která odstraní určitý prvek ze seznamu. Někdy potřebujeme odstranit prvek na určité pozici v seznamu, pak použijeme právě příkaz del. Takto můžeme ze seznamu vymazat dokonce i celou podsekvenci:

>>> a
[-1, 1, 66.6, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.6, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.6, 1234.5]

Příkazem del můžeme také odstranit celé proměnné. Po odstranění této proměnné již nebude možné se na ní odkazovat.

>>> del a
>>> print a
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
NameError: name 'a' is not defined

 
5.3 Tuple a sekvence

V předchozí části jsme poznali, že seznamy a řetězce toho mají mnoho společného, lze je indexovat, používat jejich podsekvence apod. Kromě těchto dvou datových typů Python podporuje ještě další datový typ -- tuple. Tuple si lze představit jako uspořádanou n-tici, jejíž prvky nelze měnit.

Tuple se zapisuje jako n-prvků oddělených čárkou:

>>> t = 12345, 54321, 'ahoj!'
>>> t[0]
12345
>>> t
(12345, 54321, 'ahoj!')
>>> # Tuple mohou být skládány:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'ahoj!'), (1, 2, 3, 4, 5))

Závorky kolem výčtu prvků nejsou povinné, v některých případech se jim však nevyhneme (např. předávání argumentů funkcím). Tuple lze vkládat do sebe, lze používat klasické operace jako indexování prvků a podsekvencí.

Tuple mají mnoho použití (např. páry souřadnic (x, y) atd.). Důležité pro nás je, že jde o neměnný datový typ, tudíž je lze za určitých podmínek použít jako klíče slovníků5.5. Zároveň jejich neměnnost vyžaduje menší režii a tedy i práce s nimi je rychlejší než práce se seznamy.

Existují dva speciální případy tuple -- prázdná tuple (zapisuje se párem prázdných závorek) a tuple o jednom prvku (prvek je následován čárkou, není nutné ho uzavírat do závorky).

Například:

>>> prazdna = ()
>>> singleton = 'ahoj',    # <-- nezapomeňte ukončující čárku
>>> len(prazdna)
0
>>> len(singleton)
1
>>> singleton
('ahoj',)

Operací nazývanou skládání tuple se rozumí přiřazení více prvků jedné proměnné. Tato proměnná pak bude tvořena tuple obsahující tyto prvky.

Opačnou operací je rozklad sekvencí. V tomto případě stojí na levé straně proměnné oddělené čárkou a straně pravé pak tuple obsahující prvky, které budou přiřazeny proměnné:

>>> x, y, z = t

Rozklad sekvencí vyžaduje, aby délka tuple na pravé straně byla stejná jako délka výčtu proměnných na straně levé. Nakonec si všimněte malé asymetrie, zatímco skládání vždy vytvoří tuple, rozklad funguje na libovolnou sekvenci (tj. jak na tuple, tak i na řetězce a seznamy)!

 
5.4 Slovníky

Dalším neméně důležitým datovým typem Pythonu je slovník, někdy nazývaný též asociativní pole. Jde o neuspořádanou množinu dvojic klíč: hodnota. Hodnoty nejsou reprezentovány indexy, ale klíči. Z toho vyplývá, že klíče musí být v rámci jednoho slovníku jedinečné.

Na klíč jsou kladeny určité požadavky. Jde především o neměnnost, klíčem nemůže být žádný proměnný datový typ. Lze tedy použít čísla, řetězce a dokonce tuple, ty však musí opět obsahovat pouze tyto typy. Seznamy nelze jako klíče nikdy použít5.6. Hodnotami ve slovníku mohou být libovolné typy, dokonce opět slovníky.

Slovník v Pythonu zkonstruujeme zápisem dvojic klíč: hodnota mezi složené závorky. Pro vytvoření prázdného slovníku vynecháme zápis hodnot:

>>> slovnik1 = {1: 'jedna', 2: 'dva', 3: 'tri'}
>>> slovnik2 = {}

Slovník je proměnný datový typ, je možné do něj ukládat hodnoty pod zadaným klíčem a číst z něj hodnoty určitého klíče. Příkazem del je dokonce možné smazat pár klíč: hodnota. Pokud do slovníku uložíme novou hodnotu pod klíčem, který již slovník obsahuje, dojde k přepsání hodnoty tohoto klíče. Pokud ze slovníku chceme získat hodnotu neexistujícího klíče, dojde k výjimce.

Slovníky mají i několik metod, které jsou vesměs určeny pro manipulaci s klíči apod. My si uvedeme pouze dvě -- metoda keys(), vrátí seznam všech existujících klíčů použitých ve slovníků (jejich pořadí je vesměs náhodné). Druhá metoda has_key() vrátí logickou jedničku, pokud je klíč, který jí byl předán jako argument, obsažen ve slovníku:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> tel.keys()
['guido', 'irv', 'jack']
>>> tel.has_key('guido')
1

 
5.5 Porovnávání sekvencí a dalších typů

Sekvenční objekty mohou být porovnávány s dalšími sekvencemi. Toto porovnání se děje lexikograficky, nejprve se porovnají první dva prvky, dále další dva atd. Pokud se na nějakém indexu liší, pak tento rozdíl dá výsledek celému porovnání5.7.

Jestliže některé prvky jsou opět sekvenční typy, dojde k dalšímu lexikografickému porovnání. Jestliže je jedna sekvence delší než druhá a ve stejně dlouhé části se shodují, je ta kratší vyhodnocena jako menší. Lexikografické porovnávání řetězců používá ASCII (případně Unicode) kódování.

(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

Porovnávání objektů různých datových typů Python také umožňuje. Pravidla pro toto porovnání se mohou v budoucnu měnit, nicméně je vždy zaručena jednoznačnost porovnání. Různé typy čísel jsou porovnávány s ohledem na jejich číselnou hodnotu.



Footnotes

... seznam.5.1
V anglickém originále je tato vlastnost nazývána "in place sorting"
... LIFO5.2
Anglicky last in -- first out
... FIFO5.3
first in -- first out
... sekvenci5.4
Více o sekvencích dále v této kapitole
... slovníků5.5
O slovnících se dovíme více dále v této kapitole
... použít5.6
Trváme-li na tom, musíme nejprve seznam převést na tuple funkcí tuple() a teprve potom ho použít jako klíč.
... porovnání5.7
Každý pochopí, že jde o známé porovnávání např. řetězců podle velikosti
Viz O tomto dokumentu... kde naleznete informace, jak upozornit na případné chyby.