5. Основы Kotlin. Ассоциативные массивы Maps и множества Sets

Множества

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

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

В программировании множества используются аналогичным образом. Множество Set<T> является набором уникальных с точки зрения равенства на == элементов типа T, и основная доступная операция — включает или нет множество какой-то элемент.

Рассмотрим, как множества могут использоваться на практике. Пусть нам необходимо взять какой-то текст (в виде списка слов) и убрать из него определенные слова-паразиты (например, “типа”, “как бы”, “короче”). Это можно сделать вот так.

fun removeFillerWords(
        text: List<String>,
        vararg fillerWords: String): List<String> {
    val fillerWordSet = setOf(*fillerWords)

    val res = mutableListOf<String>()
    for (word in text) {
        if (word !in fillerWordSet) {
            res += word
        }
    }
    return res
}

Наша функция принимает на вход текст text в виде списка строк и, в виде параметра переменной длины fillerWords, — набор тех слов-паразитов, которые мы хотим из текста удалить. Первым делом мы строим из нашего параметра переменной длины множество слов-паразитов при помощи функции setOf. Обратите внимание, что здесь мы пользуемся оператором раскрытия * для передачи массива в эту функцию, чтобы итоговое множество было построено из переданных в функцию элементов.

После получения этого множества мы проходимся по всем элементам текста и, если элемент не является словом-паразитом (word !in fillerWordSet), мы добавляем его в список результата. Когда мы перебрали все элементы, мы возвращаем результат обратно.

NB: данная задача очень хорошо ложится в концепцию функций высших порядков, которую мы с вами обсуждали в прошлом уроке. С использованием функции filter наше решение будет выглядеть совсем просто:

fun removeFillerWords(
        text: List<String>,
        vararg fillerWords: String): List<String> {
    val fillerWordSet = setOf(*fillerWords)
    return text.filter { it !in fillerWordSet }
}

Попробуем написать тесты для нашей функции removeFillerWords.

@Test
@Tag("Example")
fun removeFillerWords() {
    assertEquals(
        "Я люблю Котлин".split(" "),
        removeFillerWords(
            "Я как-то люблю Котлин".split(" "),
            "как-то"
        )
    )
    assertEquals(
        "Я люблю Котлин".split(" "),
        removeFillerWords(
            "Я как-то люблю таки Котлин".split(" "),
            "как-то",
            "таки"
        )
    )
    assertEquals(
        "Я люблю Котлин".split(" "),
        removeFillerWords(
            "Я люблю Котлин".split(" "),
            "как-то",
            "таки"
        )
    )
}

При написании тестов мы используем функцию str.split(delim1, delim2, …​), которая разбивает строку-получатель str на список строк по указанным строкам-разделителям delimN, как раз для получения списка строк, соответствующего какому-либо тексту. Если запустить наши тесты, то они — ура-ура — успешно пройдут.

Основной вопрос, который возникает при взгляде на наше решение, — а зачем здесь множества? Почему нельзя было работать с оригинальным массивом слов-паразитов fillerWords? И действительно, если поменять решение соответствующим образом, то тесты все также будут проходить.

fun removeFillerWords(
        text: List<String>,
        vararg fillerWords: String): List<String> {
    val res = mutableListOf<String>()
    for (word in text) {
        if (word !in fillerWords) {
            res += word
        }
    }
    return res
}

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

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

Более подробно вопросы эффективности вы будете изучать дальше на вашем пути обучения программированию, пока что можно запомнить очень простую идею — множество элементов лучше представлять как множество типа Set.

Распространенные операции над множествами

Рассмотрим основные операции, доступные над множествами.

• set.size / set.count() возвращает количество элементов в множестве
• e in set / set.contains(e) проверяет, содержится ли элемент e во множестве set
• set.intersect(otherSet) осуществляет пересечение множеств
• set.union(otherSet) объединяет два множества
• set + e / set + array / set + list создает новое множество с добавленным элементом или элементами
• set - e / set - array / set - list возвращает множество, из которого удалены указанные элементы

Все операции поддерживают уникальность элементов в результирующем множестве автоматически.

Изменяемые множества

“И в третий раз…​” мы с вами вспомнили о том, что иногда нам хочется изменять объекты в программе, в том числе, множества. По аналогии с предыдущими случаями, тип изменяемого множества — это MutableSet<T>, и он расширяет тип обычного множества, добавляя операции по добавлению и удалению из множества элементов.

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

fun buildWordSet(text: List<String>): MutableSet<String> {
    val res = mutableSetOf<String>()
    for (word in text) res.add(word)
    return res
}

Для добавления новых слов в изменяемое множество, которое является результатом, мы используем функцию set.add(word). Поддержание уникальности содержащихся в множестве элементов выполняется автоматически. В остальном, наше решение должно быть достаточно понятным для вас без дополнительных объяснений.

Посмотрим на тесты для нашей функции.

@Test
@Tag("Example")
fun buildWordSet() {
    assertEquals(
        buildWordSet("Я люблю Котлин".split(" ")),
        mutableSetOf("Я", "люблю", "Котлин")
    )
    assertEquals(
        buildWordSet("Я люблю люблю Котлин".split(" ")),
        mutableSetOf("Котлин", "люблю", "Я")
    )
    assertEquals(
        buildWordSet(listOf()),
        mutableSetOf<String>()
    )
}

На что можно обратить здесь внимание? В отличие от списков, для равенства множеств порядок элементов не является важным; причем это верно как для изменяемых, так и для неизменяемых множеств. Это напрямую следует из свойств множеств из математики, где равенство множеств работает именно так.

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