Теперь, когда мы, наконец, прошли треть пути по этой серии, вещи, наконец, начинают складываться. Конечно, мы знаем о довольно большом количестве различных структур данных, о том, как они работают, какие из них быстрые и насколько одни из них более полезны для решения конкретных проблем, чем другие.
Но почти нет смысла знать об этом, если мы не понимаем, как они на самом деле используются в реальной жизни. Это похоже на изучение геометрии: все это, вероятно, казалось бессмысленным, пока однажды вы не проснулись и не поняли, что вам на самом деле придется рассчитать квадратные метры комнаты, потому что вы хотите заново покрыть пол ковром! (Хорошо, на самом деле мне никогда не приходилось этого делать, но я могу представить, что геометрия как концепция в целом была бы очень полезной, если бы мне когда-либо пришлось.)
Сегодня многие вещи соберутся вместе, потому что мы собираемся узнать о структуре данных, которая почти догматична по своей теории, но невероятно повсеместна на практике. Фактически, вы, вероятно, уже работали с этой структурой в той или иной форме и, вероятно, познакомились с ней на уроках математики в средней школе.
Итак, о какой структуре данных я говорю? Конечно же, я имею в виду всесильный набор!
Теория без страха
Прежде чем мы перейдем к реальной реализации наборов, нам сначала нужно понять, откуда они берутся. Это означает, что пора нам погрузиться в теорию - теорию множеств! Но не бойтесь: велика вероятность, что вы в той или иной мере использовали теорию множеств. На самом деле, вы, вероятно, знаете теорию множеств под другим названием: диаграмма Венна. Диаграмма Венна была фактически включена в «учебную программу по теории множеств» в 1960-х годах, потому что это был очень эффективный способ иллюстрации простых отношений между множествами.
Хорошо, теперь, когда мы уверены, что теория множеств не так уж и страшна, нам лучше выяснить, что это такое! Набор на самом деле является математическим понятием, и способ, которым мы связываем наборы друг с другом, называется теорией множеств.
set - это не что иное, как неупорядоченный набор элементов без абсолютно никаких дубликатов.
Это определение состоит из трех важных частей: неупорядоченные, элементы и без дубликатов. . Фактически, эти три слова охватывают почти все определение множества; если мы сможем это запомнить, мы будем знать все о том, как работают наборы.
Но мы еще вернемся к тому, почему это важно. Сначала давайте посмотрим на некоторые наборы в действии. Мы знаем, что наборы хорошо представлены диаграммами Венна, поэтому для нашего примера мы рассмотрим два набора: набор из некоторых книг, которые я прочитал, и набор из некоторых книг, которые у меня есть.
Поскольку мы знакомы с концепцией диаграмм Венна, мы знаем, что центральная секция зеленого цвета (где два набора пересекаются) представляет книги, которые я прочитал , и книги, которые принадлежат мне. Мы также знаем, что два набора, изображенные выше, существуют в большей группе всех книг в мире!
Диаграмма Венна - хорошее введение в теорию множеств, поскольку она значительно упрощает объяснение следующей части. Представьте, что мы хотим представить эти два набора данных в какой-то структуре. Что ж, мы уже знаем, что нам нужно разделить их на две группы: книги, которые я прочитал, и книги, которые у меня есть. Чтобы упростить задачу, мы назовем книги, которые я прочитал, как установить X, а книги, которые у меня есть, как набор Д. Перенастроенные в структуры данных, эти два набора на диаграмме Венна также можно переписать, чтобы они выглядели так:
Мы заметим, что и установка X, и установка Y немного похожи на объекты или хэши: элементы не имеют индексов или какого-либо порядка. У них также нет повторяющихся значений, что является частью того, что делает их набором. Помните, что набор - это набор уникальных неупорядоченных объектов, а это означает, что мы никогда не найдем повторяющиеся значения в наборе.
Безболезненные (сетевые) операции
Итак, что мы можем сделать с этими наборами теперь, когда они записаны в формате структуры данных? Что ж, мы можем проделать с ними какие-то операции! Двумя наиболее важными операциями, выполняемыми над наборами, являются пересечения и объединения.
Пересечение двух множеств часто обозначается сокращенно следующим образом: X ∩ Y. Пересечение представляет собой место, где два набора - как вы уже догадались - пересекаются! Другими словами, он возвращает все элементы, которые существуют в обоих наборах. В нашем примере пересечение множества X и множества Y - это все элементы, которые существуют в них обоих. Хорошее ключевое слово для запоминания того, как работают пересечения, - это слово и: элементы, которые существуют как в X, так и в Y. В этом случае это будет означать «Код завершен» и «Молоко и мед». Несмотря на то, что они существуют в обоих наборах, поскольку наборы могут содержать только уникальные значения, мы не повторяем их; каждое из этих названий книг существует в наборе только один раз.
Объединение двух наборов часто обозначается сокращенно следующим образом: X ∪ Y. Объединение представляет собой два набора целиком или два набора, когда они были объединены вместе. Другими словами, он возвращает все элементы, которые существуют в любом из двух наборов. Хорошее ключевое слово для запоминания того, как работают пересечения, - это слово или: элементы, которые существуют как в X, так и в Y. В этом случае это будет означать все восемь названий книг! Важно помнить, что хотя «Код завершен» и «Молоко и мед» существуют в обоих наборах, они могут появляться только один раз в объединении набора X и набора Y, поскольку наборы могут иметь только разные значения и никогда не могут содержат дубликаты.
Если бы мы применили пересечения и объединения к нашей диаграмме Венна ранее, наши диаграммы выглядели бы так:
Хорошо, пора еще немного усложнить ситуацию! Пересечения и объединения - это здорово, но они только касаются поверхности теории множеств. Для наших целей нам также потребуется ознакомиться с некоторыми другими операциями. Как оказалось, есть две операции, которые довольно часто используются в информатике: установить различия и относительные дополнения. В следующем разделе мы узнаем, какую роль они играют, но сначала давайте разберемся, как они работают!
Различия между наборами - это то, как мы можем определить разницу между двумя наборами. Другими словами, мы можем определить, как выглядит набор без каких-либо элементов, содержащихся в наборе other. Другой способ записать это - X - Y. В показанном здесь примере разница между набором X и набором Y приводит к появлению всех элементов, которые существуют в наборе X, но не существуют в наборе Y, или букв C, Z, и W.
Относительные дополнения в основном противоположны установленным различиям. Например, относительное дополнение Y по сравнению с X вернет все элементы в наборе Y, которые не появляются в наборе X. Мы можем обозначить относительное дополнение, используя сокращенное обозначение Y ∖ X , что фактически приводит к тому же возвращаемому набору, что и Y— X. В нашем примере набор Y меньше, чем набор X. В нашем примере единственное, что существует в Y, но не существует в X, - это число 2.
Фактически, мы просто вычитаем набор X из набора Y и отвечаем на вопрос: что существует в Y, чего нет в X?
Вы могли заметить, что в некоторых примерах мы имеем дело со строками, а в других элементы представляют собой буквы, а иногда даже числа. Это поднимает важный момент: наборы могут содержать буквально любые элементы или объекты! Вы можете думать о них как о хэшах: они могут содержать любой элемент, если он встречается только один раз в наборе.
Хорошо, давайте посмотрим на одну последнюю операцию - самую сложную из всех. Но мы справимся!
Иногда, когда у нас есть два набора, мы можем захотеть найти противоположность пересечения двух наборов. Другими словами, я мог бы захотеть найти все книги, которые у меня есть, и все книги, которые я прочитал, но ни одной, которые пересекаются между ними. Как бы мы назвали это подмножество? И как мы его найдем?
Что ж, подходящим термином для того, что мы ищем в данном случае, является то, что называется симметричной разницей наших двух множеств, которую также иногда называют дизъюнктивным объединением. . Симметричная разность дает все элементы, которые существуют в любом из двух наборов, но не существуют на их пересечении (X ∩ Y).
Давайте посмотрим на пример, который поможет прояснить, что я имею в виду:
В приведенном выше примере симметричная разность в основном такая же, как нахождение относительного дополнения множества X и множества Y. Если мы сверхматематически относимся к этому, нахождение симметричной разности аналогично нахождению объединения относительных дополнений множества X и множества Y. установить Y. Мы могли бы записать это как: X △ Y = (X ∖ Y) ∪ (Y ∖ X).
Но пусть это вас не смущает!
Все, что нам действительно нужно сделать, чтобы найти симметричное различие двух наборов, это спросить себя: какие элементы существуют в наборе X, но не существуют в наборе Y, и какие элементы существуют в Y, но не существуют в X? Другими словами: какие элементы уникальны для каждого набора и не встречаются в обоих из них?
В приведенном выше примере числа 1, 2, и 3 встречаются в обоих наборах. Однако буквы A, B, C и X, Y, Z встречаются только внутри набора X или набора Y и, следовательно, представляют собой симметричную разницу между двумя наборами.
Хорошо, это было много теоретической информации. Давайте посмотрим, как эта теория реализуется на практике, ладно?
Устанавливает все вокруг нас
Надеюсь, вы уже задаетесь вопросом, в чем смысл обучающих наборов. Я вас не виню: хороший вопрос! И наконец пора на него ответить.
Угадай, что? Наборы есть везде. Это настоящие структуры данных, которые мы можем использовать, когда захотим, в Java, Python, Ruby и даже JavaScript! Возможно, вы даже сможете догадаться о некоторых методах, которые каждый из этих языков позволяет нам применять на множествах.
Давайте быстро рассмотрим на примере JavaScript:
Очевидно, некоторые имена методов будут меняться от языка к языку. Например, реализация has в Ruby называется include?, но идея довольно схожа для разных языков. Версия наборов Python на самом деле позволяет вам вызывать методы, такие как intersection, union и symmetric_difference!
Но что вообще хорошего в наборах? Я имею в виду, что мы можем использовать их на всех этих языках, но когда они пригодятся?
Ну, во-первых, они могут быть довольно эффективными по времени.
Помните все эти сложные операции, такие как intersection, union и difference? Ну, угадайте, что? Время, необходимое нам для выполнения любой из этих сложных операций, зависит исключительно от длины двух наборов. Это связано с тем, что для того, чтобы найти пересечение, объединение или различие / дополнение этих двух наборов, мы должны эффективно пройти через всю длину двух сравниваемых наборов. Обычно даже гигантские множества не занимают столько времени, чтобы пройти.
Но как насчет основных операций? Как насчет добавления элемента в один из этих наборов, его удаления или даже поиска элемента внутри него? Что ж, все эти операции занимают постоянное время или O (1). Это может быть невероятно мощным и часто означает, что набор может быть лучшей структурой, чем словарь или хеш!
Но подождите секунду: как это возможно, что все эти операции с наборами выполняются так быстро ?! Как такое вообще случилось? Что ж, как оказалось, многие наборы фактически реализованы хеш-таблицами под капотом! (Видите ли, я обещал вам, что все соберется вместе!) Мы уже знаем о хэш-таблицах, но почему они делают хорошие скелеты для реализаций множеств?
На то есть несколько веских причин: во-первых, учитывая то, что мы знаем о хэш-таблицах, у них всегда будут уникальные ключи для каждого элемента. Это отлично подходит для наборов, поскольку наборы могут иметь только уникальные значения. Во-вторых, в хеш-таблицах порядок не имеет значения, так же как порядок не имеет значения в наборе. Наконец, хеш-таблицы обеспечивают постоянное время доступа O (1), что идеально для базовых операций, выполняемых с набором.
Хорошо, поэтому хеш-таблицы - хорошие наборы. А наборы - это структуры данных, которые большинство языков предоставляет нам бесплатно. Но когда я начал эту публикацию, я сказал вам, что наборы были везде, верно? Я чувствую, что, вероятно, должен открыть вам небольшой секрет, который (надеюсь) поразит вас:
Реляционные базы данных почти полностью основаны на теории множеств.
Фактически, если вы когда-либо работали с базой данных или запрашивали ее, или вам приходилось писать SQL, вы, вероятно, знакомы с идеей поиска записей на пересечении таблицы.
Это не более чем абстракция набора наборов с диаграммой Венна, с которой мы начали этот пост! Фактически, даже самые сложные операторы SQL - это не что иное, как операции над множествами.
SQL INNER JOIN - это просто пересечение двух наборов.
Нахождение LEFT JOIN двух таблиц - это не что иное, как поиск разницы наборов или относительного дополнения двух таблиц.
SQL-запрос, который вызывает FULL OUTER JOIN, просто возвращает объединение двух наборов.
И этот сверхсложный FULL OUTER JOIN, где один ключ в обеих таблицах равен NULL? (Также известный как проклятие моего существования, когда дело доходит до написания операторов SQL?) Это просто симметричное различие или дизъюнктивное объединение двух таблиц.
Как это удивительно ?! Вся эта кажущаяся скучной теория множеств, когда применяется на практике, делает базы данных самыми крутыми вещами на свете. И это, друг мой, уже само по себе подвиг!
Ресурсы
Теория множеств довольно широко распространена в различных областях информатики, от ее использования в реляционных базах данных до структур данных, существующих на различных языках, включая Python, Ruby, JavaScript и Java. Существует множество хороших ресурсов, которые помогут вам лучше понять теорию множеств; вот несколько, с которых можно начать!
- ЛЕВОЕ СОЕДИНЕНИЕ против ЛЕВОГО ВНЕШНЕГО СОЕДИНЕНИЯ в SQL Server, StackOverflow
- Теория множеств, MariaDB
- Сложность операций Python, профессор Ричард Э. Паттис
- Теория множеств - Дизайн компьютерных программ, Udacity
- Теория множеств | Введение , GeeksforGeeks
