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

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 и многие другие. Проверьте список здесь, прежде чем писать собственные.

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

data class Shape(val edges: Int, val angle: Int = 0, val color: Int)

val circle = Shape(edges = 0, color = 1)
val square = Shape(edges = 4, color = 2)
val rhombus = Shape(edges = 4, angle = 45, color = 3)
val triangle = Shape(edges = 3, color = 4)
val shapes = listOf(circle, square, rhombus, triangle)

fun main() {
    println(shapes.map {it.color}.toList())
    
    val yellowSquareSequence = shapes.asSequence().map {
        it.copy(color = 3)
    }.first {
        it.edges == 4
    }
    println(yellowSquareSequence)
   
    val yellowSquareCollection = shapes.map {
        it.copy(color = 3)
    }.first {
        it.edges == 4
    }
    println(yellowSquareCollection)
}

[1, 2, 3, 4]
Shape(edges=4, angle=0, color=3)
Shape(edges=4, angle=0, color=3)

Коллекции

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

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

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

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

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

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

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

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

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

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

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