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

Более интересным примером является Power Set набора (P(s)), то есть набор, содержащий все подмножества текущего набора (включая пустой набор). Это означает, что он имеет гораздо большую кардинальность (размер), чем исходный набор. Хотя бесконечность сама по себе не является числом, на самом деле вы можете определить большую бесконечность, чем бесконечность, воспользовавшись наборами степеней и идеей количества элементов. Я не буду вдаваться в подробности, но это небольшой дополнительный кусочек математики. Если вам интересно, в Википедии есть отличные статьи об этих теориях. В частности, взгляните на статью об «Алеф Нуль»; это отличное чтение!

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

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

История

В области математики немецкий математик по имени Георг Кантор отвечал за разработку множеств и теории множеств в 1874 году. Его статья называлась «О свойстве совокупности всех действительных алгебраических чисел». Понимание множеств — это процесс, который в значительной степени зависит от математики, поэтому я бы порекомендовал заядлым ученикам ознакомиться с основными идеями, прежде чем использовать их в программировании. Наборы появляются снова и снова в компьютерных науках, так что я не могу не подчеркнуть этого достаточно.

Что касается раннего использования программирования, то в конце 1960-х годов был разработан язык высокого уровня под названием SETL, основанный исключительно на теории множеств. Его изобрел Джейкоб Шварц из Нью-Йоркского университета. Многие языки программирования с тех пор имеют реализацию набора. C++, Java, Objective-C, Python и платформа .NET — вот некоторые известные примеры.

Представление

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

Можно использовать список элементов. В результате для проверки принадлежности потребуются итерации и условные проверки временной сложности O(n). Это было бы в равной степени верно и для удаления. Но наборы часто также реализуются с помощью деревьев, попыток или карт (на основе хеш-таблиц). В реализации на основе карты каждый ключ был бы часовым, просто описывающим текущий элемент набора. Значением будет член множества. Карты, как мы знаем, обеспечивают амортизированные средние случаи O (1) для многих операций.

Реализация на C++ использует двоичное дерево поиска. Java имеет три реализации, выходящие из интерфейса Set: HashSet, SortedSet и TreeSet. Как вы могли догадаться, каждая реализация поддерживается чем-то другим. Отсортированный набор также позволяет иметь упорядоченный набор. C# также имеет классы HashSet и SortedSet.

Альтернативы

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