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

Абстрактный тип данных для хранения уникальных значений

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

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

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

Теория типов

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

${\displaystyle 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(x1,x2,…,xn,): создает структуру набора со значениями 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. ^[a]
• map(F,S): возвращает набор различных значений, полученных в результате применения функции F к каждому элементу S.
• filter(P,S): возвращает подмножество, содержащее все элементы S , удовлетворяющие заданному предикату P.
• fold(A0,F,S): возвращает значение A _{| S |} после применения к каждому элементу e из S некоторой бинарной операции F. Для того чтобы это было корректно определено, F должна быть ассоциативной и коммутативной.Ai+1 := F(Ai, e)
• clear(S): удалить все элементы S .
• equal(S1', S2'): проверяет, равны ли два заданных набора (т.е. содержат ли они все и только одни и те же элементы).
• hash(S): возвращает хеш-значение для статического набора S, такое что если тоequal(S1, S2)hash(S1) = hash(S2)

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

• 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-find ), которые оптимизированы для одной или нескольких из этих операций за счет других.union(S,T)

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

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

• В 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, а начиная с версий 3.0 и 2.7 поддерживаются непустые литералы множеств с использованием синтаксиса фигурных скобок, например: {x, y, z}; пустые множества должны создаваться с помощью set(), поскольку Python использует {}для представления пустого словаря.
• .NET Framework предоставляет универсальные интерфейсы HashSetи SortedSetклассы, реализующие универсальный ISetинтерфейс.
• Библиотека классов SmalltalkSet включает и IdentitySet, используя для проверки на включение равенство и идентичность соответственно. Многие диалекты предоставляют вариации для сжатого хранения ( NumberSet, CharacterSet), для упорядочивания ( OrderedSet, SortedSet, и т.д.) или для слабых ссылок ( WeakIdentitySet).
• Стандартная библиотека Rubyset включает модуль, содержащий Setклассы SortedSet, реализующие множества с использованием хэш-таблиц, причем последние допускают итерацию в отсортированном порядке.
• Стандартная библиотека OCaml содержит модульSet , который реализует функциональную структуру данных с использованием двоичных деревьев поиска.
• Реализация GHC в Haskell предоставляет Data.Setмодуль, который реализует неизменяемые множества с использованием бинарных деревьев поиска. ^[9]
• Пакет Tcl Tcllib предоставляет модуль набора, который реализует структуру данных набора на основе списков TCL.
• Стандартная библиотека Swift содержит Setтип, начиная с версии Swift 1.2.
• JavaScript представлен Setкак стандартный встроенный объект в стандарте ECMAScript 2015 ^[10] .
• В стандартной библиотеке Erlangsets есть модуль.
• Clojure имеет буквенный синтаксис для хешированных наборов, а также реализует отсортированные наборы.
• LabVIEW имеет встроенную поддержку множеств, начиная с версии 2019.
• Ada предоставляет пакеты Ada.Containers.Hashed_Setsи Ada.Containers.Ordered_Sets.

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

Мультисет

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

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

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

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

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

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

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

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

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

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

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

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

SELECT выражение1 , выражение2 ... FROM table_name ...    

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

MULTISET ( SELECT выражение1 , выражение2 ... FROM table_name ...)    

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

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

• Фильтр Блума
• Непересекающееся множество
• Множество (математика)

Примечания

1. Например, в Python pickможно реализовать на основе производного класса встроенный метод setследующим образом:

   класс  Set ( set ):  def  pick ( self ):  return  next ( iter ( self ))

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

Ссылки

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