0 dní v řadě · 0 bodů

Datové struktury · 24 min

Slovníky

Najdeš hodnotu podle jména místo pozice, spočítáš výskyty, seskupíš data a poradíš si s chybějícími klíči.

Hloubka
Úkoly
Lidsky řečeno

Šatna v divadle. Dáš kabát a dostaneš lístek s číslem. Po představení šatnářka neprohledává všechny kabáty, podívá se na lístek a jde přímo k věšáku. Slovník v Pythonu funguje stejně: k hodnotě se dostaneš přes klíč, a je jedno, kolik věcí je uvnitř.

Hledání podle jména

Kavárna má ceník. Se seznamy bys potřeboval dva, jeden s názvy a druhý s cenami, a hlídat, aby si odpovídaly. Slovník (anglicky dictionary, v Pythonu dict) drží oboje v párech. Píše se do složených závorek ve tvaru klíč: hodnota.

nazvy = ["espresso", "cappuccino", "čaj"]
ceny = [55, 72, 48]
print(ceny[nazvy.index("čaj")])

cenik = {"espresso": 55, "cappuccino": 72, "čaj": 48}
print(cenik["čaj"])
print(len(cenik))
print(cenik)
Výstup
48
48
3
{'espresso': 55, 'cappuccino': 72, 'čaj': 48}

Druhý zápis se čte skoro jako věta: cena čaje. Klíč je obvykle text nebo číslo, hodnota může být cokoli. len vrátí počet párů. Prázdný slovník je {}.

Když klíč chybí

Hranaté závorky trvají na tom, že klíč existuje. Jinak program skončí chybou KeyError.

cenik = {"espresso": 55, "čaj": 48}

print(cenik["espresso"])
print(cenik["kakao"])
Výstup
55

Pokud s chybějícím klíčem počítáš, máš dvě možnosti. Metoda get vrátí None nebo náhradní hodnotu, kterou jí zadáš. Operátor in se zeptá, jestli klíč existuje.

cenik = {"espresso": 55, "čaj": 48}

print(cenik.get("čaj"))
print(cenik.get("kakao"))
print(cenik.get("kakao", 0))

print("kakao" in cenik)
print("čaj" in cenik)
print(48 in cenik)
Výstup
48
None
0
False
True
False

Přidání, změna, smazání

Přiřazení do hranatých závorek klíč vytvoří. Pokud už existuje, přepíše jeho hodnotu, protože každý klíč je ve slovníku nejvýš jednou. del smaže pár a pop ho vyjme a vrátí hodnotu. Operátor | spojí dva slovníky do nového a při shodě klíčů vyhraje ten pravý, což je ideální pro výchozí nastavení.

sklad = {"jablka": 40, "hrušky": 12}

sklad["švestky"] = 25
sklad["jablka"] = 35
sklad["hrušky"] -= 2
print(sklad)

del sklad["švestky"]
vzato = sklad.pop("hrušky")
print(vzato, sklad)
print(sklad.pop("banány", 0))

vychozi = {"jazyk": "cs", "tema": "tmavé", "pismo": 14}
moje = {"tema": "světlé"}
print(vychozi | moje)
Výstup
{'jablka': 35, 'hrušky': 10, 'švestky': 25}
10 {'jablka': 35}
0
{'jazyk': 'cs', 'tema': 'světlé', 'pismo': 14}
Kvíz

Co vypíše print({"a": 1, "b": 2, "a": 3})?

Úkol

Účet v kavárně

Projdi objednavka. Do celkem sečti ceny položek z ceníku. Položky, které v ceníku nejsou, přidej do seznamu nezname, program kvůli nim nesmí spadnout.

cenik = {"espresso": 55, "cappuccino": 72, "čaj": 48}
objednavka = ["espresso", "čaj", "dort", "espresso"]

celkem = 0
nezname = []

# doplň
Výstup

Procházení

Cyklus přes slovník dává klíče. Metoda items dává dvojice klíč a hodnota, které rozbalíš stejně jako v lekci o n-ticích. values dá jen hodnoty. Pořadí je to, v jakém se klíče do slovníku dostaly.

hodiny = {"pondělí": 8, "úterý": 6, "středa": 9}

for den in hodiny:
    print(den)

for den, pocet in hodiny.items():
    print(f"{den}: {pocet} h")

print(sum(hodiny.values()))
print(max(hodiny.values()))
print(sorted(hodiny))
print(list(hodiny.keys()))
Výstup
pondělí
úterý
středa
pondělí: 8 h
úterý: 6 h
středa: 9 h
23
9
['pondělí', 'středa', 'úterý']
['pondělí', 'úterý', 'středa']

Hodnoty existujících klíčů můžeš při procházení měnit bez obav. Přidávat nebo mazat klíče ale nesmíš, Python to pozná a skončí.

sklad = {"jablka": 0, "hrušky": 12, "švestky": 0}

for nazev, pocet in sklad.items():
    if pocet == 0:
        del sklad[nazev]
Výstup

Oprava je jednoduchá: projdi kopii, tedy for nazev, pocet in list(sklad.items()):.

Dva vzory, které použiješ pořád

Počítání výskytů. Slovník drží, kolikrát už jsi co viděl. get(klic, 0) vyřeší první výskyt, kdy klíč ještě neexistuje. Nejčastější položky pak zjistíš přes dvojice (počet, slovo), které se řadí podle počtu.

text = "pes kočka pes ryba kočka pes"

pocty = {}
for slovo in text.split():
    pocty[slovo] = pocty.get(slovo, 0) + 1
print(pocty)

dvojice = []
for slovo, pocet in pocty.items():
    dvojice.append((pocet, slovo))
print(sorted(dvojice, reverse=True))
Výstup
{'pes': 3, 'kočka': 2, 'ryba': 1}
[(3, 'pes'), (2, 'kočka'), (1, 'ryba')]
Úkol

Sčítání hlasů

Do slovníku pocty spočítej hlasy pro každé jméno. Do vitez ulož jméno s nejvíce hlasy.

hlasy = ["Eva", "Adam", "Eva", "Bára", "Eva", "Adam"]

# doplň
Výstup

Seskupování. Pod každým klíčem leží seznam a ty do něj přidáváš. Nejdřív se musí založit. Metoda setdefault to zvládne v jednom kroku: vrátí seznam pod klíčem, a když tam není, vloží tam prázdný.

zaci = [("Eva", "4.A"), ("Petr", "4.B"), ("Lída", "4.A"), ("Ota", "4.C")]

tridy = {}
for jmeno, trida in zaci:
    if trida not in tridy:
        tridy[trida] = []
    tridy[trida].append(jmeno)
print(tridy)

stejne = {}
for jmeno, trida in zaci:
    stejne.setdefault(trida, []).append(jmeno)
print(stejne == tridy)
Výstup
{'4.A': ['Eva', 'Lída'], '4.B': ['Petr'], '4.C': ['Ota']}
True
Úkol

Úklid složky

Roztřiď soubory podle přípony do slovníku podle_pripony. Klíč je přípona bez tečky, hodnota seznam názvů v původním pořadí. Pozor, archiv.tar.gz má příponu gz.

soubory = ["foto.jpg", "cv.pdf", "pes.jpg", "archiv.tar.gz", "smlouva.pdf"]

# doplň
Výstup

Co může být uvnitř

Hodnotou může být seznam i další slovník. Takhle vypadají data z webových služeb ve formátu JSON. Čteš je patro po patře.

Klíč musí být neměnný: text, číslo nebo n-tice. N-tice se hodí na souřadnice. Seznam jako klíč skončí chybou TypeError: unhashable type: 'list'.

zakaznik = {
    "jmeno": "Eva Malá",
    "adresa": {"mesto": "Brno", "psc": "60200"},
    "objednavky": [1042, 1077],
}

print(zakaznik["adresa"]["mesto"])
zakaznik["objednavky"].append(1100)
print(len(zakaznik["objednavky"]))

sedadla = {(1, 1): "Eva", (1, 2): "Petr"}
print(sedadla[(1, 2)])
print(sedadla.get((5, 5), "volno"))
Výstup
Brno
3
Petr
volno
Kvíz

Který z těchto slovníků skončí chybou?

Pod kapotou · hashovací tabulka a její hrany

Slovník je hashovací tabulka. Z klíče se spočítá hash(klic), ten určí pozici a shoda se ověří přes identitu a ==. Proto je vyhledávání v průměru O(1) nezávisle na velikosti, v nejhorším případě při kolizích O(n).

Od CPythonu 3.6 je tabulka kompaktní: řídké pole indexů ukazuje do hustého pole záznamů v pořadí vložení. Ušetří to paměť a pořadí dává zadarmo, od 3.7 je garantované jazykem. Kolize se řeší otevřeným adresováním s pseudonáhodným sondováním. Tabulka roste při vkládání, když dojde kapacita daná poměrem zhruba 2/3. Mazání nechává náhrobky a slovník nezmenšuje.

Kontrakt: když a == b, musí platit hash(a) == hash(b). Důsledek, který překvapí:

d = {1: "int", 1.0: "float", True: "bool"}
print(d)
print(hash(1) == hash(1.0) == hash(True))
print(hash(-1) == hash(-2))
Výstup
{1: 'bool'}
True
True

Klíč zůstal první, hodnota poslední. A -1 se hashuje stejně jako -2, protože -1 je v C API vyhrazené pro chybu.

Co hlídat v produkci:

  • Hash textů je pro každý proces náhodně osolený (SipHash, PEP 456, od 3.11 varianta 1-3) jako obrana proti záměrným kolizím. Proto se hash("a") mezi běhy liší a nesmí se ukládat. Řídí to PYTHONHASHSEED. Celá čísla se hashují na sebe a náhodnost se jich netýká.
  • d.get("retry") nerozliší chybějící klíč od uložené None. Když na tom záleží, použij in nebo vlastní zarážku MISSING = object().
  • if d.get("limit"): je nepravda i pro 0. Tichá chyba v načítání konfigurace.
  • dict.fromkeys(klice, []) dá všem klíčům jeden sdílený seznam.
  • setdefault(k, []) vyrobí nový seznam při každém volání, i zbytečně. V horké smyčce nebo pro čitelnost je lepší collections.defaultdict, na počítání Counter. Obojí je v lekci collections a itertools.
  • keys() a items() jsou živé pohledy a umí množinové operace: a.keys() & b.keys() dá společné klíče bez kopírování celých slovníků.
  • Porovnání == u dict pořadí ignoruje, u OrderedDict mezi sebou ne.

Vyzkoušej si: Jak slovník hledá klíč

Vkládej klíče do zjednodušené hashovací tabulky a sleduj, kam padnou, kdy dojde ke kolizi a kdy se tabulka zvětší. Je to model, skutečný slovník v Pythonu je dopracovanější.