Множина (тип даних)

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Множина (структура даних))
Перейти до: навігація, пошук

Множина — абстрактний тип даних і структура даних в інформатиці, є реалізацією математичного об'єкта скінченна множина.

Дані типу «множина» дозволяють зберігати обмежене число значень певного типу без певного порядку. Повторення значень, як правило, неприпустимо. За винятком того, що множина в програмуванні скінченне, воно загалом відповідає концепції математичної множини. Для цього типу в мовах програмування зазвичай передбачені стандартні операції над множинами.

Залежно від ідеології, різні мови програмування розглядають множину як простий чи складний тип даних.

Теорія типів[ред.ред. код]

В теорії типів[en] множини, в основному, ототожнюються з індикаторною функцією (характеристичною функцією): таким чином, множина значень типу   може бути позначена  або . (Підтипи або підмножини можуть бути змодельовані уточнювальними типами, а фактор-множини замінені сетоїдами[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), яка подібна на множину, але дозволяє дублікати (повторення однакових значень).

Посилання[ред.ред. код]