Множества в Swift: что из себя представляют Set?

Множества в Swift похожи на массивы и словари, но по сути они разные. Множества Set – интересный аспект программирования на Swift. Давайте разберемся, как их можно использовать.

Что из себя представляют множества в Swift?

Создание пустых множеств, добавление и удаление элементов очень похоже на работу с массивами и словарями:

let fruit: Set = ["apple", "banana", "strawberry", "jackfruit"]
print(fruit)
// ["banana", "apple", "jackfruit", "strawberry"]

В приведенном выше примере мы создаем новое множество fruit. Тип Set мы указываем явно. В противном случае мы бы создали массив.

Тип fruit является типом Set. Так же, как массивы и словари, множества – это обобщения.

Вы можете добавить элемент в множество:

fruit.insert("pineapple")

Или удалить элемент из множества:

fruit.remove("banana")

Предметы в множестве должны быть уникальными. Вы не можете добавить одинаковые элементы в одно множество:

var fruit: Set = ["apple", "banana", "orange"]
let result = fruit.insert("orange")
print(fruit)
 
print(result)
// ["banana", "orange", "apple"]
// (inserted: false, memberAfterInsert: "orange")

Так же, как массивы и словари, множества имеют ряд полезных функций:

• isEmpty – возвращает true, когда в множестве нет элементов.
• count – возвращает количество элементов в множестве.
• first – возвращает первый элемент в множестве.
• randomElement() – возвращает случайный элемент из множества.

Отличия множеств от массивов и словарей

Множества похожи на массивы и словари, но на самом деле они разные.

• Массив связывает числовые индексы, то есть 0…n, со значениями. Массивы имеют фиксированный порядок.
• Словарь связывает ключи со значениями.

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

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

let favorites = ["Рокки", "Матрица", "Властелин Колец"]
 
for movie in favorites {
    if movie == "The Matrix" {
        print("Матрица мой любимый фильм!")
        break
    }
}

Приведенный выше код выполняет поиск значения “Матрица”, сравнивая строку с каждым фильмом в массиве favorites. В худшем случае, чтобы найти совпадение, нам придется перебрать каждый элемент favorites.

Временная сложность вышеупомянутого алгоритма составляет O(n), так называемое линейное время. Это допустимо для 3 фильмов, но представьте, сколько времени это займет, если список фильмов будет намного больше. Возможно, вам придется перебирать тысячи фильмов один за другим.

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

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

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

Поэтому мы можем переписать наш алгоритм следующим образом:

let movies: Set = ["Рокки", "Матрица", "Властелин Колец"]
 
if movies.contains("Рокки") {
    print("Рокки - мой любимый фильм!")
}

С помощью функции мы проверяем, существует ли данная строка в множестве.

Данная функция использует механизм хэш-таблицы и не использует цикл для поиска. Она вычисляет значение хеш-функции строки и использует это значение для прямого доступа к элементу в коллекции. Если данный элемент для данного хэш-значения существует, возвращается true.

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

Использование множеств с пользовательскими объектами

Что, если мы хотим сохранить список любимых фильмов с нужными нам свойствами? Для этого мы можем создать свой собственный тип данных:

struct Movie {
    var name: String
    var year: Int
    var rating: Int
}

Добавим также инициализаторы:

init(name: String, year: Int, rating: Int) {
    self.name = name
    self.year = year
    self.rating = rating
}
 
init(withName name: String) {
    self.name = name
    self.year = 0
    self.rating = 0
}

Первая функция init() создает объект типа Movie со 3 свойствами name, year и rating. Этот инициализатор обычно создается по умолчанию, если только вы не добавляете свои собственные инициализаторы.

Второй инициализатор init(withName:) создан для нашего удобства. Свойства year и rating установлены в 0.

Прежде чем мы сможем использовать структуру Movie в множестве, структура должна соответствовать протоколу Hashable. Для этого нам нужно будет сделать 3 дополнения к нашему коду.

Во-первых, мы добавим протокол Hashable:

struct Movie: Hashable {
    ...

Во-вторых, нам нужно добавить следующую функцию в структуру Movie:

static func == (lhs: Movie, rhs: Movie) -> Bool {
    return lhs.name == rhs.name
}

Вот что она делает:

• Данная функция является частью протокола Hashable, который используется для сравнения двух объектов Movie, чтобы определить, равны ли они.
• Если они равны, функция возвращает true. Если это не так, функция возвращает false.
• Два Movie объекта, которые мы сравниваем, называются lhs и rhs, которые обозначают левую и правую стороны нашего сравнения.
• Мы определяем равенство, сравнивая свойства name двух Movie объектов. То есть мы сравниваем названия фильмов. Если имена совпадают, объекты совпадают.

В-третьих, нам нужно реализовать hash(into:) функцию. Эта функция также является частью протокола Hashable:

func hash(into hasher: inout Hasher) {
    hasher.combine(name)
}

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

Далее мы название фильма для hasher, используя функцию combine(_:). Важно, чтобы функции использовали одинаковые свойства.

На данный момент объект Movie имеет свойство с именем hashValue. Мы можем проверить, что два Movie объекта совпадают:

let a = Movie(name: "Рокки", year: 1976, rating: 5)
let b = Movie(withName: "Рокки")
 
print(a == b)
// Output: true
 
print(a.hashValue)
// Output: something like "5474910254413230307"

Создадим множество фильмов:

let movies: Set = [
    Movie(name: "Рокки", year: 1976, rating: 5),
    Movie(name: "Матрица", year: 1999, rating: 10),
    Movie(name: "Властелин Колец", year: 2001, rating: 8),
    Movie(name: "Невероятная жизнь Уолтера Митти", year: 2013, rating: 7),
    Movie(name: "Дедпул", year: 2016, rating: 3)
]

Теперь мы можем узнать, является ли выбранный фильм любимым:

if movies.contains(Movie(withName: "Рокки")) {
    print("Рокки - мой любимый фильм!")
}

В приведенном выше коде мы создаем новый объект Movie с инициализатором Movie(withName:). Так как мы реализовали протокол Hashable, мы можем использовать Movie объекты для проверки наличия данного элемента в множестве. Приведенный выше код проверяет, существует ли Rocky в множестве movies. Это операция типа O(1).

Также мы можем найти любимый фильм по рейтингу:

if let movie = movies.sorted(by: { $0.rating > $1.rating }).first {
    print("Мой любимый фильм - \(movie.name)")
}

Приведенный выше код использует функцию sorted(by:) для сортировки movies по своему свойству rating (от высшего к низшему). В результате sorted(by:) возвращает массив, отсортированный по самому высокому рейтингу, в котором мы получаем первый элемент массива с помощью свойства first.

Мы можем найти рейтинг конкретного фильма:

if let index = movies.firstIndex(of: Movie(withName: "Властелин Колец")) {
    let lotr = movies[index]
    print("Я оценил фильм = \(lotr.rating)")
}

В приведенном выше коде мы получаем индекс фильма с помощью функции firstIndex(of:). Как и в случае с фильмом, мы используем его индекс (хеш-значение).

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

Мы можем выбрать фильм с рейтингом 8 и выше:

let top = movies.filter({ $0.rating >= 8 })
 
for movie in top {
    print(movie.name)
}

Сравнение множеств

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

• union – сочетание множеств.
• subtraction – вычитание множеств.
• intersection – множество элементов, которые присутствуют в обоих множествах.
• symmetric difference – множество элементов, которые присутствуют в одном или другом множестве, но не в обоих.

Давайте сравним ингредиенты в различных сортах кофе:

let cappuccino: Set = ["espresso", "milk", "milk foam"]
let americano: Set = ["espresso", "water"]
let machiato: Set = ["espresso", "milk foam"]
let latte: Set = ["espresso", "milk"]

Union

Используем union для machiato и latte:

let result = machiato.union(latte)
print(result)
// ["espresso", "milk foam", "milk"]

Subtraction

Давайте применим subtraction americano из cappuccino:

let result = cappuccino.subtracting(americano)
print(result)
// ["milk foam", "milk"]

Неважно, что там в cappuccino нет water, потому что вы все равно не можете вычесть то, чего нет.

Имейте в виду, что a – b – это не то же самое, что b – a:

let result = americano.subtracting(cappuccino)
print(result)
// ["water"]

Intersection

Применим intersection для latte и cappuccino:

let result = latte.intersection(cappuccino)
print(result)
// ["espresso", "milk"]

Также мы также найти, что есть общего между всеми видами кофе:

let result = latte.intersection(cappuccino).intersection(machiato).intersection(americano)
print(result)
// ["espresso"]

Symmetric difference

Какая разница между americano и latte?

let result = latte.symmetricDifference(americano)
print(result)
// ["milk", "water"]