0 dní v řadě · 0 bodů

Soubory, chyby a knihovny · 22 min

collections a itertools

Hotové nástroje na počítání, seskupování, fronty, dvojice, kombinace a dávky. Méně ručních cyklů a méně chyb.

Hloubka
Úkoly
Lidsky řečeno

Seznam a slovník jsou kladivo a šroubovák. Zvládneš s nimi skoro všechno, ale matku utáhneš lépe klíčem. Modul collections je zásuvka se specializovaným nářadím. Modul itertools je zase běžící pás: položky po něm jedou jedna za druhou a ty jen skládáš stanoviště, která s nimi něco udělají.

Counter: počítání bez podmínek

Kavárna má seznam objednávek a chce vědět, co se prodává. Ručně bys založil slovník, pro každou položku zjišťoval, jestli už v něm je, a přičítal. Counter tohle umí sám.

from collections import Counter

objednavky = ["latte", "espresso", "latte", "čaj", "latte", "espresso", "kakao"]
pocty = Counter(objednavky)

print(pocty)
print(pocty["latte"])
print(pocty["mojito"])
print(pocty.most_common(2))
print(pocty.total())
Výstup
Counter({'latte': 3, 'espresso': 2, 'čaj': 1, 'kakao': 1})
3
0
[('latte', 3), ('espresso', 2)]
7

Counter je slovník, jehož hodnoty jsou počty. Má dvě příjemné vlastnosti: na neznámou položku odpoví nulou místo chyby a most_common vrátí nejčastější položky seřazené od největšího počtu.

Počítadla jde i sčítat a odčítat. Odčítání zahodí všechno, co kleslo na nulu nebo níž.

from collections import Counter

sklad = Counter(mleko=5, kava=3, cukr=1)
prodej = Counter(mleko=2, cukr=4)
dodavka = Counter(kava=10)

print(sklad - prodej)
print(sklad + dodavka)

sklad.subtract(prodej)
print(sklad)
Výstup
Counter({'mleko': 3, 'kava': 3})
Counter({'kava': 13, 'mleko': 5, 'cukr': 1})
Counter({'mleko': 3, 'kava': 3, 'cukr': -3})

Pokud potřebuješ vidět i záporný stav, třeba abys poznal, že se prodalo víc cukru, než bylo na skladě, použij metodu subtract. Ta nic nezahazuje.

Úkol

Nejčastější slova

Napiš funkci nejcastejsi(text, n), která vrátí seznam n nejčastějších slov ve tvaru [(slovo, pocet), ...]. Velikost písmen nerozlišuj, slova jsou oddělená mezerami.

from collections import Counter

def nejcastejsi(text, n):
    return []
Výstup

defaultdict: slovník, který si poradí sám

Chceš zákazníky rozdělit podle měst. U běžného slovníku musíš pokaždé řešit, jestli už pro město existuje seznam. defaultdict dostane při vytvoření „továrnu“, tedy funkci, kterou zavolá, když klíč chybí. Tady je to list, takže chybějící klíč dostane prázdný seznam.

from collections import defaultdict

zakaznici = [("Praha", "Eva"), ("Brno", "Petr"), ("Praha", "Jan"), ("Ostrava", "Iva"), ("Brno", "Ola")]

podle_mesta = defaultdict(list)
for mesto, jmeno in zakaznici:
    podle_mesta[mesto].append(jmeno)

print(dict(podle_mesta))

utrata = defaultdict(int)
for mesto, castka in [("Praha", 300), ("Brno", 120), ("Praha", 80)]:
    utrata[mesto] += castka

print(dict(utrata))
Výstup
{'Praha': ['Eva', 'Jan'], 'Brno': ['Petr', 'Ola'], 'Ostrava': ['Iva']}
{'Praha': 380, 'Brno': 120}
Úkol

Soubory podle přípony

Napiš funkci podle_pripony(soubory), která ze seznamu názvů udělá slovník {pripona: [nazvy]}. Příponu ber od poslední tečky a převeď ji na malá písmena. Názvy v seznamech nech beze změny a v původním pořadí. Každý název tečku obsahuje.

from collections import defaultdict

def podle_pripony(soubory):
    return {}
Výstup

deque a namedtuple

Fronta u pokladny: lidé přicházejí na konec a odcházejí zepředu. Se seznamem to jde přes pop(0), jenže po odebrání prvního prvku se musí všechny ostatní posunout o místo. U milionu položek je to znát. deque (čti „dek“) je struktura stavěná na rychlou práci s oběma konci.

Parametr maxlen z ní navíc udělá okno na posledních pár položek. Co se nevejde, vypadne na druhém konci.

from collections import deque

fronta = deque(["Eva", "Petr"])
fronta.append("Jan")
print(fronta.popleft(), "je na řadě")
print(fronta)

historie = deque(maxlen=3)
for stranka in ["úvod", "ceník", "kontakt", "blog", "košík"]:
    historie.append(stranka)
print(list(historie))
Výstup
Eva je na řadě
deque(['Petr', 'Jan'])
['kontakt', 'blog', 'košík']
Úkol

Klouzavý průměr

Napiš funkci klouzavy_prumer(cisla, okno). Vrátí seznam průměrů přes posledních okno hodnot, a to jen pro pozice, kde je okno celé zaplněné. Pro [1, 2, 3, 4, 5] a okno 3 je výsledek [2.0, 3.0, 4.0].

from collections import deque

def klouzavy_prumer(cisla, okno):
    return []
Výstup

Druhý užitečný typ je namedtuple. Řeší nečitelné bod[0] a bod[1]: je to n-tice, jejíž položky mají jména. Zůstává neměnná a jde rozbalovat jako každá jiná n-tice.

from collections import namedtuple

Polozka = namedtuple("Polozka", ["nazev", "cena", "kusu"])

p = Polozka("káva", 89, 2)
print(p)
print(p.cena * p.kusu)

nazev, cena, kusu = p
print(nazev)

zdrazena = p._replace(cena=99)
print(zdrazena.cena, p.cena)
print(zdrazena._asdict())
Výstup
Polozka(nazev='káva', cena=89, kusu=2)
178
káva
99 89
{'nazev': 'káva', 'cena': 99, 'kusu': 2}

Když budeš chtít měnitelné záznamy, výchozí hodnoty a vlastní metody, je lepší nástroj dataclass z lekce dataclasses a enum.

Kvíz

Co vrátí Counter("aab")["z"]?

Pod kapotou · co je pod kapotou collections

deque je v CPythonu obousměrně propojený seznam bloků o 64 ukazatelích. append, appendleft, pop a popleft jsou O(1) a dokumentace je uvádí jako bezpečné pro více vláken. Cenou je indexace: d[i] uprostřed je O(n), kdežto u list O(1). list.pop(0) a list.insert(0, x) jsou O(n), protože posouvají pole ukazatelů.

Counter plní počty přes C funkci _count_elements, takže je rychlejší než cyklus v Pythonu. most_common(k) používá heapq.nlargest, tedy O(n log k), bez argumentu řadí celé O(n log n). Shody zachovávají pořadí prvního výskytu. Unární +c zahodí nekladné počty, což je stručná normalizace po subtract.

defaultdict volá továrnu v __missing__, a to spouští jen d[k]. Proto get, in ani setdefault chybějící továrnu nevolají.

namedtuple je podtřída tuple s __slots__ = (), instance tedy nemají __dict__ a zabírají stejně jako n-tice. Pole čte C deskriptor _tuplegetter. Protože je to n-tice, platí Polozka("a", 1, 2) == ("a", 1, 2), což v doménovém modelu bývá nechtěné. Pro typované varianty je tu typing.NamedTuple.

OrderedDict ztratil hlavní důvod existence, když běžný dict začal zachovávat pořadí (garantováno od 3.7). Zůstává move_to_end, popitem(last=False) a porovnání citlivé na pořadí, což je přesně sada operací pro LRU cache. ChainMap skládá vrstvy slovníků bez kopírování a hledá v nich popořadě, klasicky ChainMap(cli, env, defaults).

itertools: práce na běžícím pásu

Funkce z itertools většinou nevrátí seznam. Vrátí iterátor, objekt, který další položku vyrobí, až když si o ni řekneš. Díky tomu může být sekvence obrovská, nebo dokonce nekonečná, a paměť se nezaplní. Aby byl výsledek vidět, ukázky ho převádějí přes list().

from itertools import chain, count, cycle, islice

print(list(chain([1, 2], (3, 4), "ab")))

cisla_faktur = count(2601)
print(list(islice(cisla_faktur, 3)))
print(next(cisla_faktur))

for den, kdo in zip(["po", "út", "st", "čt"], cycle(["Eva", "Jan", "Iva"])):
    print(den, kdo)

pas = chain([1, 2], [3])
print(list(pas))
print(list(pas))
Výstup
[1, 2, 3, 4, 'a', 'b']
[2601, 2602, 2603]
2604
po Eva
út Jan
st Iva
čt Eva
[1, 2, 3]
[]
  • chain spojí několik sekvencí za sebe, aniž by je kopíroval.
  • count počítá donekonečna a islice z něj odřízne kousek. Počítadlo si pamatuje, kde skončilo.
  • cycle opakuje dokola, takže střídání služeb vyřeší zip.

Poslední dva řádky ukazují důležitou vlastnost: iterátor se vyčerpá. Podruhé už nedá nic. Když výsledek potřebuješ víckrát, ulož si ho do seznamu.

Další tři funkce řeší věci, které se ručně píšou s pomocnými proměnnými a často s chybou o jedna: průběžný součet, dvojice sousedů a dělení na dávky.

from itertools import accumulate, batched, pairwise

pohyby = [1000, -200, -50, 300]
print(list(accumulate(pohyby)))

teploty = [12, 15, 14, 19]
print([b - a for a, b in pairwise(teploty)])

adresy = ["[email protected]", "[email protected]", "[email protected]", "[email protected]", "[email protected]"]
for davka in batched(adresy, 2):
    print(davka)
Výstup
[1000, 800, 750, 1050]
[3, -1, 5]
('[email protected]', '[email protected]')
('[email protected]', '[email protected]')
('[email protected]',)

batched je novinka Pythonu 3.12. Hodí se všude, kde služba přijímá nejvýš N položek najednou.

Kombinace a seskupování

Eshop prodává trička ve třech velikostech a dvou barvách. Kolik je variant a které? Podobné otázky řeší čtveřice funkcí:

FunkceCo dáváPříklad
product(a, b)každý s každýmvelikost × barva
permutations(x, k)uspořádané výběry, na pořadí záležípořadí na stupních vítězů
combinations(x, k)výběry bez ohledu na pořadídvojice do týmu
combinations_with_replacement(x, k)totéž, prvek se smí opakovatdva kopečky zmrzliny
from itertools import combinations, permutations, product

for velikost, barva in product(["S", "M", "L"], ["bílá", "černá"]):
    print(velikost, barva)

lide = ["Eva", "Jan", "Iva"]
print(list(combinations(lide, 2)))
print(len(list(permutations(lide, 2))))
Výstup
S bílá
S černá
M bílá
M černá
L bílá
L černá
[('Eva', 'Jan'), ('Eva', 'Iva'), ('Jan', 'Iva')]
6

Poslední velký nástroj je groupby. Seskupuje položky podle klíče, ale jen sousedící. Před použitím proto skoro vždy patří seřazení podle téhož klíče.

from itertools import groupby

prodeje = [("Brno", 100), ("Praha", 50), ("Brno", 30)]
mesto = lambda radek: radek[0]

print("bez řazení:")
for klic, skupina in groupby(prodeje, key=mesto):
    print(klic, list(skupina))

print("po seřazení:")
for klic, skupina in groupby(sorted(prodeje, key=mesto), key=mesto):
    print(klic, sum(castka for _, castka in skupina))
Výstup
bez řazení:
Brno [('Brno', 100)]
Praha [('Praha', 50)]
Brno [('Brno', 30)]
po seřazení:
Brno 130
Praha 50

Právě tahle vlastnost se ale hodí, když sousedství něco znamená, třeba u série stejných znaků.

Úkol

Komprese opakování

Napiš funkci zkomprimuj(text), která nahradí každou sérii stejných znaků znakem a délkou série. Z "aaabcc" vznikne "a3b1c2", z prázdného textu prázdný text.

from itertools import groupby

def zkomprimuj(text):
    return text
Výstup
Kvíz

Máš [1, 1, 2, 1]. Kolik skupin vrátí groupby bez řazení?

Kvíz

Do i = chain([1], [2]) zavoláš dvakrát list(i). Co dostaneš podruhé?

Pod kapotou · na co si dát pozor v itertools

Skupina z groupby sdílí zdroj s hlavním iterátorem. Po posunu na další klíč je předchozí skupina prázdná, takže [list(g) for k, g in list(groupby(x))] vrátí samé prázdné seznamy. Materializuj hned uvnitř smyčky.

groupby versus defaultdict. sorted + groupby je O(n log n) a celý vstup drží v paměti. defaultdict je průměrně O(n), ale paměť roste s výsledkem. groupby bez řazení je jediná varianta, která zvládne proud dat s konstantní pamětí, když už je podle klíče seřazený, typicky výstup z SQL s ORDER BY.

Ne všechno je líné. product, combinations a permutations si nejdřív celý vstup načtou do n-tic, takže nekonečný vstup je zablokuje. cycle si ukládá kopii všech prvků. tee bufferuje rozdíl mezi větvemi, a když jednu vyčerpáš před druhou, drží v paměti všechno. Po tee původní iterátor nepoužívej.

islice neumí záporné indexy a k pozici se musí proklikat, takže islice(it, 10**9, None) opravdu projde miliardu položek.

chain.from_iterable je líné zploštění o jednu úroveň a na rozdíl od chain(*x) nerozbaluje vnější sekvenci předem.

Dokumentace itertools má na konci sekci recipes, a co v ní chybí, bývá v balíčku more-itertools.