Lidsky řečeno
Představ si tři šatny. V první visí kabáty bez ladu a skladu a šatnářka prochází jeden po druhém, dokud nenajde ten tvůj. Ve druhé jsou seřazené podle jména, takže šatnářka jde doprostřed a pokaždé půlku řady vyřadí. Ve třetí máš lístek s číslem a jde rovnou k věšáku. S dvaceti kabáty je to jedno. S dvaceti tisíci stojí fronta z první šatny až na ulici. Tahle lekce ukazuje, jak poznat, ve které šatně právě pracuje tvůj program.
Počítej kroky, ne sekundy
Pořadatel koncertu má seznam prodaných vstupenek a u dveří ověřuje, jestli číslo od návštěvníka v seznamu je. Kolik práce to dá?
Stopky by odpověděly špatně: stejný kód běží jinak na starém notebooku a jinak na serveru. Spolehlivější je spočítat kroky, tedy kolikrát musel program něco porovnat.
prodane = list(range(1, 1001)) # vstupenky číslo 1 až 1000
hledana = 1000
kroky = 0
for cislo in prodane:
kroky += 1
if cislo == hledana:
break
print("Porovnání:", kroky)
Porovnání: 1000
Přesně tohle dělá i krátký zápis hledana in prodane. Nevypadá jako cyklus, ale uvnitř prvek po prvku prochází celý seznam. Teď zvětšíme data a budeme hledat vstupenku, která neexistuje. To je nejhorší případ: program musí projít úplně všechno, než si může být jistý.
for velikost in [10, 100, 1_000, 10_000, 100_000]:
prodane = list(range(velikost))
hledana = -1 # takové číslo nikdo nemá
kroky = 0
for cislo in prodane:
kroky += 1
if cislo == hledana:
break
print(f"{velikost:>7} vstupenek: {kroky:>7} porovnání")
10 vstupenek: 10 porovnání
100 vstupenek: 100 porovnání
1000 vstupenek: 1000 porovnání
10000 vstupenek: 10000 porovnání
100000 vstupenek: 100000 porovnáníDesetkrát víc dat, desetkrát víc práce. To zní férově. Horší je jiná otázka: neprodal někdo stejnou vstupenku dvakrát? Dá se to řešit dvěma způsoby a tady se začnou dít věci.
for pocet in [100, 200, 400, 800]:
vstupenky = list(range(pocet)) # všechny různé, to je nejhorší případ
# Způsob 1: porovnej každou s každou další
kroky_dvojice = 0
for i in range(pocet):
for j in range(i + 1, pocet):
kroky_dvojice += 1
if vstupenky[i] == vstupenky[j]:
print("duplicita")
# Způsob 2: pamatuj si v množině, co už prošlo
kroky_mnozina = 0
videne = set()
for cislo in vstupenky:
kroky_mnozina += 1
if cislo in videne:
print("duplicita")
videne.add(cislo)
print(f"{pocet:>4} vstupenek: dvojice {kroky_dvojice:>7}, množina {kroky_mnozina:>4}")
100 vstupenek: dvojice 4950, množina 100 200 vstupenek: dvojice 19900, množina 200 400 vstupenek: dvojice 79800, množina 400 800 vstupenek: dvojice 319600, množina 800
Sleduj sloupec s dvojicemi: při dvojnásobku vstupenek je práce čtyřikrát větší. Množina jen kopíruje velikost dat. Oba způsoby dávají stejnou odpověď, jen jeden z nich přestane být použitelný dávno před tím druhým.
Big O: tvar růstu
Big O (česky „velké O“) je zkratka pro odpověď na jedinou otázku: když přibudou data, jak poroste práce? Písmeno n znamená velikost dat, třeba počet prvků v seznamu. Nejde o přesný počet kroků, jde o tvar křivky.
| Zápis | Říká se | Typický příklad | Co udělá dvojnásobek dat |
|---|---|---|---|
O(1) | konstantní | x in mnozina, d[klic], len(s) | nic |
O(log n) | logaritmická | hledání půlením | přidá jeden krok |
O(n) | lineární | x in seznam, sum(s) | práce se zdvojnásobí |
O(n log n) | „en log en“ | sorted(s) | o něco víc než dvojnásobek |
O(n²) | kvadratická | každý s každým | práce se zčtyřnásobí |
Čísla jsou výmluvnější než názvy. import math si přinese hotové matematické funkce, moduly přijdou na řadu později.
import math
print(f"{'n':>10}{'log n':>8}{'n log n':>14}{'n²':>20}")
for n in [10, 1_000, 1_000_000]:
log = math.ceil(math.log2(n))
print(f"{n:>10_}{log:>8}{n * log:>14_}{n * n:>20_}")
n log n n log n n²
10 4 40 100
1_000 10 10_000 1_000_000
1_000_000 20 20_000_000 1_000_000_000_000Pro představu: kdyby jeden krok trval mikrosekundu, milion prvků by při O(log n) zabral 20 mikrosekund, při O(n) sekundu, při O(n log n) dvacet sekund a při O(n²) skoro dvanáct dní. Rychlejší počítač tohle nezachrání, lepší postup ano.
Odhad si uděláš podle čtyř pravidel:
- Konstanty se škrtají.
3n + 5kroků je pořádO(n). Zajímá nás tvar, ne měřítko. - Zůstává nejrychleji rostoucí člen.
n² + njeO(n²), protože při velkémnto druhé skoro nic neznamená. - Cykly za sebou se sčítají, cykly v sobě se násobí. Dva průchody seznamem po sobě jsou
O(n), průchod v průchodu jeO(n²). - Různá data, různá písmena. Když pro každý z
nřádků prohledáš jiný seznam délkym, je toO(n·m).
Program projde seznam jednou, aby našel maximum, a potom ještě jednou, aby spočítal součet. Jakou má složitost?
Násobí se jen cykly vnořené do sebe. Dva průchody po sobě jsou 2n kroků, a to je pořád lineární růst.
Funkce s kvadratickou složitostí zpracuje 10 000 řádků za 10 sekund. Kolik zhruba potrvá 20 000 řádků?
Dvojnásobek dat znamená u O(n²) čtyřnásobek práce. Je to odhad, ale u velkých n obvykle docela sedí.
Kolik co stojí v Pythonu
Tuhle tabulku se vyplatí mít v hlavě. „V průměru“ znamená, že jednotlivá operace může výjimečně trvat déle, ale v součtu to nepoznáš.
| Co děláš | Zápis | Cena |
|---|---|---|
| Přečíst nebo přepsat prvek na pozici | s[i], s[i] = x | O(1) |
| Přidat na konec, vzít z konce | s.append(x), s.pop() | O(1) v průměru |
| Vložit nebo vzít na začátku či uprostřed | s.insert(0, x), s.pop(0) | O(n) |
| Hledat hodnotu v seznamu | x in s, s.index(x), s.count(x), s.remove(x) | O(n) |
Udělat řez délky k | s[a:b] | O(k) |
| Projít všechno | sum(s), max(s), for x in s | O(n) |
| Seřadit | sorted(s), s.sort() | O(n log n) |
| Zjistit délku | len(s) | O(1) |
| Množina: přidat, smazat, ověřit | m.add(x), m.discard(x), x in m | O(1) v průměru |
| Slovník: číst, zapsat, smazat, ověřit klíč | d[k], d[k] = v, del d[k], k in d | O(1) v průměru |
| Hledat mezi hodnotami slovníku | x in d.values() | O(n) |
Proč jsou množina a slovník tak rychlé? Z hodnoty si spočítají číslo, kterému se říká hash, a to rovnou určí místo v paměti, kde se má hledat. Je to lístek ze šatny. Proto taky přijímají jen neměnné hodnoty: kdyby se kabát cestou změnil na jiný, lístek by vedl jinam.
Tady si můžeš změřit i skutečný čas. Modul time nabízí stopky. Čísla se budou lišit podle počítače, proto ukázka nemá pevný výstup, ale poměr mluví jasně.
import time
velikost = 10_000
seznam = list(range(velikost))
mnozina = set(seznam)
dotazy = [velikost - 1 - i for i in range(2_000)] # hledáme blízko konce
start = time.perf_counter()
nalezeno = 0
for x in dotazy:
if x in seznam:
nalezeno += 1
cas_seznam = time.perf_counter() - start
start = time.perf_counter()
nalezeno = 0
for x in dotazy:
if x in mnozina:
nalezeno += 1
cas_mnozina = time.perf_counter() - start
print(f"seznam: {cas_seznam * 1000:10.3f} ms")
print(f"množina: {cas_mnozina * 1000:10.3f} ms")
Kontrola objednávek
E-shop má seznam blokovaných adres a seznam objednávek. Vytvoř z blokovaných adres množinu blokovane_rychle. Potom do seznamu zamitnute ulož všechny adresy z objednavky, které jsou blokované, ve stejném pořadí, v jakém jdou objednávky za sebou.
blokovane = ["[email protected]", "[email protected]", "[email protected]"]
objednavky = ["[email protected]", "[email protected]", "[email protected]",
"[email protected]", "[email protected]", "[email protected]"]
# doplň
Pod kapotou · proč je append levný: amortizace
list v CPythonu je souvislé pole ukazatelů na objekty, takže s[i] je jen aritmetika s adresou. Pole má rezervu: list_resize při zaplnění počítá novou kapacitu jako (newsize + (newsize >> 3) + 6) & ~3, tedy růst zhruba o osminu. Geometrický růst znamená, že drahé kopírování přichází stále vzácněji a jeho cena rozpočítaná na jeden append zůstává konstantní. Tomu se říká amortizovaná složitost. Výjimka: jednotlivý append může trvat O(n), což je v systémech s tvrdými požadavky na latenci znát.
import sys
s = []
kapacita = sys.getsizeof(s)
zmeny = 0
for i in range(100_000):
s.append(i)
nova = sys.getsizeof(s)
if nova != kapacita:
zmeny += 1
kapacita = nova
print("append:", len(s), "| změn kapacity:", zmeny)
append: 100000 | změn kapacity: 66
Sto tisíc přidání a jen pár desítek změn kapacity. [None] * n alokuje celé pole rovnou. Comprehension sice roste stejně jako append, ale běží přes instrukci LIST_APPEND, takže odpadá hledání a volání metody. Oba rozdíly jsou v konstantě, ne v Big O.
Skryté cykly
Nejdražší řádky v programu často vypadají nejnevinněji. Jeden zápis, žádné for, a přitom uvnitř běží průchod celými daty. Když takový řádek dáš do cyklu, máš O(n²) a nikde ho nevidíš.
Typický příklad je fronta. pop(0) vezme první prvek a všechny ostatní musí poposkočit o místo dopředu.
fronta = list(range(1_000))
posuny = 0
while fronta:
posuny += len(fronta) - 1 # tolik prvků se posune po pop(0)
fronta.pop(0)
print("pop(0), posunutých prvků:", posuny)
fronta = list(range(1_000))
odebrano = 0
while fronta:
fronta.pop() # z konce se nic neposouvá
odebrano += 1
print("pop(), odebráno prvků:", odebrano, "a posunuto 0")
pop(0), posunutých prvků: 499500 pop(), odebráno prvků: 1000 a posunuto 0
Pro opravdovou frontu existuje collections.deque, ukáže ji lekce collections a itertools. Stejně záludné je počítání výskytů přes count. Výsledek je správný, ale každé count znovu projde celý seznam.
objednavky = ["pivo", "voda", "pivo", "káva", "voda", "pivo"]
# O(n²): pro každou položku se znovu prochází celý seznam
pomale = {}
for polozka in objednavky:
pomale[polozka] = objednavky.count(polozka)
# O(n): jeden průchod a slovník jako počítadlo
rychle = {}
for polozka in objednavky:
rychle[polozka] = rychle.get(polozka, 0) + 1
print(pomale == rychle)
print(rychle)
True
{'pivo': 3, 'voda': 2, 'káva': 1}Další podezřelí, které hledej uvnitř cyklů:
s.remove(x),s.index(x),s.insert(0, x)projdou nebo posunou celý seznam,s[1:]pokaždé vyrobí kopii skoro celého seznamu,sorted(s)v cyklu řadí znovu a znovu, stačí většinou jednou před ním,text = text + kousekmůže při každém přidání kopírovat vše dosavadní. Kousky sbírej do seznamu a na konci spoj přes"".join(kousky).
První vstupenka, která přišla podruhé
V seznamu davky je několik skupin vstupenek v pořadí, v jakém prošly turniketem. Pro každou skupinu najdi první vstupenku, která se objevila podruhé, a přidej ji do seznamu vysledky. Když se ve skupině nic neopakuje, přidej None. Každou skupinu zvládni jedním průchodem s množinou.
davky = [
["A12", "B07", "C33", "B07", "A12"],
["X1", "X2", "X3"],
["Q", "Q"],
[],
]
vysledky = []
# doplň
Pod kapotou · detaily, které v běžných tabulkách nenajdeš
- Řazení je Timsort, od Pythonu 3.11 se slučovacím pravidlem Powersort. Je stabilní a na už seřazených datech mu stačí
n − 1porovnání, takže „seřadit, co je skoro seřazené“ bývá levné.key=se počítá pro každý prvek jen jednou. x in range(...)je pro celá číslaO(1), počítá se aritmeticky. Ufloatse alerangepoctivě prochází.x in {1, 2, 3}s konstantami překladač uloží jako hotovýfrozenset, takže se množina nestaví při každém průchodu.s += kousekumí CPython někdy provést na místě, když na řetězec nevede jiná reference. Je to implementační detail a PEP 8 výslovně radí na něj nespoléhat,"".joinje jistota.joinsi navíc vstup nejdřív převede na seznam, takže generátor mu paměť neušetří.a in bu řetězců používá od Pythonu 3.10 pro delší vzory dvoucestný algoritmus, který drží nejhorší případ lineární.- Mazání ze začátku slovníku je past:
k = next(iter(d)); del d[k]v cyklu je kvadratické, protože iterace musí pokaždé přeskočit už smazané položky. Na frontu patřídequeneboOrderedDict.popitem(last=False).
Půlení: když jsou data seřazená
V seřazených datech nemusíš číst všechno. Podíváš se doprostřed a hned víš, ve které polovině hledat dál. Je to starý trik z telefonního seznamu a jmenuje se binární vyhledávání. Každý krok zahodí polovinu zbytku, proto je to O(log n).
range se umí indexovat jako seznam a nezabírá paměť za každý prvek, takže si můžeme dovolit milion čísel.
cisla = range(0, 2_000_000, 2) # milion seřazených sudých čísel
hledane = 1_234_566
dolni = 0
horni = len(cisla) - 1
kroky = 0
nalezeno = False
while dolni <= horni:
stred = (dolni + horni) // 2
kroky += 1
if cisla[stred] == hledane:
nalezeno = True
break
elif cisla[stred] < hledane:
dolni = stred + 1
else:
horni = stred - 1
print("Prvků:", len(cisla))
print("Nalezeno:", nalezeno)
print("Kroků:", kroky)
Prvků: 1000000 Nalezeno: True Kroků: 20
Milion prvků a stačí nanejvýš dvacet pohledů. Podmínkou je, že data musí být seřazená. Řazení samo stojí O(n log n), takže kvůli jedinému hledání se nevyplatí. Vyplatí se, když se v neměnných datech hledá často, nebo když chceš rozsahy typu „všechny objednávky mezi 100 a 200 Kč“, které množina neumí.
Kolik otázek stačí
Při hře na hádání čísla od 1 do n každá otázka „je to víc, nebo míň?“ půlí možnosti, takže k otázek rozliší až 2 ** k čísel. Pro každé číslo z rozsahy najdi nejmenší k, pro které platí 2 ** k >= n, a přidej ho do seznamu pokusy.
rozsahy = [10, 100, 1_000, 1_000_000]
pokusy = []
# doplň
Jak vybrat strukturu
Začni otázkou, co budeš s daty dělat nejčastěji.
| Potřebuješ | Sáhni po | Proč |
|---|---|---|
| držet pořadí, číst podle pozice, přidávat na konec | seznam | levné s[i] a append |
| pevný záznam, který se nemění, nebo složený klíč | n-tice | je neměnná a dá se hashovat |
| rychle zjistit „je to tam?“, zbavit se duplicit | množina | x in m je O(1) |
| k něčemu najít další údaj, počítat výskyty | slovník | d[k] je O(1) |
| přidávat na konec a brát zepředu | collections.deque | oba konce jsou O(1) |
| hledat v seřazených datech, ptát se na rozsahy | seřazený seznam a půlení | O(log n) a drží pořadí |
Rychlost není zadarmo. Množina a slovník zaberou výrazně víc paměti než seznam se stejným počtem prvků, množina neudrží pořadí ani duplicity a oboje přijímá jen neměnné hodnoty. Každá struktura je výměna.
Máš slovník {jmeno: telefon} a často se ptáš, komu patří dané číslo. Co je nejlepší?
Slovník je rychlý jen podle klíčů, hodnoty se procházejí jedna po druhé. Druhý slovník stojí paměť, ale z dotazu udělá O(1). Musíš ho ovšem měnit spolu s prvním.
Dvě položky za poukázku
Zákazník má poukázku na přesně 1000 Kč a chce ji utratit za dvě různé položky z košíku. Pro každý košík v kosiky najdi takovou dvojici cen a přidej ji do seznamu vysledky jako n-tici. Když neexistuje, přidej None. V každém košíku je nanejvýš jedna správná dvojice.
Zkus to jedním průchodem: u každé ceny víš, kolik do tisícovky chybí, a stačí se zeptat, jestli jsi takovou cenu už viděl.
poukazka = 1000
kosiky = [
[120, 640, 275, 90, 725, 310],
[500, 120, 300, 55],
[80, 500, 340, 500],
]
vysledky = []
# doplň
Pod kapotou · kdy O(1) přestane platit
Slovník i množina jsou hashovací tabulky s otevřeným adresováním. Slovník má od verze 3.6 kompaktní rozložení: řídkou tabulku indexů a vedle ní hustě uložené položky v pořadí vložení. Tabulka se zvětšuje, když se zaplní asi ze dvou třetin, u množiny ze tří pětin, takže i tady je cena jednoho vložení jen amortizovaná. O(1) navíc platí jen tehdy, když se hashe rozumně rozprostřou. Když všechny skončí stejně, degraduje hledání na průchod:
class Kolizni:
porovnani = 0
def __init__(self, hodnota):
self.hodnota = hodnota
def __hash__(self):
return 1 # všichni na stejné místo
def __eq__(self, other):
Kolizni.porovnani += 1
return self.hodnota == other.hodnota
for n in [250, 500, 1_000]:
Kolizni.porovnani = 0
m = {Kolizni(i) for i in range(n)}
print(f"{n:>5} prvků: {Kolizni.porovnani:>7} porovnání")
250 prvků: 35704 porovnání 500 prvků: 143738 porovnání 1000 prvků: 605201 porovnání
Dvojnásobek prvků, zhruba čtyřnásobek porovnání: z množiny se stalo O(n²). Není to akademická hříčka. Útoky na webové servery zaplněním tabulky kolizními klíči vedly k CVE-2012-1150 a k náhodnému hashování řetězců, proto se hash("text") mezi spuštěními liší (viz PEP 456 a PYTHONHASHSEED). Celá čísla náhodná nejsou: hash(n) je pro nezáporné n zbytek po dělení sys.hash_info.modulus. Kdo ti umí poslat libovolně velká čísla, která pak vkládáš do množiny, umí vyrobit kolize. Velikost vstupů proto omezuj na hranici systému.
Do reálné ceny mluví i to, co Big O škrtá. Prvky seznamu jsou ukazatele na objekty rozeseté po paměti, takže i lineární průchod platí za výpadky cache a za práci interpretu s každým objektem. Proto bývá NumPy s hustými poli a smyčkami v C o řády rychlejší při stejné složitosti.
Vyzkoušej si: Jak rychle roste práce
Posuvníkem měníš velikost vstupu a porovnáváš růst různých složitostí, i na logaritmické ose.
Vyzkoušej si: Závod řadicích algoritmů
Bublinkové, vkládací a slučovací řazení na stejných datech. Sleduj počet porovnání a prohození.
Vyzkoušej si: Lineární a binární hledání
Vyber cíl a po krocích porovnej, kolik kroků potřebuje každý způsob hledání.