Что такое система множеств
Что такое система множеств
Объединение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X или Y, т.е. принадлежат X или принадлежат Y.
Объединение X и Y обозначается через X∪Y
Формально x∈X∪Y ⇔ x∈X или x∈Y
Пример 3. Если X — множество точек левого круга и Y — множество точек правого круга, то
X∪Y — заштрихованная область, ограниченная обоими кругами.
представляет собой множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств данной системы М.
Для объединенных множеств справедливы:
справедливость которых вытекает из того, что левая и правая части равенств состоят из одних и тех же элементов.
Очевидно, что X∪∅ = X. Отсюда можно видеть, что ∅ играет роль нуля в алгебре множеств.
2. Пересечение множеств
Пересечение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y.
Пересечение множеств обозначается X∩Y.
Формально x∈X∩Y ⇔ x∈X и x∈Y
Пример 5. Если Х — множество точек левого круга, а Y — множество точек правого круга, то X∩Y представляет собой заштрихованную область, являющуюся общей частью обоих кругов.
Множества X и Y называются непересекающимися (дизъюнктными), если они не имеют общих элементов, то есть если X∩Y=∅.
Частный случай: кортеж длины 1 —
кортеж длины 0 — или ∧ — пустой кортеж.
Отличие кортежа и обыкновенного множества: в кортеже могут быть одинаковые элементы.
Упорядоченные множества, элементами которых являются вещественные числа, будем называть векторами или точками пространства (n-мерного).
Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны.
Компонентами кортежа (вектора) могут быть также компоненты кортежи (векторы):
Пример. Слова в предложении,
Прямое произведение множеств
Прямым (декартовым) произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая принадлежит множеству Y.
Пример 3. Пусть X и Y — отрезки вещественной оси. Прямое произведение X*Y изображается заштрихованным прямоугольником. См. рис. б).
Прямое произведение изменяется при изменении порядка сомножителей т.е.
Очевидно X*Y = ∅ ⇔ X = ∅ или Y = ∅.
Частным случаем прямого произведения является понятие степеней (декартовых) множества — прямое произведение одинаковых множеств
M s =M*M*. *M, M 1 =M, M 0 =∧.
Обычно R — множество вещественных чисел, тогда R 2 =R*R — вещественная плоскость и R 3 =R*R*R — трехмерное вещественное пространство.
Проекция множества.
Операция программирования множества тесно связана с операцией проектирования кортежа и может применяться лишь к таким множествам, элементами которых являются кортежи одинаковой длины.
Пусть M — множество, состоящее из кортежей длины S. Тогда пролинией множества M будем называть множество пролиний всех кортежей из М
Очевидно что если М=Х*Y то Пр1М=Х, Пр2М=Y
и если Q⊆Х*Y то Пр1Q⊆Х и Пр2Q⊆Y
Пусть V — множество векторов одинаковой длины S.
В общем случае ПрiV — вовсе не обязательно прямое произведение: оно может быть подмножеством.
Система непересекающихся множеств и её применения
Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.
Условие
Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.
Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:
На рисунке я продемонстрирую работу такой гипотетической структуры.
Реализация
Классическая реализация DSU была предложена Bernard Galler и Michael Fischer в 1964 году, однако исследована (включая временную оценку сложности) Робертом Тарьяном уже в 1975. Тарьяну же принадлежат некоторые результаты, улучшения и применения, о которых мы сегодня ещё поговорим.
Хранить структуру данных будем в виде леса, то есть превратим DSU в систему непересекающихся деревьев. Все элементы одного множества лежат в одном соответствующем дереве, представитель дерева — его корень, слияние множеств суть просто объединение двух деревьев в одно. Как мы увидим, такая идея вкупе с двумя небольшими эвристиками ведет к поразительно высокому быстродействию получившейся структуры.
Для начала нам потребуется массив p, хранящий для каждой вершины дерева её непосредственного предка (а для корня дерева X — его самого). С помощью одного только этого массива можно эффективно реализовать две первые операции DSU:
MakeSet(X)
Чтобы создать новое дерево из элемента X, достаточно указать, что он является корнем собственного дерева, и предка не имеет.
Find(X)
Представителем дерева будем считать его корень. Тогда для нахождения этого представителя достаточно подняться вверх по родительским ссылкам до тех пор, пока не наткнемся на корень.
Но это еще не все: такая наивная реализация в случае вырожденного (вытянутого в линию) дерева может работать за O(N), что недопустимо. Можно было бы попытаться ускорить поиск. Например, хранить не только непосредственного предка, а большие таблицы логарифмического подъема вверх, но это требует много памяти. Или хранить вместо ссылки на предка ссылку на собственно корень — однако тогда при слиянии деревьев (Unite) придется менять эти ссылки всем элементам одного из деревьев, а это опять-таки временные затраты порядка O(N).
Мы пойдем другим путём: вместо ускорения реализации будем просто пытаться не допускать чрезмерно длинных веток в дереве. Это первая эвристика DSU, она называется сжатие путей (path compression). Суть эвристики: после того, как представитель таки будет найден, мы для каждой вершины по пути от X к корню изменим предка на этого самого представителя. То есть фактически переподвесим все эти вершины вместо длинной ветви непосредственно к корню. Таким образом, реализация операции Find становится двухпроходной.
На рисунке показано дерево до и после выполнения операции Find(3). Красные ребра — те, по которым мы прошлись по пути к корню. Теперь они перенаправлены. Заметьте, как после этого кардинально уменьшилась высота дерева.
Исходный код в рекурсивной форме написать достаточно просто:
Unite(X, Y)
Со слиянием двух деревьев придется чуть повозиться. Найдем для начала корни обоих сливаемых деревьев с помощью уже написанной функции Find. Теперь, помня, что наша реализация хранит только ссылки на непосредственных родителей, для слияния деревьев достаточно было бы просто подвесить один из корней (а с ним и все дерево) сыном к другому. Таким образом все элементы этого дерева автоматически станут принадлежать другому — и процедура поиска представителя будет возвращать корень нового дерева.
Встает вопрос: какое дерево к какому подвешивать? Всегда выбирать какое-то одно, скажем, дерево X, не годится: легко подобрать пример, на котором после N объединений мы получим вырожденное дерево — одну ветку из N элементов. И тут в ход вступает вторая эвристика DSU, направленная на уменьшение высоты деревьев.
Будем хранить помимо предков еще один массив Rank. В нем для каждого дерева будет храниться верхняя граница его высоты — то есть длиннейшей ветви в нем. Заметьте, не сама высота — в процессе выполнения Find длиннейшая ветвь может самоуничтожиться, а тратить еще итерации на нахождение новой длиннейшей ветви слишком дорого. Поэтому для каждого корня в массиве Rank будет записано число, гарантированно больше или равное высоте его дерева.
Теперь легко принять решении о слиянии: чтобы не допустить слишком длинных ветвей в DSU, будем подвешивать более низкое дерево к более высокому. Если их высоты равны — не играет роли, кого подвешивать к кому. Но в последнем случае новоиспеченному корню надо не забыть увеличить Rank.
Вот так производится типичный Unite (например, с параметрами 8 и 19):
Однако на практике оказывается, что можно и не тратить дополнительные O(N) памяти на махинации с рангами. Достаточно выбирать корень для переподвешивания случайным образом — как ни удивительно, но такое решение дает на практике скорость, вполне сравнимую с оригинальной ранговой реализацией. Автор данной статьи всю жизнь пользуется именно рандомизированным DSU, и еще не было случая, когда тот бы подвёл.
Быстродействие
В силу применения двух эвристик скорость работы каждой операции сильно зависит от структуры дерева, а структура дерева — от списка выполненных до того операций. Исключение составляет только MakeSet — её время работы очевидно O(1) 🙂 Для остальных двух скорость очень неочевидна.
Итак, имеем:
MakeSet(X) — O(1).
Find(X) — O(1) амортизированно.
Unite(X, Y) — O(1) амортизированно.
Расход памяти — O(N).
Практические применения
Для DSU известно большое число различных использований. Большинство связано с решением некоторой задачи в режиме оффлайн — то есть когда список запросов касательно структуры, которые поступают программе, известен заранее. Я приведу здесь несколько таких задач вместе с краткими идеями решений.
Остов минимального веса
Дан неориентированный связный граф со взвешенными ребрами. Выкинуть из него некоторые ребра так, чтобы в итоге получилось дерево, причем суммарный вес ребер этого дерева должен быть наименьшим.
Одно из известных мест, где встает эта задача (хотя и решается иначе) — блокирование избыточных связей в Ethernet-сети для избегания возможных циклов пакетов. Протоколы, созданные с этой целью, широко известны, причем половина серьезных модификаций в них сделана Cisco. Более подробно см. Spanning Tree Protocol.
На рисунке показан взвешенный граф с выделенным минимальным остовом.
Алгоритм Краскала для решения этой задачи: отсортируем все ребра по возрастанию веса и будем поддерживать текущий лес минимального веса с помощью DSU. Изначально DSU состоит из N деревьев, по одной вершине в каждом. Идем по ребрам в порядке возврастания; если текущее ребро объединяет разные компоненты — сливаем их в одну и запоминаем ребро как элемент остова. Как только количество компонент достигнет единицы — мы построили искомое дерево.
Алгоритм Тарьяна для поиска LCA оффлайн
Дано дерево и набор запросов вида: для данных вершин u и v вернуть их ближайшего общего предка (least common ancestor, LCA). Весь набор запросов известен заранее, т.е. задача сформулирована в режиме оффлайн.
Компоненты связности в мультиграфе
Дан мультиграф (граф, в котором пара вершин может быть соединена более чем одним непосредственным ребром), к которому поступают запросы вида «удалить некоторое ребро» и «а сколько сейчас в графе компонент связности?» Весь список запросов известен заранее.
Решение банально. Выполним сначала все запросы на удаление, посчитаем количество компонент в итоговом графе, запомним его. Получившийся граф запихнем в DSU. Теперь будем идти по запросам удаления в обратном порядке: каждое удаление ребра из старого графа означает возможное слияние двух компонент в нашем «flashback-графе», хранящемся в DSU; в таком случае текущее количество компонент связности уменьшается на единичку.
Сегментирование изображений
Рассмотрим некоторое изображение — прямоугольный массив пикселей. Его можно представить как сетчатый граф: каждая вершина-пиксель непосредственно связана ребрами со своими четырьмя ближайшими соседями. Задача заключается в том, чтобы выделить на изображении одинаковые смысловые зоны, например, похожего цвета, и уметь для двух пикселей быстро определять, находятся ли они в одной зоне. Так, например, раскрашиваются старые черно-белые фильмы: для начала нужно выделить области с примерно одинаковыми оттенками серого.
Есть два подхода к решению этой проблемы, оба в конечном итоге используют DSU. В первом варианте мы проводим ребро не между каждой парой соседних пикселей, а только между теми, которые достаточно близки по цвету. После этого обычный прямоугольный обход графа заполнит DSU, и мы получим набор компонент связности — они же однотонные области изображения.
Второй вариант более гибкий. Не будем полностью убирать ребра, а присвоим каждому из них вес, рассчитанный на основании разности цветов и еще каких-то дополнительных факторов — своих для каждой конкретной задачи сегментирования. В полученном графе достаточно найти какой-нибудь лес минимального веса, например, тем же алгоритмом Краскала. На практике в DSU записывают не любое текущее соединяющее ребро, а только те, для которых на данный момент две компоненты не сильно отличаются по меркам другой специальной весовой функции.
Генерация лабиринтов
Задача: сгенерировать лабиринт с одним входом и одним выходом.
Алгоритм решения:
Начнем с состояния, когда установлены все стены, за исключением входа и выхода.
На каждом шаге алгоритма выберем случайную стену. Если ячейки, между которыми она стоит, еще никак не соединены (лежат в разных компонентах DSU), то уничтожаем её (сливаем компоненты).
Продолжаем процесс до некоторого состояния сходимости: например, когда вход и выход соединены; либо, когда осталась одна компонента.
Однопроходные алгоритмы
Существуют варианты реализации Find(X), которые требуют одного прохода до корня, а не двух, однако сохраняют ту же или почти ту же степень быстродействия. Они реализуют другие стратегии сокращения высоты дерева, в отличие от path compression.
Вариант №1: path splitting. По пути от вершины Х до корня перенаправить родительскую связь каждой вершины с её предка на предка предка (дедушку).
Вариант №2: path halving. Взять идею path splitting, однако перенаправлять связи не всех вершин по пути, а только тех, на которых делаем перенаправления — то есть «дедушек».
На рисунке взято все то же дерево, в нем выполняется запрос Find(3). По центру показан результат с применением path splitting, справа — path halving.
Функциональная реализация
У системы непересекающихся множеств есть один большой недостаток: она не поддерживает ни в какой форме операцию Undo, потому что реализована насквозь в императивном стиле. Гораздо удобнее была бы реализация DSU в функциональном стиле, когда каждая операция не изменяет структуру на месте, а возвращает слегка модифицированную новую структуру, в которой произведены требуемые изменения (при этом большая часть памяти у старой и новой структур общая). Такие структуры данных в английской терминологии носят название persistent, они широко применяются в чистом функциональном программировании, где доминирует идея неизменяемости данных.
В силу чисто императивной идеи алгоритмов DSU её функциональная реализация с сохранением быстродействия долгое время казалась немыслимой. Тем не менее, в 2007 году Sylvain Conchon и Jean-Christophe Filliâtre представили в своей работе искомый функциональный вариант, в котором операция Unite возвращает измененную структуру. Если говорить честно, он не совсем функциональный, он использует императивные присваивания, однако они надежно скрыты внутри реализации, а интерфейс persistent DSU — чисто функциональный.
Основная идея реализации — использование структур данных, реализующих «персистентные массивы»: они поддерживают те же операции, что и массивы, однако все так же не модифицируют память, а возвращают измененную структуру. Такой массив можно легко реализовать с помощью какого-нибудь дерева, однако в таком случае операции с ним будут занимать O(log2 N) времени, а для DSU такая оценка оказывается уже чрезмерно большой.
За дальнейшими техническими подробностями отсылаю читателей к оригинальной статье.
Литература
Системы непересекающихся множеств в объеме данной статьи обсуждаются в знаменитой книге — Кормен, Лейзерсон, Ривест, Штайн «Алгоритмы: построение и анализ». Там же можно найти и доказательство того, что выполнение операций занимает порядка α(N) времени.
На сайте Максима Иванова можно найти полную реализацию DSU на C++.
В статье Wait-free Parallel Algorithms for the Union-Find Problem обсуждается парралельная версия реализации DSU. В ней отсутствуют блокировки потоков.
Системы множеств
Элементы множества сами могут быть множествами.
Пример 1. Множество X = <1>,<2,3>, <1,2>состоит из
В этом случае будем говорить о системе множеств. Рассмотрим такие системы: булеан и разбиение множеств.
Булеаном В(Х) множества X называется множество всех его подмножеств. В булеан В(Х)обязательно включается само множество X и пустое множество Æ.
Пример 2. Для множества X = <0,1>булеаном является множество:
В(Х) = Æ, <0>,<1>, <0,1>.
Разбиением P(X) множества Х называется система его непустых непересекающихся подмножеств, в объединении дающая множество X (рис. 1.6).
4) 
Пример 3. Для множества X = <1,2,3,4,5>можно построить следующие разбиения:
Примерами разбиений также являются разбиения множества студентов университета по факультетам, по курсам и по группам.
Теория множеств: основы и базовые операции над множествами
Мы знаем довольно много о структурах данных, понимаем их устройство, разбираемся, какие структуры работают быстро и помогают решать конкретные задачи. Но эти знания бесполезны, если мы не понимаем, как это использовать в реальной жизни. Это похоже на изучение геометрии в школе. Вы долго считаете предмет бесполезным, пока однажды не появляется необходимость рассчитать площадь пола, чтобы заказать новое ковровое покрытие. Впрочем, пользу геометрии можно почувствовать, даже если вы никогда не считали площадь пола в комнате самостоятельно.
Сегодня поговорим о структуре данных, которая в теории очень догматична, а на практике очень популярна. На самом деле вы так или иначе уже сталкивались с этой структурой, а также слышали о ней на уроках математики в школе. Вы уже догадались, что речь идёт о множествах.
Теория множеств без страха
Прежде чем разбирать устройство множеств, давайте поймём, откуда они появляются. То есть давайте сразу погрузимся в теорию — да-да, в теорию множеств! Не бойтесь сложностей — высока вероятность того, что вы уже так или иначе использовали эту теорию. Возможно, вы сталкивались с теорией множеств, когда проходили в школе диаграмму Венна. Диаграмму Венна включили в программу изучения множеств, так как она хорошо иллюстрирует отношения подмножеств.
Мы выяснили, что теория множеств не должна никого пугать. Теперь пришло время разобраться, что это за теория на самом деле. Множество — математическая концепция. Теорией множеств описывают отношения множеств.
Множество — ни что иное, как неупорядоченная коллекция, в которой нет дублирующихся элементов.
В этом определении есть три важных слова: «неупорядоченная», «дублирующихся» и «элементов». Эти слова точно передают суть и устройство множества. Если мы это запомним, то будем знать основную информацию о том, как работает эта структура данных.
Нужно понять, почему это важно. Для начала давайте посмотрим на множества в действии. Как сказано выше, отношения множеств удачно иллюстрирует диаграмма Венна. Давайте взглянем на два множества: книги, которые есть у человека дома, и книги, которые этот человек прочитал.
Если вы знакомы с диаграммой Венна, то понимаете, что в центре в зелёном круге находятся книги, которыми человек владеет, и которые он прочитал. Здесь множества пересекаются. Также вы понимаете, что два множества — прочитанные человеком книги и книги, которые есть у человека — существуют внутри другого множества. Это все существующие в мире книги.
Диаграмма Венна — хорошая база для понимания теории множеств, так как с её помощью легче понять более сложные вещи. Допустим, вы хотите представить два множества книг в какой-то структуре данных. Вы уже знаете, что книги надо разделить на два множества: которые человек прочитал и которые есть у него дома. Для удобства назовём первое множество Set X, а второе Set Y. Эти множества после реконфигурации в структуры данных можно представить с помощью диаграммы Венна.
Можно заметить, что множества Set X и Set Y стали похожи на объекты или хэши: элементы внутри них не имеют индексов или других элементов, позволяющих их упорядочить. В них также нет повторяющихся элементов, что делает эти структуры данных множествами. Как вы уже знаете, множество — это коллекция неупорядоченных элементов, которые не повторяются.
Начните изучать разработку с бесплатного курса «Основы современной вёрстки». Вы научитесь создавать статические веб-страницы, стилизовать элементы, использовать редакторы кода с полезными расширениями. В конце курса вы опубликуете свой первый сайт на GitHub Pages.
Об операциях с множествами без боли
Какие возможности открывает представление множеств в формате структур данных? С ними теперь можно выполнять разные операции. Две самые важные операции, которые выполняются над множествами — это пересечение и объединение.
Пересечение множеств часто записывается с помощью такой нотации: X ∩ Y. Пересечение определяет, где два множества пересекаются. Другими словами, эта операция возвращает все элементы, которые входят в два множества. В нашем примере пересечение Set X и Set Y возвращает все книги, которые человек читал и которые есть у него дома. Хороший ключ к пониманию пересечения — ключевое слово «и». Мы получаем книги, которые человек читал и которые есть у него дома. Несмотря на то, что полученные с помощью пересечения книги существуют в двух множествах, мы не повторяем их, так как в множестве могут быть только уникальные элементы.
Объединение двух множеств обозначается так: X ∪ Y. Объединение возвращает общность двух множеств или объединённое множество. Иными словами, с помощью объединения множеств можно получить новое множество элементов, которые существуют хотя бы в одном исходном множестве. В нашем случае объединение вернёт все книги, которые человек читал, а также все книги, которые есть у него дома. Обратите внимание, если книга входит одновременно в Set X и Set Y, она не может дублироваться в новом множестве после объединения, так как в множества входят только уникальные элементы.
С помощью диаграммы Венна пересечение и объединение можно представить так:
Теперь давайте рассмотрим более сложные вещи. Объединение и пересечение — важные операции над множествами, но это только азы теории. Нам надо познакомиться с другими операциями, чтобы решать более серьёзные задачи. Важно понимать разность множеств и относительные дополнения множеств. Ниже мы разберём, почему это важные операции, но сначала нужно понять, как они работают.
Как понятно из названия, разность множеств определяет разницу между множествами. Иными словами, мы определяем, какие элементы останутся в множестве X, если удалить из него все элементы, которые содержатся в множестве Y. Это действие можно обозначить так: X — Y. В примере на иллюстрации ниже разница между множеством X и множеством Y — это элементы, которые существуют в Set X, но не существуют в Set Y. Они обозначены буквами C, Z и W.
Относительное дополнение — противоположность разности множеств. Например, относительное дополнение Y по сравнению с X возвращает все элементы множества Y, которые не входят в множество X. Относительное дополнение можно обозначить так: X \ Y. Относительное дополнение X \ Y фактически возвращает такой же набор элементов, как разность Y — X. В нашем примере множество Y меньше множества X. Единственный элемент, который входит в Set Y, но не входит в Set X — число 2.
По сути, мы просто вычитаем множество X из множества Y и отвечаем на вопрос: что существует в Y, чего нет в X?
Вы могли заметить, что в части примеров мы имеем дело со строками, в другой части в качестве элементов выступают буквы и числа. Здесь надо подчеркнуть важный момент: множество может включать любой тип элементов или объектов. Вы можете рассматривать множества как хэши: они включают любые сущности, если те встречаются во множестве только один раз.
Теперь давайте рассмотрим ещё одну операцию, она самая сложная из всех. Но не пугайтесь, с ней тоже можно разобраться.
В некоторых случаях требуется найти противоположность пересечению множеств. Иными словами, речь идёт о книгах, которые есть у человека, и книгах, которые он прочитал, но которые не входят одновременно в оба множества. Как назвать это подмножество? И как найти его?
Правильное название для этого кейса — симметрическая разность множеств. Также употребляют термины «дизъюнктивное объединение» и «несвязное объединение». Симметрическая разность возвращает все элементы, которые входят в одно из множеств, но не входят в пересечение этих множеств. Пример на иллюстрации поможет разобраться с дизъюнктивным объединением.
В примере выше симметрическая разность похожа на поиск относительного дополнения множества X и множества Y. Если подходить к этому с позиции математики, поиск симметричной разницы — то же самое, что и объединение относительных дополнений множества X и множества Y. Эту операцию можно записать так: X △ Y= (X ∖ Y) ∪ (Y ∖ X).
Но не дайте сбить себя с толку!
Всё, что нужно для поиска симметрической разности — найти элементы, которые есть в множестве X, но отсутствуют в множестве Y, и какие элементы есть в множестве Y, но отсутствуют в множестве X. Иными словами, надо найти уникальные элементы в каждом множестве.
В примере выше числа 1, 2 и 3 входят в множества X и Y одновременно. А буквы A, B, C, X, Y, Z входят только в множества X или Y. Поэтому они представляют симметрическую разность множеств X и Y.
Мы рассмотрели теоретические вопросы. Теперь можно посмотреть, как теория множеств работает на практике.
Множества вокруг нас
К этому моменту вы наверняка задумались, зачем надо изучать теорию множеств. Это хороший вопрос, и пришло время ответить на него.
Уже догадались? Множества повсюду. Это структуры данных, которые мы можем использовать при работе с разными языками программирования, например, Python, Java, Ruby, JavaScript и так далее. Если вы знакомы с этими или другими языками программирования, то уже вспомнили методы, которые позволяют работать с множествами.
Вот пример на JavaScript.
Очевидно, что имена методов могут меняться в зависимости от языка. Например, метод has из примера выше в Ruby называется include?, но эти методы работают практически одинаково. А в Python при работе с множествами можно использовать методы intersection, union и symmetric_difference.
Но в чём именно польза множеств? Понятно, что с ними можно работать в разных языках программирования, но зачем это нужно на практике?
Один из моментов — множества могут сэкономить вам много времени. Помните все эти сложные операции — intersection, union, difference? Уже догадались? Продолжительность выполнения этих операций зависит от размера множеств. Это связано с тем, что для выполнения операций нам надо обойти все элементы множества. Обычно даже гигантские множества можно обойти достаточно быстро.
Но как насчёт основных операций? Как насчёт добавления элементов в одно из множеств, удаления элементов, поиска конкретного элемента в множестве? Все эти операции выполняются за константное время или 0(1). Это очень мощный инструмент, и это значит, что множества могут быть даже более удобной структурой данных, чем словарь или хэш.
Но подождите, почему все операции с множествами выполняются так быстро? Как это возможно? Как оказалось, под капотом множества представляют собой хэши. Теперь вся информация собирается воедино. С хэш-таблицами знакомо большинство программистов, но почему с их помощью так удобно реализовывать множества?
Это возможно благодаря нескольким факторам. Первый: в хэш-таблицах каждый элемент всегда имеет уникальный индекс. Это очень хорошо с точки зрения реализации множеств, так как множества могут включать только уникальные элементы. Второй фактор: в хэш-таблицах порядок элементов не имеет значения. В множествах порядок элементов тоже не имеет значения. Наконец, хэш-таблицы обеспечивют константное время доступа 0(1). Это идеально для выполнения базовых операций с множествами.
Заключение
Теория множеств используется в разных областях computer science. Это важная для программистов концепция, понимание которой помогает разработчикам эффективно работать с данными.
Адаптированный перевод статьи Set Theory: the Method To Database Madness by Vaidehi Joshi.
Никогда не останавливайтесь: В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях.
С нуля до разработчика. Возвращаем деньги, если не удалось найти работу.