
Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.
Множина – це колекція, яка реалізує основні математичні операції над множинами: перетини (intersection), об’єднання (union), різниця (difference) і симетрична різниця (symmetric difference). Кожен з алгоритмів ми розберемо у відповідному розділі.
Також дивіться інші матеріали цієї серії: бінарне дерево, стеки і черги, динамічний масив, зв’язний список, оцінка складності алгоритму і сортування.
Множина
У математиці множини – це колекції об’єктів, у яких є щось спільне. Наприклад, ми можемо оголосити множину парних позитивних цілих чисел:
[2, 4, 6, 8, 10, ...]
Чи множину непарних позитивних цілих:
[1, 3, 5, 7, 9, ...]
У цих двох множинах немає спільних елементів. Давайте тепер подивимося на множину дільників числа 100:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Тепер ми можемо дізнатися, які дільники числа 100 – непарні, просто дивлячись на множину непарних чисел і на множину дільників, вибираючи ті з чисел, які є в обох. Ми також можемо відповісти на запитання: “Які непарні числа не є дільниками ста”? чи “Які позитивні цілі парні або непарні, не є дільниками ста?”.
На перший погляд це видається не дуже корисним, але це штучний приклад. Припустимо, що у нас є множина всіх працівників підприємства і множина працівників, які пройшли щомісячну перевірку. Тоді ми легко зможемо відповісти на запитання: “Хто з працівників не пройшов перевірку?”.
Ми також можемо додати різні множини і побудувати складніший запит, наприклад: “Хто зі штатних працівників відділу продажів, які мають корпоративну кредитну картку, не пройшов обов’язковий курс підвищення квалфікації?”.
Клас Set
Клас Set
реалізує інтерфейс IEnumerable
і приймає аргумент типу, який є спадкоємцем IComparable
, оскільки для роботи алгоритмів потрібна перевірка елементів на рівність.
Елементи нашої множини зберігатимуться в екземплярі стандартного класу .NET List
, але на практиці для зберігання зазвичай використовуються деревовидні структури, наприклад, двійкове дерево пошуку. Вибір внутрішнього представлення впливатиме на складність алгоритмів роботи з множиною. За використання списку метод Contains
виконуватиметься протягом O (n) часу, тоді як множина, реалізована за допомогою дерева, працюватиме в середньому за O (log n) часу.
Крім методів для роботи з множиною, клас Set
також має конструктор, який приймає IEnumerable
з початковими елементами.
public class Set: IEnumerable where T: IComparable{ private readonly List_items = new List (); public Set (){ } public Set (IEnumerable items) { AddRange (items); } public void Add (T item); public void AddRange (IEnumerable items); public bool Remove (T item); public bool Contains (T item); public int Count { get; } public Set Union (Set other); public Set Intersection (Set other); public Set Difference (Set other); public Set SymmetricDifference (Set other); public IEnumerator GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();}
Метод Add
- Поведінка: додає елементи у множину. Якщо елемент вже є у множині, видає виняток
InvalidOperationException
. - Складність: O (n)
За реалізації методу Add
необхідно вирішити, чи будемо ми дозволяти дубльовані елементи. Якщо у нас є множина:
[1, 2, 3, 4]
Якщо користувач спробує додати число 3, в результаті вийде:
[1, 2, 3, 3, 4]
У деяких випадках це допустимо, але в нашій реалізації ми не підтримуватимемо дублікати. Якщо представити, наприклад, множину студентів коледжу, було б нелогічним додавати в неї того самого студента двічі. Насправді, спроба додати елемент, який вже є, – швидше за все помилка, і наша реалізація класу Set
сприймає її саме так.
Метод Add
використовує метод Contains
, який буде розглянутий далі.
public void Add (T item){ if (Contains (item)) { throw new InvalidOperationException ("Item already exists in Set"); }_items.Add (item);}
Метод AddRange
- Поведінка: додає декілька елементів у множину. Якщо який-небудь з елементів, що додаються, є у множині, або в елементах, що додаються, дублюється, видає виняток
InvalidOperationException
. - Складність: O (m·n), де m – кількість елементів, що вставляються, і n – кількість елементів множини.
public void AddRange (IEnumerable items){ foreach (T item in items) { Add (item); }}
Метод Remove
- Поведінка: видаляє вказаний елемент з множини і повертає
true
. У разі, якщо елемента немає, повертаєfalse
. - Складність: O (n)
public bool Remove (T item){ return_items.Remove (item);}
Метод Contains
- Поведінка: повертає
true
, якщо множина містить вказаний елемент. Якщо ні, то повертаєfalse
. - Складність: O (n)
public bool Contains (T item){ return_items.Contains (item);}
Метод Count
- Поведінка: повертає кількість елементів великої кількості або 0, якщо множина порожня.
- Складність: O (1)
public int Count{ get { return_items.Count; }}
Метод GetEnumerator
- Поведінка: повертає ітератор для перебору елементів множини.
- Складність: отримання ітератора – O (1), обхід елементів множини – O (n).
public IEnumerator GetEnumerator (){ return_items.GetEnumerator ();} System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator (){ return_items.GetEnumerator ();}
Алгоритми
Метод Union
- Поведінка: повертає множину, отриману операцією, об’єднуючи її з указаною.
- Складність: O (m·n), де m і n – кількість елементів переданої і поточної множин відповідно.
Об’єднання множин – це множина, яка містить елементи, наявні хоча б в одній з двох.
Наприклад, є дві множини (виділені червоним):
За операції об’єднання вибираються елементи обох множин. Якщо елемент є в обох множинах, береться тільки одна його копія. Об’єднання двох множин показане жовтим кольором.
Така діаграма, що наочно показує операції з множинами, називається діаграмою Венна.
Інший приклад з використанням множини цілих чисел:
[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
public Set Union (Set other){ Set result = new Set (_ items); foreach (T item in other._ items) { if (!Contains (item)) { result.Add (item); } } return result;}
Метод Intersection
- Поведінка: повертає множину, отриману операцією перетину його з указаною.
- Складність: O (m·n), де m і n – кількість елементів переданої і поточної множин відповідно.
Перетин великих кількостей містить тільки ті елементи, які є в обох множинах. Використовуючи діаграму Венна, перетин можна зображувати так:
Чи використовуючи цілі числа:
[1, 2, 3, 4] intersect [3, 4, 5, 6] = [3, 4]
public Set Intersection (Set other){ Set result = new Set (); foreach (T item in_items) { if (other._ items.Contains (item)) { result.Add (item); } } return result;}
Метод Difference
- Поведінка: повертає множину, що є різницею поточної з указаною.
- Складність: O (m·n), де m і n – кількість елементів переданої і поточної множин відповідно.
Різниця великих кількостей – це всі елементи, які містяться в одній множині (тій, у якої викликається метод), але не містяться в іншій (тій, яка передається аргументом). Діаграма Венна для різниці великих кількостей виглядатиме так:
Чи використовуючи цілі числа:
[1, 2, 3, 4] difference [3, 4, 5, 6] = [1, 2]
public Set Difference (Set other){ Set result = new Set (_ items); foreach (T item in other._ items) { result.Remove (item); } return result;}
Метод Symmetric Difference
- Поведінка: повертає множину, що є симетричною різницею поточної з указаною.
- Складність: O (m·n), де m і n – кількість елементів переданої і поточної множин відповідно.
Симетрична різниця – це всі елементи, які містяться тільки в одній з даних множин. Діаграма Венна для симетричної різниці виглядатиме так:
Чи, використовуючи цілі числа:
[1, 2, 3, 4] symmetric difference [3, 4, 5, 6] = [1, 2, 5, 6]
Ви, можливо, помітили, що симетрична різниця – це “перетин навпаки”. Враховуючи це, давайте спробуємо знайти її, використовуючи наявні операції.
Отже, ми хочемо отримати множину, яка містить усі елементи з двох множин, за винятком тих, які є в обох. Іншими словами, ми хочемо отримати різницю об’єднання двох множин і їх перетину.
Чи якщо розглядати за кроками:
[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6][1, 2, 3, 4] intersection [3, 4, 5, 6] = [3, 4][1, 2, 3, 4, 5, 6] set difference [3, 4] = [1, 2, 5, 6]
Що дає нам потрібний результат: [1, 2, 5, 6]
.
public Set SymmetricDifference (Set other){ Set union = Union (other); Set intersection = Intersection (other); return union.Difference (intersection);}
Метод IsSubset
Ви, можливо, цікавитеся, чому ми не додали метод IsSubset
, який перевіряє, чи міститься одна множина в іншій. Наприклад:
[1, 2, 3] is subset [0, 1, 2, 3, 4, 5] = true
В той час, як:
[1, 2, 3] is subset [0, 1, 2] = false
Справа в тому, що цю перевірку можна провести, використовуючи наявні методи. Наприклад:
[1, 2, 3] difference [0, 1, 2, 3, 4, 5] = []
Порожня множина в результаті говорить нам про те, що всі елементи першої множини містяться в другій, тобто перша є підмножиною другої. Інший спосіб перевірити це:
[1, 2, 3] intersection [0, 1, 2, 3, 4, 5] = [1, 2, 3]
Якщо в результаті ми отримаємо множину з такою ж кількістю елементів, що і первинна, значить, вона є підмножиною другої.
У загальному випадку, звичайно, клас Set
може мати метод IsSubset
(який може бути реалізований ефективніше). Проте варто пам’ятати, що це вже не якась нова можливість, а просто інше застосування наявних.
Далі буде
На цьому все, а наступного разу ми перейдемо до завершальної теми цього циклу статей – алгоритмів сортування.
Переклад статті “The Set Collection”
Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?