Множина — абстрактний тип даних і структура даних в інформатиці, є реалізацією математичного об'єкта скінченна множина.
Дані типу «множина» дозволяють зберігати обмежене число значень певного типу без певного порядку. Повторення значень, як правило, неприпустимо. За винятком того, що множина в програмуванні скінченне, воно загалом відповідає концепції математичної множини. Для цього типу в мовах програмування зазвичай передбачені стандартні операції над множинами.
Залежно від ідеології, різні мови програмування розглядають множину як простий чи складний тип даних.
Теорія типів
В теорії типів множини, в основному, ототожнюються з індикаторною функцією (характеристичною функцією): таким чином, множина значень типу може бути позначена або . (Підтипи або підмножини можуть бути змодельовані уточнювальними типами, а фактор-множини замінені сетоїдами[en].) Характеристична функція множини визначається так:
Теоретично, велика кількість інших абстрактних структур даних може розглядатись як множина з додатковими операціями і/або додатковими аксіомами, накладеними на стандартні операції. Наприклад, абстрактна структура даних купа розглядається як множина структур із min(S)
операцією, яка повертає найменший елемент.
Операції
Основні теоретико-множинні операції
Визначають такі операції алгебри множин:
union(S,T)
: повертає об’єднання множин S і T.intersection(S,T)
: повертає перетин множин S і T.difference(S,T)
: повертає різницю множин S і T.subset(S,T)
: предикат, що перевіряє чи є множина S підмножиною множини T.
Статичні множини
Типові операції, які задаються статичною структурою множини S:
is_element_of(x,S)
: перевіряє входження значення X у множину S.is_empty(S)
: перевіряє чи є множина S порожньою.size(S)
абоcardinality(S)
: повертає число елементів S множини.iterate(S)
: функція, що повертає один довільно вибраний елемент множини S при кожному виклику.enumerate(S)
: повертає у довільному порядку список елементів, які містяться у множини S.build()
: створює множину зі значеннями .- create_from(collection): створює нову множину, яка містить у собі всі елементи даної сукупності або всі елементи, повернуті ітератором.
Динамічні множини
Динамічні структури зазвичай додають:
create()
: створює нову, спочатку порожню множину.create_with_capacity(n)
: створює нову, спочатку порожню множину, але розмірністю n.add(x,S)
: додає елемент x до множини S, якщо такого ще не існуєremove(S,x)
: видаляє елемент x із множини S, якщо існує.capacity(S)
: повертає максимальне число елементів, яке може містити S.
Деякі множинні структури можуть дозволити собі використовувати лише деякі із цих операцій. Потреба кожної операції буде залежати від реалізації, а також конкретних значень, що входять до множини, і порядку, у якому вони розташовані у множині.
Додаткові операції
Існує багато інших операцій, що можуть бути визначені щодо термінів вище, такі як:
pop(S)
: повертає довільно вибраний елемент множини S, і видаляє його з S.pick(S)
: повертає довільно вибраний елемент множини S. З функціональної точки зору мутаторрор
може бути інтерпретований як пара селекторів(pick, rest)
деrest
повертає множину, що включає в себе усі елементи, окрім вибраного.map(F,S)
: повертає множину різних значень, отриманих від F до кожного елемента S.filter(P,S)
: повертає підмножину елементів, що містяться у S, та задовольняють даний предикат P.fold(A,F,S)
: повертає значення A, після застосування формулидля кожного елемента e у S, для деякої бінарної операції F. F повинна бути асоціативною і комунікативною, для того, щоб бути чітко визначеною.
clear(S)
: видаляє усі елементи S.equal(S, S)
: перевіряє чи є дві множини рівними (тобто мають усі однакові елементи).- hash(S): повертає хеш-значення для статичної множини S, таке, якщо
equal(S,S)
тодіhash(S) = hash(S)
.
Операції для множин, що містять елементи спеціального типу:
sum(S)
: повертає суму усіх елементів множини S, для деякого визначення суми. Наприклад, сума для цілих або дійсних чисел може бути визначена так:fold(0, add, S)
.collapse(S)
: дано множину множин, повертає об’єднання ряду множин. Наприклад,collapse({{1}, {2, 3}}) == {1, 2, 3}
може розглядатись як сума.flatten(S)
: дано множину, що складається із множин і атомних елементів (елементи, що не є множиною), повертає множину, елементи якої є початковою множиною верхнього рівня або елементи множини, які входять до цієї множини. Іншими словами, видаляє рівень вкладеності, такий як: collapse але дозволяє атоми. Це може бути зроблено один раз або декілька разів, для того, щоб отримати множину тільки атомних елементів. Наприклад,flatten({1, {2, 3}}) == {1, 2, 3}
.nearest(S,x)
: повертає елемент множини S, що є найближчим до значення x.min(S)
,max(S)
: повертає мінімальний/максимальний елементи множини S.
Реалізація
Множини можна реалізувати, використовуючи різні структури даних, які забезпечують різні часові затрати і просторові компроміси для різних операцій. Деякі реалізації створені для того, щоб покращити ефективність дуже спеціалізованих операцій, таких як: nearest
або union
. Реалізації описані для «загального використання», як правило, прагнуть оптимізувати element_of
, add
та delete
операції. Простою реалізацією є використання списку (абстрактний тип даних), ігноруючи порядок елементів та уникаючи їх повтору. Це просто, але неефективно, бо операції на перевірку належності у множині чи видалення елементу O(n) повинні сканувати увесь список. Замість цього, множини часто реалізуються з використанням більш ефективних структур даних, а саме, різних видів дерев, префіксних дерев або хеш-таблиць.
Так як множини можна інтерпретувати як щось на зразок карти (індикаторною функцією), вони зазвичай реалізуються у той самий спосіб, що і (часткові) карти (асоціативні масиви) – у цьому разі значення кожної пари ключа-значення має тип одиниці або контрольного елемента (наприклад, 1), а саме збалансоване дерево для відсортованого масиву (O(log n) для більшості операцій) або хеш-таблицю для невідсортованого масиву (O(1) в середньому випадку, але O(n) в найгіршому випадку, для більшості операцій). Відсортована лінійна хеш-таблиця може бути використана для забезпечення детерміновано впорядкованих множин.
Крім того, у мовах, які підтримують карти, а не множини, множини можуть бути реалізовані на основі карти. Наприклад, загальна ідіома у мові програмування Perl, що конвертує масив у хеш, чиї параметри приймають параметри контрольного елемента, для використання як масиву:
my %elements = map { $_ => 1 } @elements;
Множина в Паскалі
У мові Паскаль множина — складовий тип даних, який зберігає інформацію про присутність у множині об'єктів будь-якого рахункового типу. Потужність цього типу визначає розмір множини — 1 біт на елемент. У Turbo Pascal є обмеження на 256 елементів, у деяких інших реалізаціях це обмеження ослаблене. Приклад роботи з множинами:
type
{визначаємо базові для множин зліченний тип і тип-діапазон}
colors = (red,green,blue);
smallnumbers = 0..10;
{визначаємо множини з наших типів}
colorset = set of colors;
numberset = set of smallnumbers;
{можна і не задавати тип окремо}
anothernumberset = set of 0..20;
{оголошуємо змінні типу множин}
var
nset1,nset2,nset3:numberset;
cset:colorset;
begin
nset1 := [0,2,4,6,8,10]; {задаємо у вигляді конструктора множини}
cset := [red,blue]; {простим перерахуванням елементів}
nset2 := [1,3,9,7,5]; {порядок перерахування не важливий}
nset3 := []; {пуста множина}
include(nset3,7); {додавання елемента}
exclude(nset3,7); {вилучення елемента}
nset1 := [0..5]; {можливо задавати елементи діапазоном}
nset3 := nset1 + nset2; {об'єднання}
nset3 := nset1 * nset2; {перетин}
nset3 := nset1 - nset2; {різниця}
if (5 in nset2) or {перевірка на входження елемента}
(green in cset) then
{…}
end.
Мультимножина
Узагальненням поняття множини є мультимножина чи сумка (англ. bag), яка подібна на множину, але дозволяє дублікати (повторення однакових значень).
Джерела
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10. Елементарні структури даних. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
![]() |
Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її. |