0 dní v řadě · 0 bodů

Datové struktury · 18 min

Množiny

Odstraníš duplicity, bleskově ověříš výskyt a porovnáš dvě skupiny přes průnik, sjednocení a rozdíl.

Hloubka
Úkoly
Lidsky řečeno

Představ si vyhazovače na soukromé akci. V ruce drží seznam hostů. Nezajímá ho, kdo na seznamu stojí první, ani jestli tam někoho omylem napsali dvakrát. Řeší jedinou otázku: jsi tam, nebo ne? Přesně takhle přemýšlí množina.

Duplicity zmizí samy

Přišly přihlášky na workshop. Někdo klikl dvakrát, někdo se pro jistotu přihlásil i druhý den. Seznam má pět řádků, ale kolik přijde lidí?

prihlasky = ["[email protected]", "[email protected]", "[email protected]", "[email protected]", "[email protected]"]

lide = set(prihlasky)

print(len(prihlasky))
print(len(lide))
print(sorted(lide))

Množina (anglicky set) je kolekce, ve které je každá hodnota nejvýš jednou. Funkce set(...) vezme cokoli, čím se dá projít, a z každé hodnoty nechá jeden kus.

Množina si nepamatuje pořadí. Proto výpis procházím přes sorted, který vrátí obyčejný seřazený seznam. Bez něj by texty mohly při každém spuštění programu vyjít v jiném pořadí.

Množinu jde napsat i rovnou, do složených závorek. Má to jednu záludnost: prázdné {} není množina, ale slovník. Prázdná množina se píše set(). A protože pořadí neexistuje, neexistuje ani „nultý prvek“.

cisla = {3, 1, 2, 3, 1}

print(len(cisla))
print(sorted(cisla))
print(type({}))
print(type(set()))

print(cisla[0])
Výstup
3
[1, 2, 3]
<class 'dict'>
<class 'set'>
Úkol

Kolik lidí opravdu přišlo

V seznamu navstevy je každý příchod do posilovny. Do proměnné pocet ulož, kolik různých lidí přišlo. Do proměnné jmena ulož jejich jména jako seznam seřazený podle abecedy.

navstevy = ["ota", "iva", "ota", "max", "iva", "ota", "lea"]

# doplň pocet a jmena
Výstup

Už jsem to viděl?

Nejčastější použití množiny v reálném kódu vypadá takhle: procházíš data a pamatuješ si, co už prošlo. Třeba hledáš objednávky, které systém poslal dvakrát.

objednavky = ["A17", "B02", "A17", "C33", "B02", "D41"]

videne = set()
dvakrat = []

for cislo in objednavky:
    if cislo in videne:
        dvakrat.append(cislo)
    else:
        videne.add(cislo)

print(dvakrat)
print(len(videne))
Výstup
['A17', 'B02']
4

Množina se dá za běhu měnit. Metoda add přidává, discard a remove odebírají. Rozdíl mezi nimi poznáš, až odebíráš něco, co v množině není: discard mlčky pokračuje, remove skončí chybou KeyError.

stitky = {"akce", "novinka"}

stitky.add("doprava zdarma")
stitky.add("akce")           # už tam je, nic se nestane
stitky.discard("výprodej")   # není tam, nic se nestane
stitky.remove("novinka")

print(sorted(stitky))
print("akce" in stitky)
print("novinka" in stitky)
Výstup
['akce', 'doprava zdarma']
True
False

Proč nepoužít seznam? Protože seznam hledá poctivě: bere položku za položkou, dokud nenajde shodu. Množina podle hodnoty rovnou spočítá, kde by měla ležet, a podívá se tam. Spusť si to. Časy se budou lišit podle počítače, ale rozdíl bývá obrovský.

import timeit

seznam = list(range(100_000))
mnozina = set(seznam)
hledane = 99_999

cas_seznam = timeit.timeit("hledane in seznam", globals=globals(), number=200)
cas_mnozina = timeit.timeit("hledane in mnozina", globals=globals(), number=200)

print(f"seznam:  {cas_seznam * 1000:10.3f} ms")
print(f"množina: {cas_mnozina * 1000:10.3f} ms")
Výstup

Proč to tak je a kdy se to vyplatí, rozebírá lekce Rychlost a volba struktury.

Úkol

První opakování

Čtečka posílá kódy balíků. Najdi kód, u kterého se jako první ukázalo, že už prošel, a ulož ho do proměnné prvni. V ukázkových datech je to M2: objeví se podruhé dřív, než se vrátí K7.

kody = ["K7", "M2", "Q9", "M2", "K7", "Q9"]

# doplň
Výstup

Co do množiny smí

Aby množina věděla, kam hodnotu uložit, spočítá si z ní číslo, takzvaný hash. Představ si ho jako otisk prstu. Kdyby se hodnota později změnila, změnil by se i otisk a množina by ji už nenašla. Proto do ní smí jen hodnoty, které se měnit nedají: čísla, texty, n-tice. Seznam ani slovník ne.

Stejně je na tom sama množina. Když potřebuješ množinu uvnitř jiné množiny nebo jako klíč slovníku, použij její neměnnou sestru frozenset. Hodí se třeba pro dvojice, u kterých nezáleží na pořadí. Přátelství Evy s Petrem je totéž co přátelství Petra s Evou.

mista = {(0, 0), (2, 5), (0, 0)}
print(len(mista))

znami_od = {frozenset({"Eva", "Petr"}): 2019}
print(znami_od[frozenset({"Petr", "Eva"})])

spatne = {[0, 0], [2, 5]}
Výstup
2
2019
Kvíz

Co udělá x = {} a následné x.add(1)?

Porovnávání dvou skupin

Tady množiny předvedou to nejlepší. Máš lidi, kteří se přihlásili, a lidi, kteří zaplatili. Kdo zaplatil a nepřihlásil se? Komu poslat upomínku? S cykly by to bylo několik řádků. S množinou jeden znak.

text
     prihlaseni            zaplatili
  +-------------+-------+-------------+
  |    Petr     |  Eva  |    Ivan     |
  |    Jana     |  Ota  |             |
  +-------------+-------+-------------+
    jen vlevo     oba     jen vpravo
OperátorMetodaVýsledek
a & ba.intersection(b)průnik: je v obou
a | ba.union(b)sjednocení: je aspoň v jedné
a - ba.difference(b)rozdíl: je v a, ale ne v b
a ^ ba.symmetric_difference(b)je právě v jedné z nich
prihlaseni = {"Eva", "Petr", "Jana", "Ota"}
zaplatili = {"Eva", "Ota", "Ivan"}

print("v pořádku:", sorted(prihlaseni & zaplatili))
print("všichni:  ", sorted(prihlaseni | zaplatili))
print("upomínka: ", sorted(prihlaseni - zaplatili))
print("záhada:   ", sorted(zaplatili - prihlaseni))
print("nesedí:   ", sorted(prihlaseni ^ zaplatili))

print(sorted(prihlaseni.union(["Lea", "Eva"])))
Výstup
v pořádku: ['Eva', 'Ota']
všichni:   ['Eva', 'Ivan', 'Jana', 'Ota', 'Petr']
upomínka:  ['Jana', 'Petr']
záhada:    ['Ivan']
nesedí:    ['Ivan', 'Jana', 'Petr']
['Eva', 'Jana', 'Lea', 'Ota', 'Petr']

Všimni si posledního řádku. Metody berou cokoli, čím se dá projít, tedy i seznam. Operátory chtějí množinu na obou stranách, takže prihlaseni | ["Lea"] skončí chybou TypeError.

Kvíz

Máš množiny objednali a dostali. Jak zjistíš, komu zboží ještě nepřišlo?

Množiny jde i porovnávat. a <= b se ptá, jestli je celé a obsažené v b, tedy jestli je a jeho podmnožina. isdisjoint zjistí, jestli skupiny nemají nic společného.

recept = {"mouka", "vejce", "mléko"}
doma = {"mouka", "vejce", "mléko", "sůl", "cukr"}
alergeny = {"arašídy", "sója"}

print(recept <= doma)
print(doma <= recept)
print(recept < recept)
print(recept <= recept)
print(recept.isdisjoint(alergeny))
Výstup
True
False
False
True
True

< je přísnější verze: a musí být v b obsažené a b musí mít něco navíc. Proto množina není ostrou podmnožinou sama sebe.

Všechny operace mají i variantu, která mění množinu na místě: a |= b (totéž co a.update(b)), a &= b a a -= b.

Úkol

Co dokoupit

Máš recept a spiz. Vytvoř tři proměnné:

  • chybi: množina surovin, které recept potřebuje a ve spíži nejsou,
  • mam: množina surovin z receptu, které ve spíži jsou,
  • muzu_varit: True, když je ve spíži všechno z receptu, jinak False.
recept = {"mouka", "vejce", "mléko", "cukr"}
spiz = {"sůl", "mouka", "cukr", "olej"}

# doplň
Výstup
Pod kapotou · hashovací tabulka v CPythonu

Množina je tabulka s otevřeným adresováním. Index se bere z dolních bitů hashe. Při kolizi CPython nejdřív zkusí až 9 sousedních slotů, protože leží ve stejné oblasti paměti a procesorová cache je zvládne levně. Teprve pak skočí jinam podle sekvence, do které postupně míchá vyšší bity hashe. Tabulka roste, když obsazené sloty včetně těch po smazání dosáhnou 60 %.

Průměrně je x in s O(1), v nejhorším případě při samých kolizích O(n). a & b iteruje menší z obou množin, tedy O(min(len(a), len(b))), a | b je O(len(a) + len(b)) a a - b je O(len(a)).

Tři věci, které v produkci překvapí:

  • Hash str a bytes je solený náhodně pro každý proces kvůli útokům přes kolize (PEP 456, PYTHONHASHSEED). Pořadí množiny textů se proto mezi spuštěními mění a test porovnávající str(mnozina) občas spadne.
  • Rovnost vynucuje stejný hash, takže 1, 1.0 a True jsou jeden prvek. Zůstává ten vložený první. NaN se nerovná ničemu, ani sobě. Od Pythonu 3.10 se jeho hash odvozuje od identity objektu, takže různé objekty NaN zůstanou v množině vedle sebe.
  • Mazání tabulku nezmenšuje a iterace prochází všechny její sloty. Množina, která narostla na milion prvků a spadla na deset, se dál prochází pomalu a drží paměť. Pomůže s = set(s).
import sys

print({1, 1.0, True})
print(len({float("nan"), float("nan")}))

nan = float("nan")
print(len({nan, nan}))

print(hash(1), hash(1.0), hash(-1), hash(sys.hash_info.modulus))

velka = set(range(100_000))
pred = sys.getsizeof(velka)
for cislo in range(99_990):
    velka.discard(cislo)

print(len(velka), sys.getsizeof(velka) == pred)
print(sys.getsizeof(set(velka)) < pred)
Výstup
{1}
2
1
1 1 -2 0
10 True
True

Celá čísla se hashují modulo sys.hash_info.modulus (na 64bitovém CPythonu je to 2^61 − 1), proto vyšla nula. hash(-1) je -2, protože -1 znamená v C API chybu.

Ještě jedna past: < je u množin jen částečné uspořádání. Dvě různé množiny můžou být neporovnatelné, takže a < b i b < a vrátí False. Výsledek sorted(seznam_mnozin) nebo min(seznam_mnozin) pak nemá rozumný význam. Viz dokumentace množin.

Vyzkoušej si: Množiny na Vennově diagramu

Uprav dvě množiny a sleduj výsledek operací sjednocení, průniku, rozdílu a symetrického rozdílu s jejich zápisem v Pythonu.