12. Slovníky

1. Slovníkové operace
2. Slovníkové metody
3. Alias a kopírování
4. Řídké matice
5. Náznaky
6. Čísla typu 'long'
7. Počítání písmen
8. Glosář
9. Cvičení

Dosud poznané složené datové typy – řetězce, seznamy a entice – jsou sekvence, které používají celá čísla jako indexy pro přístup jednotlivým položkám.

Slovníky jsou odlišný složený datový typ. Jsou rovněž složeny z položek, ale každá položka se skládá z dvojice klíč - hodnota. Klíčem může být pouze neměnitelný datový typ, hodnotou libovolný datový typ.

Jako příklad vytvoříme slovník pro překlad anglických slov do španělštiny. Klíči u tohoto slovníku budou řetězce.

Začneme tak, že vytvoříme prázdný slovník, do kterého přidáme párové položky. Prázdný slovník se označuje {}:

>>> eng2sp = {}
>>> eng2sp['one'] = 'uno'

>>> eng2sp['two'] = 'dos'

První přiřazení vytvoří prázdný slovník s názvem eng2sp, další přiřazení přidávají nové položky. Aktuální hodnotu slovníku můžeme vytisknout obvyklým způsobem:

>>> print eng2sp
{'two': 'dos', 'one': 'uno'}

Párové položky jsou oddělené čárkami. Každý pár obsahuje klíč a hodnotu, oddělenou dvojtečkou. Python používá složitý algorimus pro zařazení páru do slovníku. Pro nás bude jednodušší předpokládat, že toto řazení je nepředvídatelné.

Jiným způsobem vytvoříme slovník tak, že přímo zadáme seznam párů klíč-hodnota:

>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}

Na pořadí při zapisování párů nezáleží. Hodnoty ve slovníku jsou přístupné prostřednictvím klíčů, nikoliv indexů a o pořadí se tedy nemusíme starat.

Takto použijeme klíče k vyhledání odpovídající hodnoty:

>>> print eng2sp['two']
'dos'

Klíč 'two' zprostřekuje hodnotu 'dos'

12.1 Slovníkové operace

Příkaz del odstraní dvojici klíč-hodnota ze slovníku. Následující slovník na příklad obsahuje jména různého druhu ovoce a jeho množství na skladě:

>>> inventory = {'apples': 430, 'bananas': 312, 'pears': 217, 'oranges': 525}
>>> print inventory
{'oranges': 525, 'apples': 430, 'pears': 217, 'bananas': 312}

Když někdo skoupí všechny hrušky, můžeme tento vstup ze slovníku vyjmout:

>>> del inventory['pears']
>>> print inventory
{'apples': 430, 'oranges': 525, 'bananas': 312}

Nebo očekáváme-li, že hrušky zase budou, můžeme pouze změnit hodnotu spojenou s hruškami:

>>> inventory['pears'] = 0
>>> print inventory
{'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 0}

U slovníku můžeme také použít funkci len, která vrací počet dvojic klíč-hodnota:

>>> len(inventory)
4

12.2 Slovníkové metody

Slovníky mají řadu užitečných vestavěných metod.

Metoda keys přijme slovník a vrátí seznam jeho klíčů, avšak místo syntaxe pro funkci keys(eng2sp) použijeme syntaxi pro metodu eng2sp.keys().

>>> eng2sp.keys()
['one', 'three', 'two']

Tato forma tečkové notace určuje jméno metody keys a jméno objektu eng2sp, na němž má být metoda použita. Prázdné závorky naznačují, že tato metoda nepřijímá žádné parametry.

Volání metody se nazývá invokace; v tomto případě bychom řekli, že invokujeme metodu keys pro objekt ger2eng.

Metoda values je podobná; vrací seznam hodnot ve slovníku:

>>> eng2sp.values()
['uno', 'tres', 'dos']

Metoda items vrací obojí formou seznamu entic:

>>> eng2sp.items()
[('one', 'uno'), ('three', 'tres'), ('two', 'dos')]

Syntaxe poskytuje užitečnou informaci o typech. Hranaté závorky naznačují, že jde o seznam. Oblé závorky naznačují, že položkami seznamu jsou entice.

Přijímá-li metoda argument, používá stejnou syntaxi jako volání funkce. Na příklad, metoda has_key přijímá klíč a vrací True, jestliže se klíč ve slovníku nachází:

>>> eng2sp.has_key('one')
True
>>> eng2sp.has_key('deux')
False

Pokusíme-li se volat metodu bez udání objektu, dostaneme chybu. V tomto případě nám chybové hlášení příliš nepomůže:

>>> has_key('one')
NameError: name 'has_key' is not defined

12.3 Alias a kopírování

Protože jsou slovníky měnitelné, musíme si dát pozor na aliasování. Kdykoliv dvě proměnné odkazují ke stejnému objektu, jeho změna prostřednictvím jedné proměnné je "viděna" i druhou proměnnou.

Chceme-li měnit slovník a přitom si zachovat kopii originálu, použijeme metodu copy. Například, opposites je slovník, který obsahuje dvojice protikladů:

>>> opposites = {'up': 'down', 'right': 'wrong', 'true': 'false'}
>>> alias = opposites
>>> copy = opposites.copy()

Proměnné alias a opposites odkazují na stejný objekt, proměnná copy odkazuje na čerstvou kopii téhož slovníku. Upravíme-li alias, změní se i opposites:

>>> alias['right'] = 'left'
>>> opposites['right']
'left'

Když naproti tomu upravíme copy, tak se opposite nezmění:

>>> copy['right'] = 'privilege'
>>> opposites['right']
'left'

12.4 Řídké matice

V odstavci 9.18 jsme použili seznam seznamů k prezentaci matice. To je dobrý způsob pro matice s převážně nenulovými hodnotami, uvažme však řídkou matici jako je tato:

Vyjádření matice prostřednictvím seznamu obsahuje množství nul:

matrix = [ [0,0,0,1,0],
           [0,0,0,0,0],
           [0,2,0,0,0],
           [0,0,0,0,0],
           [0,0,0,3,0] ]

Alternativou je použití slovníku. Jako klíče můžeme použít entice, obsahující čísla řádků a sloupců. Zde je slovníkové vyjádření téže matice:

>>> matrix = {(0,3): 1, (2, 1): 2, (4, 3): 3}

Potřebujeme jenom tři dvojice klíč-hodnota pro tři nenulové prvky matice. Každý klíč je entice a každá hodnota je celé číslo.

Prvky matice jsou přístupné pomocí operátoru [ ]:

>>> matrix[0,3]
1

Všimněme si, že vyjádření matice slovníkem má jinou skladbu než vyjádření matice vnořenými seznamy. Místo dvou celočíselných indexů používáme jenom jeden, jímž je entice z celých čísel.

Je zde však jeden problém. Pokusíme-li se ukázat na nulový prvek matice, dostaneme chybu, protože ve slovníku takový klíč uvedený nemáme:

>>> matrix[1,3]
keyerror: (1, 3)

Tento problém řeší metoda get:

>>> matrix.get((0,3), 0)
1

Prvním argumentem je klíč, druhým argumentem je hodnota, kterou má funkce get vrátit, nebude-li zadávaný klíč ve slovníku:

>>> matrix.get((1,3), 0)
0

Metoda get rozhodně zlepšuje přístup k prvkům řídké matice.

12.5 Náznaky

Když jsme si v poslední kapitole pohrávali s funkcí fibonacci, mohli jsme si všimnout, že čím větší argument jsme použili, tím déle trvalo provádění funkce. Se zvětšujícím se argumentem časové nároky velmi rychle rostly. Na jednom z našich počítačů končí fibonacci(20) okamžitě, fibonacci(30) zabere asi vteřinu a fibonacci(40) trvá zhruba věčnost.

Abychom pochopili proč, pohleďme na toto schema volání funkce fibonacci(4):

Schema zobrazuje sadu funkcí v rámečcích se šipkami, ukazujícími na volané funkce. Nejvýše umístěná fce, fibonacci(4) volá fibonacci(3) a fibonacci(2). Fce fibonacci(3) zas volá fibonacci(2) a fibonacci(1). A tak dále.

Spočítejme, kolikrát je voláno fibonacci(0) a fibonacci(1). Je to řešení neefektivní a rychle se zhoršuje při zvětšujícím se argumentu.

Dobrým řešením je ukládat si záznamy o spočítaných hodnotách do slovníku pro potřebu dalšího použití. Takovýmto záznamům říkejme náznaky (hints). Zde vidíme realizaci funkce fibonacci s použitím náznaků:

previous = {0:0, 1:1}

def fibonacci(n):
    if previous.has_key(n):
        return previous[n]
    else:
        new_value = fibonacci(n-1) + fibonacci(n-2)
        previous[n] = new_value
        return new_value

Kdykoli je funkce fibonacci volána, prozkoumá svůj slovník, zda neobsahuje výsledek. Jestliže ano, funkce se může vrátit okamžitě bez jakýchkoli dalších rekurzivních volání. Jestliže ne, musí vypočítat novou hodnotu. Tato nová hodnota je přidána do slovníku před tím, než se funkce vrátí k rekurzivnímu volání.

S použitím této verze náš počítač spočítá fibonacci(100) v jednom oka mžiku.

>>>fibo(100)
354224848179261915075L

Písmeno L na konci čísla oznamuje, že se jedná o "dlouhé" celé číslo typu long.

12.6 Čísla typu 'long'

Python poskytuje typ zvaný long, který umí zacházet s celým číslem jakékoliv velikosti (omezené pouze velikostí paměti na našem počítači).

Hodnotu typu long můžeme vytvořit třemi způsoby. První je ten, že aritmetickým výrazem vypočítáme tak velké číslo, že se nevejde do typu int. Právě jsme to viděli v příkladu s fibonacci(100). Při druhém způsobu přímo zapíšeme celé číslo s písmenem L na konci:

>>> type(1L)
<type 'long int'>

Při třetím způsobu použijeme funkci long k přeměně hodnoty na typ long. Funkce long, stejně jako int a float, přijímají jakýkoli číselný typ, dokonce i číselný řetězec:

>>> long(1)
1L
>>> long(3.9)
3L
>>> long('57')
57L

12.7 Počítání písmen

V odstavci 7.8 jsme napsali funkci, která počítala četnost písmene v řetězci. Obecnější formou tohoto problému je vytvoření histogramu písmen v řetězci, to jest, kolikrát se které písmeno vyskytne.

Takový histogram by mohl být užitečný pro komprimaci textového souboru. Protože se různá čísla vyskytují s různou četností, můžeme soubor komprimovat s použitím kratších kódů pro často se vyskytující písmena a delších kódů pro písmena s menší četností.

Pomocí slovníku vytvoříme histogram elegantním způsobem:

>>> letter_counts = {}
>>> for letter in "Mississippi":
...   letter_counts[letter] = letter_counts.get (letter, 0) + 1
...
>>> letter_counts
{'M': 1, 's': 4, 'p': 2, 'i': 4}

Začínáme prázdným slovníkem. Pro každé písmeno v řetězci zvětšíme aktuální četnost (může být i nula) o 1. Na konci procesu máme slovník obsahující dvojice z písmen a jejich četností.

Bylo by ještě působivější, kdybychom histogram uspořádali podle abecedy. Můžeme to udělat pomocí metod items a sort.

>>> letter_items = letter_counts.items()
>>> letter_items.sort()
>>> print letter_items
[('M', 1), ('i', 4), ('p', 2), ('s', 4)]

Metodu items jsme již poznali, poprvé se ale setkáváme s metodou sort pro seznamy. Existují další metody pro seznamy, včetně append, extend a reverse. Bližší podrobnosti si přečteme v dokumentaci pro Python.

12.8 Glosář

12.9 Cvičení