Набір у програмуванні на 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.

Хоча елементи набору можна змінити в будь-який час, елементи замороженого набору залишаються незмінними після створення.

Якщо параметри не передано, він повертає порожній заморожений набір.

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 є дві основні підводні камені:

1. Набір не підтримує елементи в певному порядку.
2. До набору 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.