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

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

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

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

Теория типов

В теории типов множества обычно отождествляются с их индикаторной функцией (характеристической функцией): соответственно, множество значений типа $A$ может быть обозначено $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) или cardinality(S) возвращает количество элементов в 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): возвращает набор различных значений, полученных в результате применения функции к каждому элементу S. F
filter(P,S): возвращает подмножество, содержащее все элементы , удовлетворяющие заданному предикату P. S
fold(A₀,F,S): возвращает значение A _{| С |} после подачи заявки A_i+1 := F(A_i, e) для каждого элемента 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): учитывая набор множеств, вернуть объединение. ^[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), max(S): возвращает минимальный/максимальный S. элемент

Реализации

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

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

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

my %elements = map { $_ => 1 } @elements;

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

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

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

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

В C++ стандартная библиотека шаблонов (STL) предоставляет set класс шаблона, который обычно реализуется с использованием двоичного дерева поиска (например, красно-черное дерево ); SGI также предоставляет STL от hash_set класс шаблона, который реализует набор с использованием хеш-таблицы. C++11 поддерживает unordered_set класс шаблона, который реализован с использованием хеш-таблицы. В наборах ключами являются сами элементы, в отличие от упорядоченных контейнеров, где доступ к элементам осуществляется с использованием их (относительной или абсолютной) позиции. Элементы множества должны иметь строгий слабый порядок.
Стандартная библиотека Rust предоставляет общий HashSet и BTreeSet типы.
Java предлагает Set интерфейс для поддержки наборов (с HashSet класс, реализующий его с использованием хеш-таблицы), а SortedSet субинтерфейс для поддержки отсортированных наборов (с TreeSet класс, реализующий его с использованием двоичного дерева поиска).
Apple Foundation Платформа (часть Cocoa ) предоставляет Objective-C. классы NSSet, NSMutableSet, NSCountedSet, NSOrderedSet, и NSMutableOrderedSet. API CoreFoundation предоставляют типы CFSet и CFMutableSet в C. для использования
В Python есть встроенный set и frozenset типы начиная с 2.4, а также с Python 3.0 и 2.7 поддерживают непустые литералы множества с использованием синтаксиса фигурных скобок, например: {x, y, z}; пустые наборы должны создаваться с использованием set(), потому что Python использует {} для представления пустого словаря.
предоставляет .NET Framework универсальный HashSet и SortedSet классы, реализующие общий ISet интерфейс.
Smalltalk включает в себя Библиотека классов Set и IdentitySet, используя равенство и идентичность для проверки включения соответственно. Многие диалекты предоставляют варианты сжатого хранения ( NumberSet, CharacterSet), для заказа ( OrderedSet, SortedSetи т.д.) или для слабых ссылок ( WeakIdentitySet).
Ruby включает в себя Стандартная библиотека set модуль, который содержит Set и SortedSet классы, реализующие наборы с использованием хеш-таблиц, причем последняя позволяет выполнять итерацию в отсортированном порядке.
содержит Стандартная библиотека OCaml Set модуль, который реализует структуру данных функционального набора с использованием двоичных деревьев поиска.
GHC Реализация Haskell обеспечивает Data.Set модуль, который реализует неизменяемые множества с использованием двоичных деревьев поиска. ^[9]
Пакет Tcl Tcllib предоставляет модуль set, который реализует структуру данных set на основе списков TCL.
Стандартная библиотека Swift содержит Set типа, начиная с Swift 1.2.
JavaScript Представлен Set как стандартный встроенный объект с ECMAScript 2015 ^[10] стандарт.
Стандартная библиотека Erlang имеет sets модуль.
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 Commons предоставляют Коллекции Bag и SortedBag интерфейсы с реализацией таких классов, как HashBag и TreeBag.
- Google Гуава предоставляет Multiset интерфейс с реализацией таких классов, как HashMultiset и TreeMultiset.
Apple предоставляет NSCountedSet class как часть Cocoa , а CFBag и CFMutableBag типы как часть CoreFoundation .
Python включает в себя Стандартная библиотека collections.Counter, что похоже на мультимножество.
Smalltalk включает в себя Bag класс, экземпляр которого можно создать для использования идентичности или равенства в качестве предиката для проверки включения.

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

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

contains(B, x): проверяет, присутствует ли элемент x (хотя бы один раз) в сумке B
is_sub_bag(B₁, B₂): проверяет, встречается ли каждый элемент в пакете B ₁ в 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 используется для того, чтобы все строки были разными, или выборка включает первичный (или возможный) ключ.

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

SELECT expression1, expression2... FROM table_name...

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

MULTISET(SELECT expression1, expression2... FROM table_name...)

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

См. также

Примечания

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

Ссылки

^ Питон: поп()
^ Управление и обработка сложных структур данных: Третий семинар по информационным системам и искусственному интеллекту, Гамбург, Германия, 28 февраля - 2 марта 1994 г. Труды, под ред. Кай против Удачи, Хайнц Марбургер, с. 76
^ Python Issue7212 : получить произвольный элемент из набора, не удаляя его; см . msg106593 относительно стандартного имени.
^ Ruby Функция № 4553 : добавление Set#pick и Set#pop
^ Индуктивный синтез функциональных программ: универсальное планирование, свертывание конечных программ и абстракция схемы посредством аналогичных рассуждений, Уте Шмид , Спрингер, 21 августа 2003 г., стр. 240
^ Последние тенденции в спецификации типов данных: 10-й семинар по спецификации абстрактных типов данных, совместный с 5-м семинаром COMPASS, С. Маргерита, Италия, 30 мая - 3 июня 1994 г. Избранные статьи, том 10, изд. Эджидио Астезиано, Джанна Реджио, Анджей Тарлецкий, с. 38
^ Руби: сгладить()
^ Ван, Томас (1997), Сортированная линейная хеш-таблица , заархивировано из оригинала 12 января 2006 г.
^ Стивен Адамс, « Эффективные наборы: балансирование » , Журнал функционального программирования 3 (4): 553-562, октябрь 1993 г. Проверено 11 марта 2015 г.
^ «Спецификация языка ECMAScript 2015 – ECMA-262, 6-е издание» . www.ecma-international.org . Проверено 11 июля 2017 г.

[6] Например, в Python pick может быть реализован в производном классе встроенного set следующее:
class Set(set): def pick(self): return next(iter(self))

[9] Вставка элемента может быть выполнена за время O (1), просто вставив его в конец, но если избегать дублирования, это займет O ( n ). время

[1] Питон: поп()

[2] Управление и обработка сложных структур данных: Третий семинар по информационным системам и искусственному интеллекту, Гамбург, Германия, 28 февраля - 2 марта 1994 г. Труды, под ред. Кай против Удачи, Хайнц Марбургер, с. 76

[3] Python Issue7212 : получить произвольный элемент из набора, не удаляя его; см . msg106593 относительно стандартного имени.

[4] Ruby Функция № 4553 : добавление Set#pick и Set#pop

[5] Индуктивный синтез функциональных программ: универсальное планирование, свертывание конечных программ и абстракция схемы посредством аналогичных рассуждений, Уте Шмид , Спрингер, 21 августа 2003 г., стр. 240

[7] Последние тенденции в спецификации типов данных: 10-й семинар по спецификации абстрактных типов данных, совместный с 5-м семинаром COMPASS, С. Маргерита, Италия, 30 мая - 3 июня 1994 г. Избранные статьи, том 10, изд. Эджидио Астезиано, Джанна Реджио, Анджей Тарлецкий, с. 38

[8] Руби: сгладить()

[10] Ван, Томас (1997), Сортированная линейная хеш-таблица , заархивировано из оригинала 12 января 2006 г.

[11] Стивен Адамс, « Эффективные наборы: балансирование » , Журнал функционального программирования 3 (4): 553-562, октябрь 1993 г. Проверено 11 марта 2015 г.

[12] «Спецификация языка ECMAScript 2015 – ECMA-262, 6-е издание» . www.ecma-international.org . Проверено 11 июля 2017 г.

[1]

[2]

[3]

[4]

[5]

[а]

[6]

[7]

[б]

[8]

[9]

[10]

v т и Типы данных
Uninterpreted	Bit Byte Trit Tryte Word Bit array
Numeric	Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Reduced precision Minifloat Half precision bfloat16 Single precision Double precision Quadruple precision Octuple precision Extended precision Long double Integer signedness Interval Rational
Pointer	Address physical virtual Reference
Text	Character String null-terminated
Composite	Algebraic data type generalized Array Associative array Class Dependent Equality Inductive Intersection List Object metaobject Option type Product Record or Struct Refinement Set Union tagged
Other	Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Strongly typed identifier Top type Type class Empty type Unit type Void
Related topics	Abstract data type Boxing Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Interface Subtyping Type constructor Type conversion Type system Type theory Variable

v т и Структуры данных
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures