Sada v programování Python je neuspořádaný datový typ kolekce, který je iterovatelný, proměnlivý a nemá žádné duplicitní prvky.
Sada je reprezentována { } (hodnoty uzavřené ve složených závorkách)
Hlavní výhodou použití sady, na rozdíl od a seznam , spočívá v tom, že má vysoce optimalizovanou metodu pro kontrolu, zda je v sadě obsažen konkrétní prvek. To je založeno na datové struktuře známé jako hashovací tabulka. Protože sady nejsou seřazeny, nemůžeme přistupovat k položkám pomocí indexů jako v seznamech.
Příklad sad Pythonu
Python3
java porovnat řetězce
var>=> {>'Geeks'>,>'for'>,>'Geeks'>}> type>(var)> |
>
>
Výstup:
set>
Časová složitost: O(1)
Pomocný prostor: O(1)
Typ Casting metodou Python Set
Pro přetypování se používá 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)> |
>
>
Výstup:
Python sada je neuspořádaný datový typ, což znamená, že nemůžeme vědět, v jakém pořadí jsou prvky sady uloženy.
{'c', 'b', 'a'} {'d', 'c', 'b', 'a'}> Časová složitost: O(n)
Pomocný prostor: O(n)
Zkontrolujte jedinečné a neměnné pomocí sady Python
Sady Pythonu nemohou mít duplicitní hodnotu a jakmile je vytvořena, nemůžeme její hodnotu změnit.
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)> |
>
>
Výstup:
První kód vysvětluje, že sada nemůže mít duplicitní hodnotu. Každá položka v něm má jedinečnou hodnotu.
Druhý kód generuje chybu, protože po vytvoření sady nemůžeme přiřadit nebo změnit hodnotu. Můžeme pouze přidávat nebo mazat položky v sadě.
{'Geeks', 'for'} TypeError: 'set' object does not support item assignment> Heterogenní prvek se sadou Python
Sady Pythonu v ní mohou ukládat heterogenní prvky, tj. sada může ukládat směs datových typů typu string, integer, boolean atd.
Python3
# Python example demonstrate that a set> # can store heterogeneous elements> myset>=> {>'Geeks'>,>'for'>,>10>,>52.7>,>True>}> print>(myset)> |
>
>
Výstup:
{True, 10, 'Geeks', 52.7, 'for'}> Časová složitost: O(n)
Pomocný prostor: O(n)
Zmrazené sady Pythonu
Zmrazené sady v Pythonu jsou neměnné objekty, které podporují pouze metody a operátory, které vytvářejí výsledek, aniž by ovlivnily zmrazenou sadu nebo sady, na které jsou aplikovány. To lze provést pomocí metody frozenset() v Pythonu.
Zatímco prvky sady lze kdykoli upravit, prvky zmrazené sady zůstanou po vytvoření stejné.
Pokud nejsou předány žádné parametry, vrátí prázdnou sadu zmrazených hodnot.
Krajta
# 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')> |
>
>
Výstup:
Normal Set {'a', 'c', 'b'} Frozen Set {'e', 'g', 'f'}> Časová složitost: O(n)
Pomocný prostor: O(n)
Vnitřní fungování sady
To je založeno na datové struktuře známé jako hashovací tabulka. Pokud je na stejné pozici indexu přítomno více hodnot, pak se hodnota připojí k této pozici indexu a vytvoří se propojený seznam.
V sadách Pythonu jsou implementovány pomocí slovníku s fiktivními proměnnými, kde klíčové bytosti nastavují členové s větší optimalizací na časovou složitost.
Implementace sady:
Sady s mnoha operacemi v jedné hashTable:
Metody pro množiny
Přidávání prvků do sad Pythonu
Vložení do sady se provádí přes set.add( ), kde je vytvořena vhodná hodnota záznamu pro uložení do hashovací tabulky. Stejné jako při kontrole položky, tj. v průměru O(1). V nejhorším případě se to však může stát Na) .
Python3
java rozdělit řetězec podle oddělovače
# 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)> |
>
>
Výstup:
People: {'Idrish', 'Archi', 'Jay'} Set after adding element: {1, 2, 3, 4, 5, 'Idrish', 'Archi', 'Jay', 'Daxit'}> Časová složitost: O(n)
Pomocný prostor: O(n)
Sjednocení na sadách Pythonu
Dvě sady lze sloučit pomocí funkce union() nebo | operátor. K oběma hodnotám hashovací tabulky se přistupuje a prochází se s nimi operacemi sloučení, aby se prvky spojily a zároveň se odstranily duplikáty. Časová složitost toho je O(délka(s1) + čočka(s2)) kde s1 a s2 jsou dvě množiny, jejichž spojení je třeba provést.
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)> |
>
>
Výstup:
Union using union() function {'Karan', 'Idrish', 'Jay', 'Arjun', 'Archil'} Union using '|' operator {'Deepanshu', 'Idrish', 'Jay', 'Raju', 'Archil'}> Časová složitost: O(n)
Pomocný prostor: O(n)
Operace průniku na sadách Pythonu
To lze provést pomocí operátoru intersection() nebo &. Jsou vybrány společné prvky. Jsou podobné iteraci přes seznamy hash a kombinují stejné hodnoty v obou tabulkách. Časová složitost toho je O(min(len(s1), len(s2)), kde s1 a s2 jsou dvě množiny, jejichž spojení je třeba provést.
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)> |
napište json do souboru python
>
>
Výstup:
Intersection using intersection() function {3, 4} Intersection using '&' operator {3, 4}> Časová složitost: O(n)
Pomocný prostor: O(n)
Hledání rozdílů množin v Pythonu
Najít rozdíly mezi sadami. Podobné jako hledání rozdílů v propojeném seznamu. To se provádí pomocí operátorů Different() nebo –. Časová složitost nalezení rozdílu s1 – s2 je O(délka(s1))
Python3
# 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)> |
>
>
Výstup:
Difference of two sets using difference() function {0, 1, 2} Difference of two sets using '-' operator {0, 1, 2}> Časová složitost: O(n)
Pomocný prostor: O(n)
Vymazání sad Pythonu
Metoda Set Clear() vyprázdní celou sadu na místo.
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)> |
>
>
Výstup:
Initial set {1, 2, 3, 4, 5, 6} Set after using clear() function set()> Časová složitost: O(n)
Pomocný prostor: O(n)
V sadách Pythonu však existují dvě hlavní úskalí:
- Sada neuchovává prvky v žádném konkrétním pořadí.
- Do sady Pythonu lze přidat pouze instance neměnných typů.
Časová složitost množin
| Úkon | Průměrný případ | Nejhorší případ | poznámky |
|---|---|---|---|
| x v s | O(1) | Na) | |
| Union s|t | O(jen(s)+jen(t)) | ||
| Křižovatka s&t | O(min(jen(s), jen(t)) | O(jen(s) * jen(t)) | nahraďte min maximálním, pokud t není sada |
| Vícenásobná křižovatka s1&s2&..&sn | (n-1)*O(l) kde l je max(délka(s1),..,délka(sn)) | ||
| Rozdíl s-t | O(pouze(s)) |
Operátoři pro sady
Sady a zmrazené sady podporují následující operátory:
| Operátoři | Poznámky |
|---|---|
| klíč v s | kontrola kontejnmentu |
| klíč není v s | kontrola nezadržování |
| s1 == s2 | s1 je ekvivalentní s2 |
| s1 != s2 | s1 není ekvivalentní s2 |
| s1 <= s2 | s1 je podmnožinou s2 |
| s1 | s1 je vlastní podmnožina s2 |
| s1>= s2 | s1 je nadmnožina s2 |
| s1> s2 | s1 je správná nadmnožina s2 |
| s1 | s2 | spojení s1 a s2 |
| s1 a s2 | průsečík s1 a s2 |
| s1 – s2 | množina prvků v s1, ale ne v s2 |
| s1 ˆ s2 | množina prvků přesně v jednom z s1 nebo s2 |
Nedávné články o Python Set.