Нравится вам это или нет, базовая дискретная математика имеет решающее значение для всех разработчиков программного обеспечения. Наборы являются одним из этих ключевых основополагающих понятий💡
Этот пост посвящен множествам, которые являются важной структурой данных, которую должен знать каждый разработчик программного обеспечения. В этой статье используется язык Python, но в большинстве языков есть встроенные функции для наборов.
Что такое набор?
Набор — это неупорядоченный набор уникальных элементов.
Вот как создать набор в Python:
my_set = set()
or
my_other_set = {1, 2, 3}
Почему наборы являются полезной структурой данных?
Наборы хороши, когда вам нужно хранить коллекцию данных со следующими свойствами:
- Порядок не имеет значения
- Нет дубликатов: предметы либо входят в набор, либо нет
- Нет необходимости в парах ключ-значение, таких как hashmap/dict
- Быстрое добавление, удаление и поиск важны
Примером данных, которые были бы хороши для набора, является хранение курсов колледжа по уровням выпускников или студентов. Порядок не имеет значения, не должно быть повторяющихся номеров курсов, нет необходимости в паре ключ-значение, а быстрое добавление, удаление и поиск определенно будут полезны при изменении номеров курсов. Некоторые курсы (такие как CS3450 в следующем примере) могут быть как для выпускников, так и для студентов, поэтому операции над множествами, перечисленные далее в статье, могут быть полезны для обработки данных любым методом, который требуется приложению.
graduate_courses = {'CS340', 'CS546', 'CS3450'}
undergraduate_courses = {'CS40','CS3450','CS720'}
Примером данных, которые не подходят для набора, является хранение оценок учеников. Диктовка была бы намного лучше, потому что она может использовать пару ключ-значение, чтобы сохранить имя учащегося с правильной оценкой.
# dict, not a set
student_grades = {'Melissa': 'A', 'Bob': 'B', 'Jessica': 'F'}
Другим примером данных, которые не были бы хорошим вариантом использования для набора, является хранение победителей игрового вечера каждую неделю. Это не подходит, потому что человек может выиграть игру более одного раза, поэтому будут дубликаты. Кроме того, было бы идеально сохранить имена в порядке для надлежащего ведения учета.
# list, not a set weekly_game_winners = ['Ali', 'Julia', 'Ali', 'Sandra', 'Jess']
Установите основы
Чтобы добавить элементы в набор:
my_set = {1, 2}
my_set.add(3)
print(my_set)
>> {1, 2, 3}
Чтобы удалить элементы из набора:
my_set = {1, 2}
my_set.remove(2)
print(my_set)
>> {1}
Чтобы получить мощность (количество элементов) в наборе:
dog_names = {'Fido', 'Spot', 'Max'}
print(len(dog_names))
>> 3
Чтобы узнать, входит ли элемент в набор:
dog_names = {'Fido', 'Spot', 'Max'}
print('Fluffy' in dog_names)
>> False
print('Fido' in dog_names)
>> True
Является непересекающимся: возвращает истину, если два множества не имеют общих элементов.
cat_breeds = {'ragdoll', 'siamese', 'maine_coon'}
dog_breeds = {'lab', 'chihuahua', 'husky'}
print(cat_breeds.isdisjoint(dog_breeds))
>> True
Предмет либо есть в наборе, либо его нет. Это логическое состояние. В Python, если вы попытаетесь добавить объект в уже существующий набор, ничего не произойдет, потому что он уже есть в наборе.
my_set = {1, 2}
print(my_set)
>> {1, 2}
my_set.add(2)
print(my_set)
>> {1, 2}
Установить операции
Вот некоторые операции над множествами, которые обычно преподаются на курсах дискретной математики, и их применение в программировании.
- Союз: возвращает элементы, которые находятся в любом наборе.
computer_brands = {"dell", "lenovo", "apple"}
fruits = {"banana", "apple"}
print(computer_brands.union(fruits))
>> {'lenovo', 'dell', 'banana', 'apple'}
- Пересечение: возвращает элементы, которые находятся в обоих наборах.
computer_brands = {"dell", "lenovo", "apple"}
fruits = {"banana", "apple"}
print(computer_brands.intersection(fruits))
>> {'apple'}
- Отличие: возвращаются элементы, которые есть только в первом наборе (элементы, которые есть в обоих наборах, не включены)
computer_brands = {"dell", "lenovo", "apple"}
fruits = {"banana", "apple"}
print(computer_brands.difference(fruits))
>> {'lenovo', 'dell'}
Подмножества
Множество X является подмножеством множества Y, если каждый элемент X также присутствует в Y.
Другими словами: множество является подмножеством другого множества, если каждый элемент первого множества также содержится во втором множестве.
computer_brands = {"dell", "lenovo", "apple"}
fruits = {"banana", "apple"}
print(computer_brands.issubset(fruits))
>> False
numbers = {1, 2}
more_numbers = {1, 2, 3, 4, 5}
print(numbers.issubset(more_numbers))
>> True
Свойства временной сложности множеств:
Посетите Python Wiki, если у вас возникнут вопросы о временной сложности операций над множествами.
В этих объяснениях n — мощность (размер) множества.
Основы, которые важно знать:
- Поиски: O (1) в среднем случае и O (n) амортизированном наихудшем случае
- Добавление элементов: O(1) средний случай и O(n) амортизированный худший случай
- Удаление элементов: O(1) средний случай и O(n) амортизированный худший случай
- Итерация по набору: O (n)
Домашнее задание
Ниже приведены некоторые задачи Leetcode, которые вы можете использовать, чтобы попрактиковаться в своих знаниях о множествах. Я предлагаю сначала попробовать их самостоятельно, а затем выбрать рекомендуемое решение, если вы застряли.
- Две суммы: легко
Рекомендуемое решение: Эффективное решение Educative.io.
2. Дизайн HashSet: легко
Рекомендуемое решение: FelixTechTips на Youtube
4. Подмножества: средний
Рекомендуемое решение: Neetcode на Youtube
