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. Если мы сначала вызовем коллекцию, а затем преобразуем результат, то создадим только один новый объект — жёлтый квадрат. С последовательности мы не создаём два новых объекта. С коллекциями — не создаём список.
Терминальные операции могут закончить обработку раньше, а промежуточные последовательности вычисляются лениво. Значит, последовательности могут помочь избежать лишней работы. Всегда проверяйте порядок трансформаций!
Встраивание и большие массивы данных
Операции в коллекции используют встраиваемые функции, так что байткод самих операций и лямбда‐выражений, переданных как параметры, будет встроен. Коллекции создают новый список для каждого преобразования. Последовательности же содержат ссылку на функции преобразования.
Когда мы работаем с небольшим коллекциями и одной-двумя операциями, разница в производительности не существенна. Можно использовать коллекции. Но, когда вы работаете с большими списками, они могут стать дорогостоящими. Используйте последовательности.
К сожалению, я не знаю ни одного проведённого бенчмарка, который помог бы лучше понять, как производительность коллекций и последовательностей зависит от их размеров и цепочек операций.
В зависимости от размера данных выберите подходящий контейнер: коллекции — для небольших списков, последовательности — для больших. И помните о порядке преобразований.
Читайте также:
Перевод статьи: Florina Muntenescu: Collections and sequences in Kotlin
