Zestaw w programowaniu w języku Python to nieuporządkowany typ danych kolekcji, który można iterować, modyfikować i nie zawiera duplikatów elementów.
Zbiór jest reprezentowany przez { } (wartości ujęte w nawiasy klamrowe)
Główną zaletą korzystania z zestawu, w przeciwieństwie do lista , polega na tym, że posiada wysoce zoptymalizowaną metodę sprawdzania, czy określony element znajduje się w zestawie. Opiera się to na strukturze danych znanej jako tablica mieszająca. Ponieważ zbiory są nieuporządkowane, nie możemy uzyskać dostępu do elementów za pomocą indeksów, tak jak to robimy w przypadku list.
Przykład zestawów Pythona
Python3
var>=> {>'Geeks'>,>'for'>,>'Geeks'>}> type>(var)> |
>
>
różnica między tablicą a listą tablic
Wyjście:
set>
Złożoność czasowa: O(1)
Przestrzeń pomocnicza: O(1)
Wpisz rzutowanie za pomocą metody Python Set
Do rzutowania typów używana jest metoda Python set().
Python3
# typecasting list to set> myset>=> set>([>'a'>,>'b'>,>'c'>])> print>(myset)> # Adding element to the set> myset.add(>'d'>)> print>(myset)> |
>
>
Wyjście:
Zbiór Pythona jest nieuporządkowanym typem danych, co oznacza, że nie możemy wiedzieć, w jakiej kolejności przechowywane są elementy zestawu.
{'c', 'b', 'a'} {'d', 'c', 'b', 'a'}> Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Sprawdź unikalność i niezmienność za pomocą zestawu Pythona
Zestawy Pythona nie mogą mieć zduplikowanej wartości, a po utworzeniu nie można zmienić jej wartości.
Python3
# Python program to demonstrate that> # a set cannot have duplicate values> # and we cannot change its items> # a set cannot have duplicate values> myset>=> {>'Geeks'>,>'for'>,>'Geeks'>}> print>(myset)> # values of a set cannot be changed> myset[>1>]>=> 'Hello'> print>(myset)> |
>
>
Wyjście:
Pierwszy kod wyjaśnia, że zestaw nie może mieć zduplikowanej wartości. Każdy znajdujący się w nim przedmiot ma unikalną wartość.
Drugi kod generuje błąd, ponieważ po utworzeniu zestawu nie możemy przypisać ani zmienić wartości. Możemy jedynie dodawać lub usuwać elementy w zestawie.
{'Geeks', 'for'} TypeError: 'set' object does not support item assignment> Element heterogeniczny z zestawem Pythona
Zestawy Pythona mogą przechowywać w nim elementy heterogeniczne, tj. zestaw może przechowywać mieszankę typów danych typu string, integer, boolean itp.
Python3
np.połączyć
# Python example demonstrate that a set> # can store heterogeneous elements> myset>=> {>'Geeks'>,>'for'>,>10>,>52.7>,>True>}> print>(myset)> |
>
>
Wyjście:
{True, 10, 'Geeks', 52.7, 'for'}> Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Zestawy mrożonek Pythona
Zestawy mrożone w Pythonie są niezmienne obiekty, które obsługują tylko metody i operatory, które dają wynik bez wpływu na zamrożony zbiór lub zestawy, do których są stosowane. Można to zrobić za pomocą metody mrożonej() w Pythonie.
Chociaż elementy zestawu można modyfikować w dowolnym momencie, elementy zamrożonego zestawu pozostają takie same po utworzeniu.
Jeśli nie zostaną przekazane żadne parametry, zwraca pusty zestaw zamrożony.
Pyton
# Python program to demonstrate differences> # between normal and frozen set> # Same as {'a', 'b','c'}> normal_set>=> set>([>'a'>,>'b'>,>'c'>])> print>(>'Normal Set'>)> print>(normal_set)> # A frozen set> frozen_set>=> frozenset>([>'e'>,>'f'>,>'g'>])> print>(>'
Frozen Set'>)> print>(frozen_set)> # Uncommenting below line would cause error as> # we are trying to add element to a frozen set> # frozen_set.add('h')> |
>
>
Wyjście:
Normal Set {'a', 'c', 'b'} Frozen Set {'e', 'g', 'f'}> Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Wewnętrzne działanie zestawu
Opiera się to na strukturze danych znanej jako tablica mieszająca. Jeśli na tej samej pozycji indeksu znajduje się wiele wartości, wówczas wartość jest dodawana do tej pozycji indeksu, tworząc listę połączoną.
W Pythonie zestawy są implementowane przy użyciu słownika ze zmiennymi fikcyjnymi, w których kluczowe są elementy zestawu z większą optymalizacją pod kątem złożoności czasowej.
Implementacja zestawu:
Zestawy z wieloma operacjami na pojedynczej tabeli HashTable:
Metody zestawów
Dodawanie elementów do zestawów Pythona
Wkładanie do zestawu odbywa się poprzez ustaw.dodaj( ), gdzie tworzona jest odpowiednia wartość rekordu do przechowywania w tablicy mieszającej. To samo, co sprawdzanie elementu, tj. średnio O(1). Jednak w najgorszym przypadku może tak się stać NA) .
Python3
fizzbuzz Java
# A Python program to> # demonstrate adding elements> # in a set> # Creating a Set> people>=> {>'Jay'>,>'Idrish'>,>'Archi'>}> print>(>'People:'>, end>=> ' '>)> print>(people)> # This will add Daxit> # in the set> people.add(>'Daxit'>)> # Adding elements to the> # set using iterator> for> i>in> range>(>1>,>6>):> >people.add(i)> print>(>'
Set after adding element:'>, end>=> ' '>)> print>(people)> |
>
>
Wyjście:
People: {'Idrish', 'Archi', 'Jay'} Set after adding element: {1, 2, 3, 4, 5, 'Idrish', 'Archi', 'Jay', 'Daxit'}> Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Operacja Union na zestawach Pythona
Dwa zbiory można połączyć za pomocą funkcji union() lub | operator. Dostęp do obu wartości Tabeli Hash jest możliwy i po nich następuje operacja scalania, wykonywana na nich w celu połączenia elementów, przy jednoczesnym usuwaniu duplikatów. Złożoność czasowa tego jest O(długość(s1) + długość(s2)) gdzie s1 i s2 to dwa zbiory, których sumę należy wykonać.
Python3
# Python Program to> # demonstrate union of> # two sets> people>=> {>'Jay'>,>'Idrish'>,>'Archil'>}> vampires>=> {>'Karan'>,>'Arjun'>}> dracula>=> {>'Deepanshu'>,>'Raju'>}> # Union using union()> # function> population>=> people.union(vampires)> print>(>'Union using union() function'>)> print>(population)> # Union using '|'> # operator> population>=> people|dracula> print>(>'
Union using '|' operator'>)> print>(population)> |
>
średnie drzewa
>
Wyjście:
Union using union() function {'Karan', 'Idrish', 'Jay', 'Arjun', 'Archil'} Union using '|' operator {'Deepanshu', 'Idrish', 'Jay', 'Raju', 'Archil'}> Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Operacja przecięcia na zbiorach Pythona
Można to zrobić za pomocą operatora skrzyżowania() lub &. Wybrano wspólne elementy. Są one podobne do iteracji po listach skrótów i łączenia tych samych wartości w obu tabelach. Złożoność czasowa tego równa się O(min(len(s1), len(s2)) gdzie s1 i s2 to dwa zbiory, których sumę należy wykonać.
Python3
# Python program to> # demonstrate intersection> # of two sets> set1>=> set>()> set2>=> set>()> for> i>in> range>(>5>):> >set1.add(i)> for> i>in> range>(>3>,>9>):> >set2.add(i)> # Intersection using> # intersection() function> set3>=> set1.intersection(set2)> print>(>'Intersection using intersection() function'>)> print>(set3)> # Intersection using> # '&' operator> set3>=> set1 & set2> print>(>'
Intersection using '&' operator'>)> print>(set3)> |
>
>
Wyjście:
Intersection using intersection() function {3, 4} Intersection using '&' operator {3, 4}> Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Znajdowanie różnic w zbiorach w Pythonie
Aby znaleźć różnice między zbiorami. Podobnie do znajdowania różnic na połączonej liście. Odbywa się to za pomocą operatora różnicy() lub –. Złożoność czasowa znalezienia różnicy s1 – s2 wynosi O(len(s1))
Python3
Uruchom polecenie cmd w Linuksie
# Python program to> # demonstrate difference> # of two sets> set1>=> set>()> set2>=> set>()> for> i>in> range>(>5>):> >set1.add(i)> for> i>in> range>(>3>,>9>):> >set2.add(i)> # Difference of two sets> # using difference() function> set3>=> set1.difference(set2)> print>(>' Difference of two sets using difference() function'>)> print>(set3)> # Difference of two sets> # using '-' operator> set3>=> set1>-> set2> print>(>'
Difference of two sets using '-' operator'>)> print>(set3)> |
>
>
Wyjście:
Difference of two sets using difference() function {0, 1, 2} Difference of two sets using '-' operator {0, 1, 2}> Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Czyszczenie zestawów Pythona
Metoda Set Clear() opróżnia cały zestaw na miejscu.
Python3
# Python program to> # demonstrate clearing> # of set> set1>=> {>1>,>2>,>3>,>4>,>5>,>6>}> print>(>'Initial set'>)> print>(set1)> # This method will remove> # all the elements of the set> set1.clear()> print>(>'
Set after using clear() function'>)> print>(set1)> |
>
>
Wyjście:
Initial set {1, 2, 3, 4, 5, 6} Set after using clear() function set()> Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Istnieją jednak dwie główne pułapki w zestawach Pythona:
- Zestaw nie utrzymuje elementów w określonej kolejności.
- Do zestawu Pythona można dodać tylko instancje typów niezmiennych.
Złożoność czasowa zbiorów
| Operacja | Przeciętny przypadek | Najgorszy przypadek | notatki |
|---|---|---|---|
| x w s | O(1) | NA) | |
| Unia s|t | O(dł.(s)+dł.(t)) | ||
| Skrzyżowanie s&t | O(min(długość(s), długość(t)) | O(dł.(s) * dł.(t)) | zamień min na max, jeśli t nie jest zbiorem |
| Skrzyżowanie wielokrotne s1&s2&..&sn | (n-1)*O(l) gdzie l to max(len(s1),..,len(sn)) | ||
| Różnica st | O(tylko(e)) |
Operatory na zbiory
Zbiory i zbiory zamrożone obsługują następujące operatory:
| Operatorzy | Notatki |
|---|---|
| wpisz s | kontrola szczelności |
| klucz nie jest w s | kontrola niezabezpieczenia |
| s1 == s2 | s1 jest równoważne s2 |
| s1!= s2 | s1 nie jest równoważne s2 |
| s1 <= s2 | s1 jest podzbiorem s2 |
| s1 | s1 jest właściwym podzbiorem s2 |
| s1>= s2 | s1 jest nadzbiórem s2 |
| s1> s2 | s1 jest właściwym nadzbiorem s2 |
| s1 | s2 | suma s1 i s2 |
| s1 i s2 | przecięcie s1 i s2 |
| s1 – s2 | zbiór elementów w s1, ale nie w s2 |
| s1 ˆ s2 | zbiór elementów dokładnie w jednym z s1 lub s2 |
Najnowsze artykuły na temat zestawu Python Set.