Как последовательность действий сравнивается со списком под капотом в Kotlin

Сегодня я собираюсь поговорить о Sequence в Kotlin и о том, как он работает под деревом. В качестве последовательности мы в основном говорим о лямбда-функции оператора и о том, чем она отличается от интерфейса List.

Последовательность похожа на библиотеку коллекций из Java

public interface Sequence<out T> {
    
    public operator fun iterator(): Iterator<T>
}

То же, что и List, но имеет только одну функцию, которая возвращает объект-итератор.

Все операторы являются функциями расширения, о которых мы поговорим ниже.

Это простой способ создать объект Sequence.

val seq : Sequence = listOf(1,2,3).asSequence()

asSequence() функция - это функция расширения Iterable.

public fun <T> Iterable<T>.asSequence(): Sequence<T> {
    // Create by Sequence anonymous class use the iterator same as list object 
    return Sequence { this.iterator() }
}

Из приведенного выше кода мы можем сказать, что нам нужно сначала создать объект List, а затем использовать функцию asSequence для преобразования объекта List в объект Sequence.

Итак, зачем нам Sequence, если у нас уже есть List. Вот простая разница с точки зрения оператора.

У нас есть две простые операторные функции.

val list : List<Int> = listOf(1,2,3).also { list ->
    list.map { it + 1 }.filter { it != 1 }
}
val seq : Sequence = listOf(1,2,3).also { seq -> 
    seq.map { it + 1 }.filter { it != 1 }
}

В объекте List он перебирает все элементы внутри списка, возвращает новый объект List, затем переходит к следующей операторной функции filter, мы снова запускаем процесс.

Мы просто посмотрим на функцию map из списка

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

public inline fun <T, R, C : MutableCollection<in R>> Iterable<T>.mapTo(destination: C, transform: (T) -> R): C {
    for (item in this)
        destination.add(transform(item))
    return destination
}

Мы видим, что он создаст новый объект List для хранения новых transformed элементов в destination

Итак, если у нас есть 10 операторов, он создаст 10 объектов List, и ему нужно будет перебирать все элементы, пока все они не будут добавлены в список.

Теперь давайте посмотрим на Sequence исходный код.

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

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

Как и List, он принимает в качестве аргумента лямбда-функцию.

internal class TransformingSequence<T, R>
constructor(private val sequence: Sequence<T>, private val transformer: (T) -> R) : Sequence<R> {
    override fun iterator(): Iterator<R> = object : Iterator<R> {
        val iterator = sequence.iterator()
        override fun next(): R {
            return transformer(iterator.next())
        }

        override fun hasNext(): Boolean {
            return iterator.hasNext()
        }
    }

    internal fun <E> flatten(iterator: (R) -> Iterator<E>): Sequence<E> {
        return FlatteningSequence<T, R, E>(sequence, transformer, iterator)
    }
}

Но вот главное отличие.

Для map он создаст новый объект Sequence из TransformingSequence, который реализует интерфейс Sequence и имеет свою собственную реализацию для функции iterator.

TransformingSequence имеет два свойства: последовательность, которая относится к предыдущей последовательности, и преобразователь, как лямбда-функция преобразования.

Что касается функции iterator, если вы присмотритесь, вы поймете сейчас.

По сути, sequence преобразует элемент только при вызове next()

Если нам нужно использовать последовательность после преобразования, нам нужно вызвать toList()

Поэтому независимо от того, сколько у вас операторов, он управляет оператором только тогда, когда вы вызываете toList. Для каждого оператора он преобразует последовательность в объект различия и обновляет текущий iterator.

О реализации итератора

override fun next(): R {
            return transformer(iterator.next())
        }

Мы видим, что это рекурсивная функция.

Мы получаем текущий элемент из previous sequence, используем transformer для преобразования текущего элемента в новый элемент, затем перебираем следующий элемент.

Итак по образцу

val seq : Sequence = listOf(1,2,3).also { seq -> 
    seq.map { it + 1 }.filter { it != 1 }.toList()

Он будет выполнять map функцию, 1+1 затем пройти filter 2 != 1 и так далее ...

Вот и все ! Спасибо за чтение !

Если у меня есть ошибки в этой статье, прокомментируйте их ниже.

Если вы хотите узнать больше о Sequence, прочтите эту статью.