Struktury danych w Pythonie: set (zbiór)

przez | 5 lutego 2020

Cześć! Po listach i tuplach przyszedł czas na zapoznanie się z kolejną strukturą danych w Pythonie, czyli ze zbiorem, w języku angielskim zwanym – set.

Charakterystyka zbiorów

Są dwie główne cechy wyróżniające set od poznanych do tej pory struktur:

  • jest kolekcją nieuporządkowaną, czyli nie gwarantuje zachowania żadnej kolejności elementów
  • gwarantuje brak duplikacji, czyli w zbiorze nigdy nie pojawią się dwa elementy o takiej samej wartości.

Jeśli czytałeś poprzednie wpisy to pewnie pamiętasz, że lista i krotka mają dokładnie przeciwne cechy: są uporządkowane i pozwalają na wielokrotne istnienie elementów o tej samej wartości.

Kiedy używać zbioru?

Set przyda się szczególnie, gdy chcemy:

  • usunąć duplikaty z naszej kolekcji – możemy przekonwertować listę albo tuplę na zbiór i wszystkie duplikaty zostaną usunięte,
  • sprawdzać istnienie elementu w kolekcji – jeśli mamy wiele elementów, to w przypadku zbioru będzie to dużo wydajniejsze niż dla listy czy krotki,
  • wykonywać matematyczne operacje na kolekcjach – np. wyznaczanie części wspólnej dwóch zbiorów, różnicy, zawierania się podzbioru w zbiorze itd. – w dalszej części pokażę to na przykładach.

Jakie elementy może przechowywać zbiór?

O ile w przypadku list i krotek mogliśmy wewnątrz nich trzymać w zasadzie dowolne elementy, tak przy zbiorze nie mamy już takiej dowolności.

Wiąże się to ze sposobem przechowywania elementów. Listy i krotki odwołują się do swoich elementów po kolei, dlatego nawet jeśli wartość elementu się zmieni to i tak wiedzą, gdzie w pamięci szukać tego elementu.

>>> german_cars = ["Audi", "BMW", "Mercedes"]
>>> japan_cars = ["Toyota", "Nissan"]
>>> cars = [german_cars, japan_cars]
>>> cars
[['Audi', 'BMW', 'Mercedes'], ['Toyota', 'Nissan']]

# Wyczyścimy teraz wszystkie niemieckie samochody i zastąpimy je Volkswagenem
>>> german_cars.clear()
>>> german_cars
[]
>>> german_cars.append("Volkswagen")
>>> german_cars
['Volkswagen']

# Lista german_cars zmieniła swoją wartość, ale cars wciąż może się do niej odwołać
>>> cars
[['Volkswagen'], ['Toyota', 'Nissan']]

Natomiast set przechowuje elementy bazując na ich hashu – jest to liczba będąca wynikiem funkcji skrótu hash(). Obiekty, dla których możemy wygenerować taki hash, nazywamy „hashable”, czyli hashowalnymi.

>>> name = "Szymon"
>>> hash(name)
2430349420342981267

Żeby obiekt był hashowalny musi implementować metodę __hash__(). Co więcej, musi też implementować metodę __eq__(), aby mógł być porównywalny do innych obiektów.

Nie wszystkie obiekty w Pythonie są hashowalne. Należą do nich przede wszystkim obiekty niemutowalne, których wartość się nie zmienia, np. int, str, tuple czy frozenset, o którym za chwilę powiemy. Niehashowalne są na przykład list czy dict, czyli struktury mutowalne.

Podsumowując, w zbiorze możemy przechowywać tylko obiekty hashowalne.

Czy wiesz, że?

Sam zbiór (set) nie jest hashowalny, bo jest mutowalny – możemy do niego dodawać oraz odejmować elementy. Dlatego set nie może w sobie zawierać innych setów.

Tworzenie zbioru

Do list służyły nawiasy kwadratowe [], do krotek okrągłe (), a zbiory tworzymy używając nawiasów klamrowych – {}. Niedawno obejrzałem serial „Wiedźmin” na Netfliksie, dlatego dzisiejsze przykłady sponsorują bohaterowie Andrzeja Sapkowskiego 😉

>>> heroes = {"Geralt", "Ciri", "Yennefer"}
>>> heroes
{'Ciri', 'Geralt', 'Yennefer'}
>>> type(heroes)
<class 'set'>

Ale uwaga! Zobaczmy co by się stało, gdybyśmy w ten sposób chcieli utworzyć pusty set:

>>> empty_heroes = {}
>>> empty_heroes
{}

Na pozór wszystko wygląda ok. Ale sprawdźmy, jaki jest typ naszego obiektu:

>>> type(empty_heroes)
<class 'dict'>

Gdzie się podział nasz set?! Otóż zamiast zbioru otrzymaliśmy słownik – dict – strukturę, o której będę mówił w kolejnym artykule. Tak się składa, że słownik również używa nawiasów klamrowych.

Słownik składa się z par kluczwartość, a zbiór przechowuje tylko pojedyńcze elementy – wartości. Jeśli tworzymy pustą strukturę, to Python nie wie, czy chodzi nam o zbiór czy o słownik – dlatego twórcy języka zdecydowali, że w takiej sytuacji będzie to zawsze słownik. Sorry Winnetou…

Jak w takim razie stworzyć pusty zbiór? Wykorzystujemy w tym celu konstruktor set(), podobnie jak to było z list() i tuple():

>>> empty_heroes = set()
>>> empty_heroes
set()
>>> type(empty_heroes)
<class 'set'>

Tworzenie zbioru na podstawie innej sekwencji

Za pomocą konstruktora set() możemy też otrzymać zbiór na podstawie innej kolekcji, w szczególności listy albo krotki:

>>> heroes = ["Foltest", "Triss", "Jaskier", "Triss"]
>>> heroes_set = set(heroes)
>>> heroes_set
{'Jaskier', 'Foltest', 'Triss'}

W powyższym przykładzie widać również, że stworzenie zbioru na podstawie listy, która zawierała powtórzone elementy, skutkuje automatycznym usunięciem duplikatów.

Jest to bardzo szybki sposób na zapewnienie unikalności elementów w naszej kolekcji. Jeśli dalej chcemy pracować na liście to możemy przekonwertować zbiór z powrotem. W ten sposób otrzymaliśmy listę bez duplikatów.

>>> unique_heroes = list(heroes_set)
>>> unique_heroes
['Jaskier', 'Foltest', 'Triss']

Tworzenie niezmiennego zbioru – frozenset

Jak już wspomniałem wcześniej, istnieje odmiana zbioru, który jest niemutowalny – po zainicjalizowaniu nie można dodawać ani usuwać z niego elementów. Taka struktura nazywa się frozenset od angielskiego „frozen”, czyli zamrożony. Musisz przyznać, że całkiem zgrabnie to wymyślili, nie? 😀

Możemy go utworzyć tylko i wyłącznie używając konstruktora – frozenset([iterable]), a do środka podajemy dowolny iterable, czyli np. listę, tuplę, czy nawet zbiór:

>>> immutable_heroes = frozenset({"Jaskier", "Geralt"})
>>> immutable_heroes
frozenset({'Geralt', 'Jaskier'})

>>> immutable_heroes.remove("Jaskier")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'remove'

Teraz już nic nie rozdzieli tych dwóch, wiernych kompanów 😜⚔️🪕

Możemy ewentualnie otrzymać pusty frozenset, choć nie za często nam się przyda – nie możemy go później w żaden sposób zmienić:

>>> empty = frozenset()
>>> empty
frozenset()
>>> type(empty)
<class 'frozenset'>

Czy wiesz, że?

Wcześniej mówiłem, że set nie może być elementem setu, bo jest niehashowalny. Czy domyślasz się teraz, jakie może być tego obejście?
Otóż elementem zbioru może być właśnie frozenset, bo jest niemutowalny, a tym samym jest też hashowalny.
Dlatego jeśli potrzebujesz zbiorów w zbiorze, to możesz stworzyć set, który ma w sobie frozensety.

Operacje na zbiorach

Metody niezmieniające zawartości

Na zbiorach możemy wykonywać podobne podstawowe operacje, co na listach, czyli na przykład:

>>> heroes = {"Geralt", "Ciri", "Yennefer"}

# Sprawdzanie ilości elementów
>>> len(heroes)
3

# Sprawdzanie istnienia elementu w zbiorze
>>> "Ciri" in heroes
True
>>> "Jaskier" in heroes
False

# Utworzenie płytkiej kopii zbioru
>>> heroes_copied = heroes.copy()
>>> heroes_copied == heroes
True

Powyższe operacje działają zarówno dla set jak i dla frozenset, ponieważ nie modyfikują zawartości zbioru.

Metody zmieniające zawartość

Ale już przykłady poniżej będą działać tylko dla setów:

# Dodawanie elementu
>>> heroes.add("Triss")
>>> heroes
{'Ciri', 'Geralt', 'Triss', 'Yennefer'}

# Usuwanie elementu
>>> heroes.remove("Geralt")
>>> heroes
{'Ciri', 'Triss', 'Yennefer'}

# Remove wywoła błąd KeyError, jeśli element nie istnieje w zbiorze
>>> heroes.remove("Foltest")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'Foltest'

# Jeśli chcemy usuwać elementy tak, żeby taki błąd został zignorowany,
# to możemy użyć metody discard:
>>> heroes.discard("Foltest")
>>> heroes
{'Ciri', 'Triss', 'Yennefer'}

Ciekawie jest z metodą pop(). Nie przyjmuje ona żadnego argumentu. Dla listy i tupli metoda pop() wywołana bez argumentu usuwała i zwracała ostatni element kolekcji. W przypadku setów pop() usuwa i zwraca LOSOWY element zbioru! Często może być to “pierwszy” element (pierwszy wyświetlany po wyprintowaniu zawartości setu) ale nie musi.

>>> heroes.pop()
'Ciri'
>>> heroes
{'Triss', 'Yennefer'}

Do wyczyszczenia zbioru całkowicie służy metoda clear():

>>> heroes.clear()
>>> heroes
set()

Tak już dla pewności sprawdźmy, co się stanie, jeśli spróbujemy użyć którejś z powyższych metod zmieniających zawartość zbioru na frozensecie:

>>> frozen_heroes = frozenset({"Jaskier", "Geralt"})
>>> frozen_heroes.add("Ciri")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'
>>> frozen_heroes.clear()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'clear'

Tak jak już mówiłem wcześniej – Geralt i Jaskier są nierozłączni, a do tego nie życzą sobie żadnego dodatkowego towarzystwa 😉

Dostęp do elementów zbioru

Ok, wszystko fajnie, ale chyba nie pokazaliśmy żadnego sposobu na dostęp do konkretnego elementu zbioru, nie? W listach i tuplach mogliśmy zrobić tak:

>>> weapons = ["sword", "axe", "magic"]
>>> weapons[2]
'magic'

W przypadku zbiorów nie ma takiej opcji:

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

Wszystko wynika z tego, że, tak jak mówiłem na początku, zbiór nie gwarantuje nam kolejności przechowywania elementów. Dlatego nie możemy odwoływać się do nich po indeksie.

Jak w takim razie dostać się do konkretnego elementu? Możemy zamienić set na list:

>>> weapons_list = list(weapons_set)
>>> weapons_list
['sword', 'magic', 'axe']
>>> weapons_list[0]
'sword'

Nawet w powyższych przykładach widać, że po zrobieniu konwersji list –> set –> list na końcu dostaliśmy listę w innej kolejności niż ta początkowa! To właśnie dlatego, że zbiory nie gwarantują kolejności.

Dlatego tutaj dostęp po indeksie ma niewielki sens, bo i tak nie wiemy, który element będzie na którym miejscu na liście po utworzeniu jej ze zbioru. Także jeśli chcemy odwoływać się do konkretnych elementów w naszej strukturze, to set nie jest dobrym wyborem.

Jeśli jednak chcemy po prostu wykonać jakąś operację z użyciem każdego elementu zbioru, to możemy odwołać się do każdego z nich na przykład w pętli for:

>>> for weapon in weapons_set:
...     print(weapon)

sword
magic
axe

Porównywanie zbiorów

Na zbiorach możemy wykonywać działania matematyczne z teorii zbiorów. Są to np. zawieranie się zbioru w zbiorze, różnica zbiorów, iloczyn itp. Spójrzmy na przykład:

>>> heroes = {"Geralt", "Ciri", "Yennefer"}
>>> female_heroes = {"Ciri", "Yennefer"}

# Iloczyn dwóch zbiorów - otrzymamy zbiór elementów, które należą
# jednocześnie do obu zbiorów
>>> heroes.intersection(female_heroes)
{'Ciri', 'Yennefer'}
>>> heroes &amp; female_heroes  # Robi to samo, co wyrażenie powyżej
{'Ciri', 'Yennefer'}

# Sprawdzamy, czy female_heroes zawiera się w heroes
>>> female_heroes.issubset(heroes)
True
>>> female_heroes <= heroes  # Robi to samo z wykorzystaniem operatora
True
>>> female_heroes > heroes
False

Więcej szczegółów dotyczących działań matematycznych na zbiorach znajdziesz w dokumentacji Pythona lub w świetnym artykule na stronie Real Python.

Podsumowanie

Dzisiaj poznaliśmy kolejną podstawową strukturę danych w Pythonie – set, czyli po polsku – zbiór. Służy on do przechowywania unikalnych elementów, ale nie gwarantuje ich kolejności. Jest strukturą mutowalną, a jej niemutowalnym odpowiednikiem jest frozenset.

Mam nadzieję, że artykuł był dla Ciebie wartościowy. Jeśli masz do mnie jakieś pytania to zostaw komentarz albo pisz do mnie na szymon@pythonowiec.pl.

Poniżej znajdziesz formularz rejestracji na programistyczny newsletter! Co tydzień wysyłam ciekawostki ze świata IT, a także informuję o nowych filmach i artykułach. Dużo wartości, zero spamu – w każdej chwili możesz zrezygnować. Wchodzisz w to? 😀

Jeszcze raz dzięki, wszystkiego dobrego i do następnego razu! 👋

2 myśli nt. „Struktury danych w Pythonie: set (zbiór)

  1. Pingback: [VLOG #17] Python od podstaw #3: Struktury danych - Zbiór - Dziwne, u mnie działa

  2. Pingback: Struktury danych w Pythonie: dict (słownik) - pythonowiec.pl

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *