0 dní v řadě · 0 bodů

Datové struktury · 35 min

Rychlost a volba struktury (Big O)

Naučíš se odhadnout, jak se program zpomalí s růstem dat, a vybrat seznam, množinu nebo slovník tak, aby to vydržel.

Hloubka
Úkoly
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)
Výstup
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í")
Výstup
     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}")
Výstup
 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á seTypický příkladCo udělá dvojnásobek dat
O(1)konstantníx in mnozina, d[klic], len(s)nic
O(log n)logaritmickáhledání půlenímpř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ýmprá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_}")
Výstup
         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_000

Pro 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 + 5 kroků je pořád O(n). Zajímá nás tvar, ne měřítko.
  • Zůstává nejrychleji rostoucí člen. n² + n je O(n²), protože při velkém n to 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 je O(n²).
  • Různá data, různá písmena. Když pro každý z n řádků prohledáš jiný seznam délky m, je to O(n·m).
Kvíz

Program projde seznam jednou, aby našel maximum, a potom ještě jednou, aby spočítal součet. Jakou má složitost?

Kvíz

Funkce s kvadratickou složitostí zpracuje 10 000 řádků za 10 sekund. Kolik zhruba potrvá 20 000 řádků?

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ápisCena
Přečíst nebo přepsat prvek na pozicis[i], s[i] = xO(1)
Přidat na konec, vzít z konces.append(x), s.pop()O(1) v průměru
Vložit nebo vzít na začátku či uprostředs.insert(0, x), s.pop(0)O(n)
Hledat hodnotu v seznamux in s, s.index(x), s.count(x), s.remove(x)O(n)
Udělat řez délky ks[a:b]O(k)
Projít všechnosum(s), max(s), for x in sO(n)
Seřaditsorted(s), s.sort()O(n log n)
Zjistit délkulen(s)O(1)
Množina: přidat, smazat, ověřitm.add(x), m.discard(x), x in mO(1) v průměru
Slovník: číst, zapsat, smazat, ověřit klíčd[k], d[k] = v, del d[k], k in dO(1) v průměru
Hledat mezi hodnotami slovníkux 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")
Výstup
Úkol

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ň
Výstup
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)
Výstup
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")
Výstup
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)
Výstup
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 + kousek můž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).
Úkol

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ň
Výstup
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 − 1 porovná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á čísla O(1), počítá se aritmeticky. U float se ale range poctivě 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 += kousek umí 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, "".join je jistota. join si navíc vstup nejdřív převede na seznam, takže generátor mu paměť neušetří.
  • a in b u ř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ří deque nebo OrderedDict.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)
Výstup
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í.

Úkol

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ň
Výstup

Jak vybrat strukturu

Začni otázkou, co budeš s daty dělat nejčastěji.

PotřebuješSáhni poProč
držet pořadí, číst podle pozice, přidávat na konecseznamlevné s[i] a append
pevný záznam, který se nemění, nebo složený klíčn-ticeje neměnná a dá se hashovat
rychle zjistit „je to tam?“, zbavit se duplicitmnožinax in m je O(1)
k něčemu najít další údaj, počítat výskytyslovníkd[k] je O(1)
přidávat na konec a brát zepředucollections.dequeoba konce jsou O(1)
hledat v seřazených datech, ptát se na rozsahyseř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.

Kvíz

Máš slovník {jmeno: telefon} a často se ptáš, komu patří dané číslo. Co je nejlepší?

Úkol

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ň
Výstup
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í")
Výstup
  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í.