Sada v programovaní Python je neusporiadaný dátový typ kolekcie, ktorý je iterovateľný, meniteľný a nemá žiadne duplicitné prvky.
Množina je reprezentovaná { } (hodnoty uzavreté v zložených zátvorkách)
ako zistiť veľkosť monitora
Hlavnou výhodou použitia súpravy na rozdiel od a zoznam , spočíva v tom, že má vysoko optimalizovanú metódu na kontrolu, či je konkrétny prvok obsiahnutý v množine. Toto je založené na dátovej štruktúre známej ako hašovacia tabuľka. Keďže množiny nie sú zoradené, nemôžeme pristupovať k položkám pomocou indexov, ako to robíme v zoznamoch.
Príklad sád Pythonu
Python3
var>=> {>'Geeks'>,>'for'>,>'Geeks'>}> type>(var)> |
>
>
Výkon:
set>
Časová zložitosť: O(1)
Pomocný priestor: O(1)
Typ Casting s metódou Python Set
Na pretypovanie sa používa metóda 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ýkon:
Python sada je neusporiadaný dátový typ, čo znamená, že nemôžeme vedieť, v akom poradí sú prvky sady uložené.
{'c', 'b', 'a'} {'d', 'c', 'b', 'a'}> Časová zložitosť: O(n)
Pomocný priestor: O(n)
Skontrolujte jedinečné a nemenné pomocou sady Python
Množiny Pythonu nemôžu mať duplicitnú hodnotu a po jej vytvorení už nemôžeme zmeniť jej hodnotu.
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)> |
>
java pridať do poľa
>
Výkon:
Prvý kód vysvetľuje, že množina nemôže mať duplicitnú hodnotu. Každá položka v ňom má jedinečnú hodnotu.
Druhý kód generuje chybu, pretože po vytvorení sady nemôžeme priradiť alebo zmeniť hodnotu. Položky v súprave môžeme iba pridávať alebo odstraňovať.
{'Geeks', 'for'} TypeError: 'set' object does not support item assignment> Heterogénny prvok so sadou Python
Množiny Pythonu v ňom môžu ukladať heterogénne prvky, t. j. množina môže uchovávať zmes údajových typov typu reťazec, celé číslo, boolean atď.
Python3
# Python example demonstrate that a set> # can store heterogeneous elements> myset>=> {>'Geeks'>,>'for'>,>10>,>52.7>,>True>}> print>(myset)> |
>
>
Výkon:
{True, 10, 'Geeks', 52.7, 'for'}> Časová zložitosť: O(n)
Pomocný priestor: O(n)
Zamrznuté sady Pythonu
Mrazené súpravy v Pythone sú nemenné objekty, ktoré podporujú iba metódy a operátory, ktoré vytvárajú výsledok bez ovplyvnenia zmrazenej množiny alebo množín, na ktoré sú aplikované. Dá sa to urobiť pomocou metódy frozenset() v Pythone.
Zatiaľ čo prvky množiny možno kedykoľvek upraviť, prvky zamrznutej množiny zostanú po vytvorení rovnaké.
Ak nie sú zadané žiadne parametre, vráti prázdnu zmrazenú sadu.
Python
# 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ýkon:
Normal Set {'a', 'c', 'b'} Frozen Set {'e', 'g', 'f'}> Časová zložitosť: O(n)
Pomocný priestor: O(n)
Vnútorné fungovanie súpravy
Je to založené na dátovej štruktúre známej ako hašovacia tabuľka. Ak sa na rovnakej pozícii indexu nachádza viacero hodnôt, hodnota sa pripojí k tejto pozícii indexu a vytvorí sa tak prepojený zoznam.
Sady Pythonu sú implementované pomocou slovníka s fiktívnymi premennými, kde kľúčové bytosti nastavujú členovia s väčšou optimalizáciou z hľadiska časovej zložitosti.
Implementácia sady:
Sady s množstvom operácií na jednej HashTable:
Metódy pre množiny
Pridávanie prvkov do sád Pythonu
Vloženie do súpravy sa vykonáva cez set.add( ), kde sa vytvorí vhodná hodnota záznamu na uloženie do hašovacej tabuľky. Rovnaké ako pri kontrole položky, t.j. v priemere O(1). V najhoršom prípade sa to však môže stať O(n) .
Python3
# 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)> |
bash rozdeliť reťazec oddeľovačom
>
>
Výkon:
People: {'Idrish', 'Archi', 'Jay'} Set after adding element: {1, 2, 3, 4, 5, 'Idrish', 'Archi', 'Jay', 'Daxit'}> Časová zložitosť: O(n)
Pomocný priestor: O(n)
Operácia únie na sadách Python
Dve sady je možné zlúčiť pomocou funkcie union() alebo | operátor. Obe hodnoty hash tabuľky sú prístupné a prechádzajú sa s nimi vykonaním operácie zlúčenia, aby sa prvky spojili a zároveň sa odstránili duplikáty. Časová zložitosť tohto je O(len(s1) + šošovka(s2)) kde s1 a s2 sú dve množiny, ktorých spojenie je potrebné vykonať.
Python3
vek rihanny
# 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ýkon:
Union using union() function {'Karan', 'Idrish', 'Jay', 'Arjun', 'Archil'} Union using '|' operator {'Deepanshu', 'Idrish', 'Jay', 'Raju', 'Archil'}> Časová zložitosť: O(n)
Pomocný priestor: O(n)
Operácia križovatiek na množinách Pythonu
Dá sa to urobiť pomocou intersection() alebo operátora &. Sú vybrané spoločné prvky. Sú podobné iterácii cez zoznamy hash a kombinujú rovnaké hodnoty v oboch tabuľkách. Časová zložitosť je O(min(dĺžka(s1), dĺžka(s2)), kde s1 a s2 sú dve množiny, ktorých spojenie je potrebné vykonať.
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)> |
>
>
Výkon:
Intersection using intersection() function {3, 4} Intersection using '&' operator {3, 4}> Časová zložitosť: O(n)
Pomocný priestor: O(n)
Hľadanie rozdielov množín v Pythone
Nájsť rozdiely medzi sadami. Podobne ako pri hľadaní rozdielov v prepojenom zozname. To sa vykonáva pomocou operátora Different() alebo –. Časová zložitosť nájdenia rozdielu s1 – s2 je O(len(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ýkon:
Difference of two sets using difference() function {0, 1, 2} Difference of two sets using '-' operator {0, 1, 2}> Časová zložitosť: O(n)
Pomocný priestor: O(n)
Vymazanie sád Pythonu
Metóda Set Clear() vyprázdni celú množinu na mieste.
Python3
slf4j vs log4j
# 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ýkon:
Initial set {1, 2, 3, 4, 5, 6} Set after using clear() function set()> Časová zložitosť: O(n)
Pomocný priestor: O(n)
V súboroch Pythonu však existujú dve hlavné úskalia:
- Sada neobsahuje prvky v žiadnom konkrétnom poradí.
- Do sady Python možno pridať iba inštancie nemenných typov.
Časová zložitosť Množín
| Prevádzka | Priemerný prípad | V najhoršom prípade | poznámky |
|---|---|---|---|
| x v s | O(1) | O(n) | |
| Union s|t | O(len(s)+len(t)) | ||
| Križovatka s&t | O(min(len(s), len(t)) | O(len(s) * len(t)) | nahraďte min maximálnym, ak t nie je množina |
| Viacnásobná križovatka s1&s2&..&sn | (n-1)*O(l) kde l je max(len(s1),..,len(sn)) | ||
| Rozdiel s-t | O(len(s)) |
Operátory pre súpravy
Sady a zmrazené súpravy podporujú nasledujúce operátory:
| Operátori | Poznámky |
|---|---|
| kľúč v s | kontrola kontajnmentu |
| kľúč nie je v s | kontrola nezadržania |
| s1 == s2 | s1 je ekvivalentné s2 |
| s1 != s2 | s1 nie je 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ávna nadmnožina s2 |
| s1 | s2 | spojenie s1 a s2 |
| s1 a s2 | priesečník s1 a s2 |
| s1 – s2 | množina prvkov v s1, ale nie v s2 |
| s1 ˆ s2 | množina prvkov presne v jednom z s1 alebo s2 |
Nedávne články o Python Set.