Набір у програмуванні на Python — це невпорядкований тип колекції даних, який можна ітерувати, змінювати та не мати повторюваних елементів.
Набір представлено { } (значення взяті у фігурні дужки)
Основна перевага використання набору, на відміну від a список , полягає в тому, що він має оптимізований метод для перевірки, чи міститься певний елемент у наборі. Це базується на структурі даних, відомій як хеш-таблиця. Оскільки набори не впорядковані, ми не можемо отримати доступ до елементів за допомогою індексів, як у списках.
Приклад наборів Python
Python3
var>=> {>'Geeks'>,>'for'>,>'Geeks'>}> type>(var)> |
>
>
Вихід:
set>
Часова складність: O(1)
Допоміжний простір: O(1)
Приведення типу за допомогою методу Python Set
Для приведення типу використовується метод Python set().
Python3
# typecasting list to set> myset>=> set>([>'a'>,>'b'>,>'c'>])> print>(myset)> # Adding element to the set> myset.add(>'d'>)> print>(myset)> |
>
>
Вихід:
Набір Python є невпорядкованим типом даних, що означає, що ми не можемо знати, в якому порядку зберігаються елементи набору.
{'c', 'b', 'a'} {'d', 'c', 'b', 'a'}> Часова складність: O(n)
Допоміжний простір: O(n)
Перевірте унікальність і незмінність за допомогою Python Set
Набори Python не можуть мати повторювані значення, і коли вони створені, ми не можемо змінити їх значення.
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)> |
>
>
Вихід:
Перший код пояснює, що набір не може мати повторюване значення. Кожен предмет у ньому є унікальною цінністю.
Другий код генерує помилку, оскільки ми не можемо призначити або змінити значення після створення набору. Ми можемо лише додавати або видаляти елементи в наборі.
{'Geeks', 'for'} TypeError: 'set' object does not support item assignment> Гетерогенний елемент із набором Python
Набори Python можуть зберігати в ньому неоднорідні елементи, тобто набір може зберігати суміш рядкових, цілих, логічних тощо типів даних.
Python3
# Python example demonstrate that a set> # can store heterogeneous elements> myset>=> {>'Geeks'>,>'for'>,>10>,>52.7>,>True>}> print>(myset)> |
>
>
Вихід:
{True, 10, 'Geeks', 52.7, 'for'}> Часова складність: O(n)
Допоміжний простір: O(n)
Заморожені набори Python
Заморожені набори у Python — це незмінні об’єкти, які підтримують лише методи й оператори, які створюють результат, не впливаючи на заморожений набір чи набори, до яких вони застосовуються. Це можна зробити за допомогою методу frozenset() у Python.
Хоча елементи набору можна змінити в будь-який час, елементи замороженого набору залишаються незмінними після створення.
Якщо параметри не передано, він повертає порожній заморожений набір.
додати рядок java
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')> |
>
>
Вихід:
Normal Set {'a', 'c', 'b'} Frozen Set {'e', 'g', 'f'}> Часова складність: O(n)
Допоміжний простір: O(n)
Внутрішня робота Set
Це базується на структурі даних, відомій як хеш-таблиця. Якщо в одній позиції індексу присутні кілька значень, тоді значення додається до цієї позиції індексу, щоб сформувати зв’язаний список.
У Python Sets реалізовано за допомогою словника з фіктивними змінними, де ключові істоти є членами набору з більшою оптимізацією до часової складності.
Реалізація набору:
Набори з численними операціями на одній HashTable:
Методи для множин
Додавання елементів до наборів Python
Вставка в набір здійснюється через set.add( ), де створюється відповідне значення запису для зберігання в хеш-таблиці. Те саме, що перевірка елемента, тобто O(1) у середньому. Проте в гіршому випадку це може статися 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)> |
>
>
Вихід:
People: {'Idrish', 'Archi', 'Jay'} Set after adding element: {1, 2, 3, 4, 5, 'Idrish', 'Archi', 'Jay', 'Daxit'}> Часова складність: O(n)
Допоміжний простір: O(n)
Операція об’єднання над наборами Python
Два набори можна об’єднати за допомогою функції union() або | оператор. Доступ до обох значень хеш-таблиці здійснюється за допомогою операції злиття, яка виконується над ними, щоб поєднати елементи, водночас дублікати видаляються. Часова складність цього O(len(s1) + len(s2)) де s1 і s2 — два набори, об’єднання яких необхідно виконати.
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)> |
>
>
Вихід:
Union using union() function {'Karan', 'Idrish', 'Jay', 'Arjun', 'Archil'} Union using '|' operator {'Deepanshu', 'Idrish', 'Jay', 'Raju', 'Archil'}> Часова складність: O(n)
Допоміжний простір: O(n)
Операція перетину над наборами Python
Це можна зробити за допомогою оператора intersection() або &. Загальні елементи вибрано. Вони схожі на ітерацію по хеш-списках і поєднання однакових значень в обох таблицях. Часова складність цього дорівнює O(min(len(s1), len(s2)), де s1 і s2 – два набори, об’єднання яких потрібно виконати.
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)> |
>
>
Вихід:
Intersection using intersection() function {3, 4} Intersection using '&' operator {3, 4}> Часова складність: O(n)
Допоміжний простір: O(n)
Пошук відмінностей множин у Python
Знайти відмінності між наборами. Подібно до пошуку відмінностей у пов’язаному списку. Це робиться за допомогою оператора difference() або –. Часова складність знаходження різниці s1 – s2 становить 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)> |
>
>
Вихід:
Difference of two sets using difference() function {0, 1, 2} Difference of two sets using '-' operator {0, 1, 2}> Часова складність: O(n)
Допоміжний простір: O(n)
Очищення наборів Python
Метод Set Clear() очищає весь набір на місці.
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)> |
>
>
Вихід:
Initial set {1, 2, 3, 4, 5, 6} Set after using clear() function set()> Часова складність: O(n)
Допоміжний простір: O(n)
Однак у наборах Python є дві основні підводні камені:
- Набір не підтримує елементи в певному порядку.
- До набору Python можна додати лише екземпляри незмінних типів.
Часова складність множин
| Операція | Середній випадок | Найгірший випадок | примітки |
|---|---|---|---|
| x в s | О(1) | O(n) | |
| Союз с|т | O(len(s)+len(t)) | ||
| Перехрестя с&т | O(min(len(s), len(t)) | O(довжина(s) * довжина(t)) | замініть min на max, якщо t не є набором |
| Багаторазовий перетин s1&s2&..&sn | (n-1)*O(l), де l є max(len(s1),..,len(sn)) | ||
| Різниця с-т | O(лише(и)) |
Оператори для множин
Набори та заморожені набори підтримують такі оператори:
| Оператори | Примітки |
|---|---|
| ключ у с | перевірка збереження |
| ключ не в s | перевірка на неутримання |
| s1 == s2 | s1 еквівалентний s2 |
| s1 != s2 | s1 не еквівалентний s2 |
| s1 <= s2 | s1 є підмножиною s2 |
| s1 | s1 є належною підмножиною s2 |
| s1>= s2 | s1 є надмножиною s2 |
| s1> s2 | s1 є належним надмножиною s2 |
| s1 | s2 | об'єднання s1 і s2 |
| s1 і s2 | перетин s1 і s2 |
| s1 – s2 | набір елементів в s1, але не в s2 |
| s1 ˆ s2 | набір елементів в одному з s1 або s2 |
Останні статті про Python Set.