Set (абстрактный тип данных)

В информатике набор — это абстрактный тип данных , который может хранить уникальные значения без какого-либо определенного порядка . Это компьютерная реализация математической концепции конечного множества . В отличие от большинства других типов коллекций , вместо извлечения определенного элемента из набора обычно проверяется членство значения в наборе.

Некоторые структуры данных наборов предназначены для статических или замороженных наборов , которые не изменяются после их создания. Статические наборы допускают только операции запроса над своими элементами — например, проверку наличия заданного значения в наборе или перечисление значений в произвольном порядке. Другие варианты, называемые динамическими или изменяемыми наборами , также позволяют вставлять и удалять элементы из набора.

Мультимножество — это особый вид набора , в котором элемент может появляться в наборе несколько раз.

Теория типов

В теории типов множества обычно отождествляются с их индикаторной функцией (характеристической функцией): соответственно набор значений типа может обозначаться или . (Подтипы и подмножества могут быть смоделированы уточняющими типами , а наборы факторов могут быть заменены сетоидами .) Характеристическая функция набора определяется как: $А$ $2^{A}$ ${\mathcal {P}}(A)$ $F$ $S$

F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0, & {\mbox{if }}x\not \in S\end{cases }}

Теоретически многие другие абстрактные структуры данных можно рассматривать как структуры-множества с дополнительными операциями и/или дополнительными аксиомами , налагаемыми на стандартные операции. Например, абстрактную кучу можно рассматривать как структуру набора с операцией, возвращающей элемент с наименьшим значением.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)или : возвращает количество элементов в S.cardinality(S)
iterate(S): возвращает функцию, которая возвращает еще одно значение S при каждом вызове в произвольном порядке.
enumerate(S): возвращает список, содержащий элементы S в произвольном порядке.
build(x₁,x₂,…,x_n,): создает структуру набора со значениями x ₁ , x ₂ ,..., x _n .
create_from(collection): создает новую структуру набора, содержащую все элементы данной коллекции или все элементы, возвращаемые данным итератором .

Динамические наборы

Структуры динамических наборов обычно добавляют:

create(): создает новую, изначально пустую структуру набора.
- create_with_capacity(n): создает новую структуру набора, изначально пустую, но способную содержать до n элементов.
add(S,x): добавляет элемент x в S , если он еще не присутствует.
remove(S, x): удаляет элемент x из S , если он присутствует.
capacity(S): возвращает максимальное количество значений, которые может хранить S.

Некоторые структуры наборов могут разрешать только некоторые из этих операций. Стоимость каждой операции будет зависеть от реализации и, возможно, также от конкретных значений, хранящихся в наборе, и порядка их вставки.

Дополнительные операции

Существует множество других операций, которые (в принципе) могут быть определены в терминах вышеизложенного, например:

pop(S): возвращает произвольный элемент S , удаляя его из S. ^[1]
pick(S): возвращает произвольный элемент S. ^[2]^[3]^[4] Функционально мутатор popможно интерпретировать как пару селекторов (pick, rest),, которая restвозвращает набор, состоящий из всех элементов, кроме произвольного элемента. ^[5] Можно интерпретировать в терминах iterate. ^[а]
map(F,S): возвращает набор различных значений, полученных в результате применения функции F к каждому элементу S.
filter(P,S): возвращает подмножество, содержащее все элементы S , удовлетворяющие заданному предикату P.
fold(A₀,F,S): возвращает значение A _{| С |} после применения к каждому элементу e из S для некоторой бинарной операции F. F должен быть ассоциативным и коммутативным, чтобы это было четко определено.A_i+1 := F(A_i, e)
clear(S): удалить все элементы S.
equal(S₁', S₂'): проверяет, равны ли два заданных набора (т.е. содержат ли они все и только одни и те же элементы).
hash(S): возвращает хеш-значение для статического набора S , такое, что if thenequal(S₁, S₂)hash(S₁) = hash(S₂)

Другие операции могут быть определены для множеств с элементами специального типа:

sum(S): возвращает сумму всех элементов S для некоторого определения «суммы». Например, для целых или действительных чисел он может быть определен как .fold(0, add, S)
collapse(S): учитывая набор множеств, вернуть объединение. ^[6] Например, collapse({{1}, {2, 3}}) == {1, 2, 3}. Можно считать своего рода sum.
flatten(S): учитывая набор, состоящий из наборов и атомарных элементов (элементов, которые не являются наборами), возвращает набор, элементы которого являются атомарными элементами исходного набора верхнего уровня или элементами содержащихся в нем наборов. Другими словами, уберите уровень вложенности — вроде бы, collapse,но разрешите атомы. Это можно сделать один раз или рекурсивно сгладить, чтобы получить набор только атомарных элементов. ^[7] Например, flatten({1, {2, 3}}) == {1, 2, 3}.
nearest(S,x): возвращает элемент S , ближайший по значению к x (по некоторой метрике ).
min(S), : возвращает минимальный/максимальный элемент S .max(S)

Реализации

Наборы могут быть реализованы с использованием различных структур данных , которые обеспечивают различные компромиссы во времени и пространстве для различных операций. Некоторые реализации предназначены для повышения эффективности очень специализированных операций, таких как nearestили union. Реализации, описываемые как «общего использования», обычно стремятся оптимизировать операции element_of, addи delete. Простая реализация — использовать список , игнорируя порядок элементов и стараясь избегать повторяющихся значений. Это просто, но неэффективно, поскольку такие операции, как членство в наборе или удаление элемента, требуют O ( n ), поскольку они требуют сканирования всего списка. ^[b] Вместо этого множества часто реализуются с использованием более эффективных структур данных, особенно различных разновидностей деревьев , попыток или хеш-таблиц .

Поскольку наборы можно интерпретировать как своего рода карту (с помощью индикаторной функции), наборы обычно реализуются так же, как (частичные) карты ( ассоциативные массивы ) – в этом случае значение каждой пары ключ-значение имеет тип единицы или контрольное значение (например, 1), а именно самобалансирующееся двоичное дерево поиска для отсортированных наборов ^{[ необходимо определение ]} (которое имеет O(log n) для большинства операций) или хеш-таблицу для несортированных наборов (которая имеет O(1) в среднем случае, но O(n) в худшем случае для большинства операций). Сортированная линейная хэш-таблица ^[8] может использоваться для создания детерминированно упорядоченных наборов.

Более того, в языках, поддерживающих карты, но не множества, множества могут быть реализованы с помощью карт. Например, распространенная идиома программирования в Perl , которая преобразует массив в хэш, значениями которого являются контрольное значение 1, для использования в качестве набора:

мои %elements = карта { $_ => 1 } @elements ;

Другие популярные методы включают массивы . В частности, подмножество целых чисел 1.. n может быть эффективно реализовано как n -битный битовый массив , который также поддерживает очень эффективные операции объединения и пересечения. Карта Блума реализует набор вероятностно, используя очень компактное представление, но рискуя небольшой вероятностью ложных срабатываний при запросах.

Операции с логическими множествами могут быть реализованы в терминах более элементарных операций ( pop, clearи add), но специализированные алгоритмы могут давать более низкие асимптотические границы времени. Если наборы реализованы, например, как отсортированные списки, простой алгоритм займет время, пропорциональное длине m S , умноженной на длину n T ; тогда как вариант алгоритма слияния списков выполнит работу за время, пропорциональное m + n . Более того, существуют специализированные структуры данных набора (такие как структура данных объединения-поиска ), которые оптимизированы для одной или нескольких из этих операций за счет других.union(S,T)

Языковая поддержка

Одним из первых языков, поддерживавших множества, был Паскаль ; многие языки теперь включают его, будь то в основной язык или в стандартную библиотеку .

В C++ Стандартная библиотека шаблонов (STL) предоставляет setкласс шаблонов, который обычно реализуется с использованием двоичного дерева поиска (например, красно-черного дерева ); STL SGI также предоставляет классhash_set шаблона, который реализует набор с использованием хеш-таблицы. В C++11 есть поддержка unordered_setкласса шаблона, который реализован с использованием хеш-таблицы. В наборах ключами являются сами элементы, в отличие от упорядоченных контейнеров, где доступ к элементам осуществляется с использованием их (относительной или абсолютной) позиции. Элементы множества должны иметь строгий слабый порядок.
Стандартная библиотека Rust предоставляет общие типы HashSetи BTreeSetтипы.
Java предлагает Set интерфейс для поддержки наборов ( HashSetкласс реализует его с использованием хеш-таблицы) и SortedSetподинтерфейс для поддержки отсортированных наборов ( TreeSetкласс реализует его с использованием двоичного дерева поиска).
Платформа Apple Foundation (часть Cocoa ) предоставляет классы Objective-CNSSet , NSMutableSet, NSCountedSet, NSOrderedSetи NSMutableOrderedSet. API CoreFoundation предоставляют типы CFSet и CFMutableSet для использования в C.
Начиная с версии 2.4 в Python есть встроенные типы set и Frozenset, а начиная с Python 3.0 и 2.7 поддерживаются непустые литералы множества с использованием синтаксиса фигурных скобок, например: {x, y, z}; пустые наборы должны создаваться с помощью set(), поскольку Python использует {}для представления пустого словаря.
.NET Framework предоставляет универсальный интерфейс HashSetи SortedSetклассы, реализующие универсальный ISetинтерфейс.
Библиотека классов SmalltalkSet включает и IdentitySet, использующие равенство и идентичность для проверки включения соответственно. Многие диалекты предоставляют варианты для сжатого хранения ( NumberSet, CharacterSet), упорядочивания ( OrderedSet, SortedSetи т. д.) или слабых ссылок ( WeakIdentitySet).
Стандартная библиотека Ruby включает модульset , который содержит Setклассы SortedSet, реализующие наборы с использованием хеш-таблиц, причем последняя позволяет выполнять итерацию в отсортированном порядке.
Стандартная библиотека OCaml содержит модульSet , который реализует структуру данных функционального набора с использованием двоичных деревьев поиска.
Реализация Haskell GHC предоставляет модуль, которыйData.Set реализует неизменяемые множества с использованием двоичных деревьев поиска. ^[9]
Пакет Tcl Tcllib предоставляет модуль set, который реализует структуру данных set на основе списков TCL.
Стандартная библиотека Swift содержит Setтип, начиная с Swift 1.2.
JavaScript представлен Setкак стандартный встроенный объект в стандарте ECMAScript 2015 ^[10] .
В стандартной библиотеке Erlangsets есть модуль.
Clojure имеет буквальный синтаксис для хешированных наборов, а также реализует отсортированные наборы.
LabVIEW имеет встроенную поддержку наборов, начиная с версии 2019.
Ада предоставляет пакеты Ada.Containers.Hashed_Setsи Ada.Containers.Ordered_Sets.

Как отмечалось в предыдущем разделе, в языках, которые не поддерживают наборы напрямую, но поддерживают ассоциативные массивы , наборы можно эмулировать с помощью ассоциативных массивов, используя элементы в качестве ключей и используя фиктивные значения в качестве значений, которые игнорируются.

Мультисет

Обобщением понятия набора является понятие мультимножества или сумки , которое похоже на набор, но допускает повторяющиеся («равные») значения (дубликаты). Это используется в двух разных смыслах: либо равные значения считаются идентичными и просто подсчитываются, либо равные значения считаются эквивалентными и сохраняются как отдельные элементы. Например, зная список людей (по именам) и возрастов (в годах), можно построить мультинабор возрастов, который просто подсчитывает количество людей данного возраста. В качестве альтернативы можно создать мультимножество людей, в котором два человека считаются эквивалентными, если их возрасты одинаковы (но могут быть разными людьми и иметь разные имена), и в этом случае каждая пара (имя, возраст) должна быть сохранена, и выбор по данному возрасту дает всех людей данного возраста.

Формально объекты в информатике могут считаться «равными» по одному отношению эквивалентности , но при этом различаться по другому отношению. Некоторые типы реализаций мультимножеств будут хранить отдельные равные объекты как отдельные элементы в структуре данных; в то время как другие свернут его до одной версии (первой встреченной) и сохранят положительное целое число кратности элемента.

Как и в случае с множествами, мультимножества естественным образом могут быть реализованы с использованием хеш-таблицы или деревьев, которые дают разные характеристики производительности.

Набор всех сумок типа T задается выражением Bag T. Если с помощью мультимножества считать одинаковые элементы одинаковыми и просто считать их, то мультимножество можно интерпретировать как функцию от входной области до неотрицательных целых чисел ( натуральные числа ), обобщающие идентификацию множества с его индикаторной функцией. В некоторых случаях мультимножество в этом смысле подсчета может быть обобщено, чтобы допускать отрицательные значения, как в Python.

Стандартная библиотека шаблонов C++ реализует как отсортированные, так и несортированные мультимножества. Он предоставляет multisetкласс для отсортированного мультимножества, как своего рода ассоциативный контейнер , который реализует это мультимножество с помощью самобалансирующегося бинарного дерева поиска . Он предоставляет unordered_multisetкласс для несортированного мультимножества, как своего рода неупорядоченный ассоциативный контейнер , который реализует это мультимножество с помощью хеш-таблицы . Несортированное мультимножество является стандартом C++11 ; ранее STL SGI предоставлял hash_multisetкласс, который был скопирован и в конечном итоге стандартизирован.
Для Java сторонние библиотеки предоставляют функциональность мультинабора:
- Коллекции Apache CommonsBag предоставляют интерфейсы и SortedBagс реализацией таких классов, как HashBagи TreeBag.
- Google Guava предоставляет Multisetинтерфейс с реализацией таких классов, как HashMultisetи TreeMultiset.
Apple предоставляет NSCountedSetкласс как часть Cocoa , а типы CFBagи CFMutableBag— как часть CoreFoundation .
Стандартная библиотека Python включает collections.Counter, которая похожа на мультимножество.
Smalltalk включает Bagкласс, экземпляр которого можно создать для использования либо идентичности, либо равенства в качестве предиката для проверки включения.

Если структура данных с несколькими наборами недоступна, обходным путем является использование обычного набора, но переопределение предиката равенства его элементов, чтобы всегда возвращать «не равно» для отдельных объектов (однако они все равно не смогут хранить несколько вхождений один и тот же объект) или использовать ассоциативный массив , отображающий значения в их целочисленные кратности (это вообще не позволит различать равные элементы).

Типичные операции с мешками:

contains(B, x): проверяет, присутствует ли элемент x (хотя бы один раз) в сумке B
is_sub_bag(B₁, B₂): проверяет, встречается ли каждый элемент в пакете B _{1 в}B ₁ не чаще, чем в пакете B ₂ ; иногда обозначается как B ₁ ⊑ B ₂ .
count(B, x): возвращает количество раз, когда элемент x встречается в сумке B ; иногда обозначается как B # x .
scaled_by(B, n): учитывая натуральное число n , возвращает пакет, который содержит те же элементы, что и пакет B , за исключением того, что каждый элемент, который встречается m раз в B , встречается n * m раз в результирующем пакете; иногда обозначается как n ⊗ B .
union(B₁, B₂): возвращает пакет, содержащий только те значения, которые встречаются либо в пакете B ₁ , либо в пакете B ₂ , за исключением того, что количество раз, когда значение x встречается в полученном пакете, равно ( B ₁ # x) + ( B ₂ # Икс); иногда обозначается как B ₁ ⊎ B ₂ .

Мультимножества в SQL

В реляционных базах данных таблица может быть (математическим) набором или мультимножеством, в зависимости от наличия ограничений уникальности для некоторых столбцов (что превращает ее в потенциальный ключ ).

SQL позволяет выбирать строки из реляционной таблицы: эта операция, как правило, дает мультимножество, если только ключевое слово не DISTINCTиспользуется для того, чтобы все строки были разными, или если выборка не включает первичный (или потенциальный) ключ.

В ANSI SQL это MULTISETключевое слово можно использовать для преобразования подзапроса в выражение коллекции:

ВЫБРАТЬ выражение1 , выражение2 ... ИЗ имени_таблицы ...

— это общий выбор, который можно использовать как выражение подзапроса другого, более общего запроса, тогда как

MULTISET ( ВЫБРАТЬ выражение1 , выражение2 ... ИЗ имени_таблицы ...)

преобразует подзапрос в выражение коллекции , которое можно использовать в другом запросе или при назначении столбцу соответствующего типа коллекции.

Смотрите также

Примечания

^
Например, в Python pickможно реализовать производный встроенный класс setследующим образом:
```
класс  Set ( set ):  def  Pick ( self ):  return  next ( iter ( self ))
```
^ Вставка элемента может быть выполнена за время O (1), просто вставив его в конец, но если избегать дублирования, это займет время O ( n ).