Zbiory

Zbiór (set) to kolekcja unikalnych, nieuporządkowanych elementów. Trzy supermoce zbiorów:

1. Automatyczne usuwanie duplikatów: dodanie tego samego elementu dwukrotnie nie daje żadnego efektu.
2. Sprawdzanie przynależności w czasie O(1): operacja x in s jest niezwykle szybka, nawet przy milionach elementów (działa w oparciu o mechanizm tablicy mieszającej, podobnie jak słowniki).
3. Operacje na zbiorach: suma, iloczyn (przecięcie), różnica, różnica symetryczna.

Tworzenie zbioru

vuoto = set()           # UWAGA: {} tworzy pusty słownik, a nie zbiór!
numeri = {1, 2, 3}
da_lista = set([1, 1, 2, 3, 3, 3])   # {1, 2, 3}

Same nawiasy klamrowe {} tworzą pusty słownik, a nie zbiór: aby stworzyć pusty zbiór, musisz użyć set().

Modyfikowanie zbioru

s = {1, 2, 3}
s.add(4)         # {1, 2, 3, 4}
s.add(1)         # brak efektu (element już istnieje)
s.discard(99)    # usuwa element jeśli istnieje, w przeciwnym razie nic nie robi
s.remove(2)      # usuwa element lub zgłasza KeyError

Operacje na zbiorach

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

a | b    # {1, 2, 3, 4, 5, 6}     suma zbiorów
a & b    # {3, 4}                  iloczyn zbiorów (część wspólnna)
a - b    # {1, 2}                  różnica zbiorów (elementy w a, których nie ma w b)
a ^ b    # {1, 2, 5, 6}            różnica symetryczna (xor)

Istnieją również metody (a.union(b), a.intersection(b), …), które dodatkowo przyjmują dowolny obiekt iterowalny, nie tylko zbiory.

Test przynależności

parole = {"ciao", "mondo", "python"}
"ciao" in parole       # True   O(1)
"java" not in parole   # True

Dla porównania: wyszukiwanie za pomocą słowa kluczowego in wewnątrz listy (list) ma złożoność O(n) i na długich listach jest znacznie wolniejsze.

Frozen set: wersja niemodyfikowalna

frozenset({1, 2, 3}) to wersja hashowalna zbioru: może być kluczem w słowniku lub elementem innego zbioru.

Operacje na zbiorach i wydajność

Zbiory są zaimplementowane jako tablice mieszające (hash tables), co sprawia, że test przynależności (x in moj_zbior) jest niezwykle szybki: wykonuje się w stałym czasie O(1), w przeciwieństwe do list, gdzie wyszukiwanie zajmuje czas liniowy O(n). Ponadto wspierają one operacje algebraiczne, takie jak suma (|), część wspólna (&) oraz różnica (-).

Spróbuj sam

Ćwiczenie powtórzeniowe

Dodatkowe wyzwanie