Kotlin. Коллекции и последовательности

Novikov Ivan
Jul 24 · 4 min read

Kotlin из коробки предоставляет два способа обработки данных: энергичный для Collection и ленивый для Sequence.


Collection и Sequence

Разница между ленивыми и энергичными вычислениями в том, когда они происходят. Коллекция трансформируется энергично. Каждая операция выполняется в момент вызова, а результат преобразования — новая коллекция. Преобразователи коллекций — это встраиваемые функции. Ниже встраиваемая функция map, создающая новый ArrayList:

public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}

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

  • map, distinct, groupBy и т.д. — промежуточные, возвращают Sequence.
  • first, toList, count и т.д. — терминальные, не возвращают Sequence.

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

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

public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R>{      
return TransformingSequence(this, transform)
}

Терминальные операции выполняются до совпадения с предикатом:

public inline fun <T> Sequence<T>.first(predicate: (T) -> Boolean): T {
for (element in this) if (predicate(element)) return element
throw NoSuchElementException(“Sequence contains no element matching the predicate.”)
}

В итераторе TransformingSequence из map применяется сохраненное преобразование:

internal class TransformingIndexedSequence<T, R> 
constructor(private val sequence: Sequence<T>, private val transformer: (Int, T) -> R) : Sequence<R> {override fun iterator(): Iterator<R> = object : Iterator<R> {
//…
override fun next(): R {
return transformer(checkIndexOverflow(index++), iterator.next())
}
//…
}

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

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

Коллекции

  • Вызывается map — создаётся новый ArrayList. Мы обрабатываем все элементы начальной коллекции и преобразуем её с копированием объектов. Меняем цвет и добавляем объект в новую коллекцию.
  • Вызывается first. Мы обрабатываем каждый элемент до тех пор, пока не найдём квадрат.

Последовательности

  • asSequence — последовательность создаётся на основе итератора оригинальной коллекции.
  • map. Трансформация добавляется в список выполняемых операций, но не выполняется.
  • first. Это терминальная операция. Значит, выполняются операции из списка выше. Обрабатываем каждый элемент начальной последовательности map и сразу же first. Условие из first выполняется уже на втором элементе. Не нужно обрабатывать всю последовательность!

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

Порядок преобразований

Используете вы коллекции или последовательности, порядок преобразований имеет значение. В примере выше first может не вызываться для всего списка строго после map: это не имеет значения для map. Если мы сначала вызовем коллекцию, а затем преобразуем результат, то создадим только один новый объект — жёлтый квадрат. С последовательности мы не создаём два новых объекта. С коллекциями — не создаём список.

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

Встраивание и большие массивы данных

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

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

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


В зависимости от размера данных выберите подходящий контейнер: коллекции — для небольших списков, последовательности — для больших. И помните о порядке преобразований.

Перевод статьи: Florina Muntenescu: Collections and sequences in Kotlin

NOP::Nuances of programming

Перевод и адаптация статей в сфере IT

Novikov Ivan

Written by

NOP::Nuances of programming

Перевод и адаптация статей в сфере IT

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade