Množina (set)

Už poznáte dátovú štruktúru list, do ktorej viete ukladať nejaké prvky, napríklad čísla. Už viete, že táto dátová štruktúra má každý prvok uložený na nejakej pozícii. To znamená, že ak máme nejaký list, tak vieme napríklad zistiť, že aký prvok sa nachádza na indexe 3 (na 3. pozícii).

Toto je ale vlastnosť, ktorú často nepotrebujeme. Predstavte si, že sa balíte na výlet, a máte iba jednu veľkú tašku. Veci, ktoré si do tejto tašky nie sú na žiadnych pozíciách. Jednoducho ak je vec je niekde v taške, tak je niekde v taške, ale nevieme kde presne.

Podobne funguje dátová štruktúra množina (set). Prvky v nej nie sú na žiadnych pozíciách, indexoch, ani nič také.

Na čo to dobré?

Táto dátová štruktúra zvláda veľmi rýchlo robiť tri operácie:

  • s.add(x) - vlož prvok x do množiny s
  • s.remove(x) - odstráň prvok x do množiny s (pozor, prvok x musí existovať!)
  • x in s - obsahuje množina s prvok x?

Okrem toho, sa samozrejme vieme pýtať na veľkosť množiny (počet prvkov v množine), rovnako ako pri liste.

Používa sa pomerne jednoducho:

# vytvoríme si prázdnu množinu
s = set()

print(s)            # vypíše: {}

s.add(1)
s.add(2)
s.add("ahoj")

print(s)            # vypíše: {1, 2, 'ahoj'}
print(1 in s)       # vypíše: True
print(10 in s)      # vypíše: False
print("ahoj" in s)  # vypíše: True
print("ksp" in s)   # vypíše: False


# vytvoríme slovník s hodnotami: 10, False, 50
s = {10, False, 50}

print(10 in s)       # vypíše: True

s.remove(10)

print(s)             # vypíše: {False, 50}
print(10 in s)       # vypíše: False

Na rozdiel od listu ale nevieme do množiny indexovať, takže nič takéto nefunguje:

s = set()
s.add(1)

s[1]
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: 'set' object is not subscriptable

Ale vieme cez množinu prejsť normálnym for cyklom:

s = {'a' 'b', 'c', 'd'}
for i in s:
  print(s)

Porovnanie rýchlosti s listom

Skúste si u seba na počítači spustiť tento program:

a = list(range(10000000))

for i in range(100):
  print(-i in a)

A všimnite si, ako dlho trvá, kým dobehne.

Potom vyskúšajte spustiť tento program:

a = set(range(10000000))

for i in range(100):
  print(-i in a)

A všimnite si, že oproti prvému programu skončí prakticky ihneď.

Vkladanie rôznych dátových typov

Skúste vytvoriť množinu, ktorá bude obsahovať napríklad nejaký list, alebo inú množinu:

# vytvoríme si prázdnu množinu
s = set()

s.add([1,2,9])
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: unhashable type: 'list'

s.add({1,2,9})
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: unhashable type: 'set'

Vidíme, že ani s jedným dátovým typom sa to nepodarí. Je to preto, ako interne funguje set. Pri vkladaní nejakého prvku sa z neho pokúsi urobiť niečo ako "odtlačok" (hash). To sa mu ale nepodarí s dátovým typom, ktorý sa môže meniť, ako je napríklad set alebo list.

Ak teda chcete vložiť nejaký prvok do množiny, musí byť tzv. nemeniteľný (immutable). Takéto dátové typy sú napríklad int, bool, float, string alebo tuple, ktorý sme spomínali v minulej lekcii.

Ďalej