Встречайте Kotlin-версию defaultDict

Мы все знаем, что такое (хеш)карта, и если вы знаете язык программирования Python, вы, вероятно, в какой-то момент столкнулись с defaultdict. Мне было интересно, доступна ли такая же конструкция в Kotlin, и я объясню свою находку в этой статье.

Документацию для Python defaultdict, включая пару примеров, можно найти здесь. Его основное использование демонстрируется в следующем фрагменте:

Словарь по умолчанию получил свое название из-за того, что он включает значения по умолчанию для ключей, которые ему еще не известны. Как в приведенном выше примере, где клиент пытается взять случайное значение из карты, что приводит к значению 0, хотя на эту карту никогда ничего не записывалось.

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

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

Давайте теперь рассмотрим язык программирования Kotlin и посмотрим, сможем ли мы иметь такое же поведение, как с Python defaultdict.

Простая проблема

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

Хотя в Kotlin есть естественный функциональный способ сделать это, мы хотим сначала рассмотреть некоторые итерационные подходы. Начнем со следующего.

Подход 1: итеративное решение без значений по умолчанию

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

Подход 2: итеративное решение с явными значениями по умолчанию

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

countMap[e] = countMap.getOrDefault(e, 0) + 1

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

Итеративное решение с неявными значениями по умолчанию

Подобно Python defaultdict, Kotlin поставляется с аккуратным расширением под названием MutableMap::withDefault, и оно выглядит так:

Это расширение позволяет предоставить инициализатор для ключей, которые не имеют связанного значения на карте. Давайте используем его в нашем решении:

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

Важная заметка

Есть одна важная вещь, о которой вам нужно знать при использовании расширения withDefault, которое является частью его документации:

[…] Это неявное значение по умолчанию используется, когда исходная карта не содержит значения для указанного ключа, а значение получено с помощью функции [Map.getValue] […]

Значение по умолчанию будет предоставлено только в том случае, если вы используете Map::getValue, что не имеет места при доступе к карте с операторами индекса.

Причиной этого является контракт интерфейса Map, в котором говорится:

Возвращает значение, соответствующее заданному [ключу], или null, если такой ключ отсутствует на карте.

Так как дефолтные карты хотят выполнить этот контракт, они не могут вернуть ничего, кроме null в случае несуществующих ключей, что ранее обсуждалось на Kotlin forum.

Давайте идиоматично

Хорошо, мы увидели, что Kotlin действительно предоставляет способы предоставления значений по умолчанию в картах, и это здорово. Но разве идиоматично писать код так, как мы это делали в приведенных выше примерах? Смотря как. Большинство случаев можно решить гораздо проще, используя функциональные API Kotlin, которые имеют встроенные функции группировки и подсчета.

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

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

В Котлине есть десятки способов решения данной проблемы, но, пожалуй, самый короткий (хотя и не самый оптимальный) из них является функциональным:

Заключение

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

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

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