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))
5 3 ['[email protected]', '[email protected]', '[email protected]']
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])
3 [1, 2, 3] <class 'dict'> <class 'set'>
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
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))
['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)
['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")
Proč to tak je a kdy se to vyplatí, rozebírá lekce Rychlost a volba struktury.
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ň
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]}
2 2019
Co udělá x = {} a následné x.add(1)?
Prázdné složené závorky patří slovníku, protože ten byl v Pythonu dřív. Prázdná množina se zapisuje set().
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.
prihlaseni zaplatili
+-------------+-------+-------------+
| Petr | Eva | Ivan |
| Jana | Ota | |
+-------------+-------+-------------+
jen vlevo oba jen vpravo| Operátor | Metoda | Výsledek |
|---|---|---|
a & b | a.intersection(b) | průnik: je v obou |
a | b | a.union(b) | sjednocení: je aspoň v jedné |
a - b | a.difference(b) | rozdíl: je v a, ale ne v b |
a ^ b | a.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 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.
Máš množiny objednali a dostali. Jak zjistíš, komu zboží ještě nepřišlo?
U rozdílu záleží na pořadí. Zůstane to, co je vlevo a chybí vpravo.
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))
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.
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, jinakFalse.
recept = {"mouka", "vejce", "mléko", "cukr"}
spiz = {"sůl", "mouka", "cukr", "olej"}
# doplň
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
strabytesje 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.0aTruejsou jeden prvek. Zůstává ten vložený první.NaNse nerovná ničemu, ani sobě. Od Pythonu 3.10 se jeho hash odvozuje od identity objektu, takže různé objektyNaNzů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)
{1}
2
1
1 1 -2 0
10 True
TrueCelá čí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.