Kotlin知识归纳（八） —— 序列

前序

      之前探究集合的函数式Api时发现，这些函数都会遍历集合并且提早创建新集合，每一步的中间结果会被存储在新集合中。当数据量很大时，调用十分的低效。

fun main(args: Array<String>) {
    val list = (1..10).toList()
    list.filter { 
        it % 2 == 0
    }.map { 
        it * it
    }.forEach {
        println(it)
    }
}

序列

      序列对每个元素逐个执行所有处理步骤，可以避免构建中间变量，提高整个集合处理链的性能。序列也称为惰性集合，序列与Java8中的Stream很像，序列是Kotlin对流这种概念提供的实现。

      Kotlin惰性集合操作的入口是 Sequence 接口。该接口只有 iterator 方法，用来从序列中获取值。

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

创建序列

创建序列有四种方式：

• 1、使用顶层函数sequenceOf()，将元素作为其参数。（类似创建集合的那一堆顶层函数，如listOf）

val numbers= sequenceOf(1,2,3,4,5,6,7,8,9,10)

• 2、使用Iterable的扩展函数asSequence()将集合转换为序列。(常用)

val numbers = (1..10).toList().asSequence()

• 3、使用generateSequence()。给定一个初识的元素，并提供函数计算下一个元素。该函数会一直生成序列的元素，直到函数实参返回null为止。如果函数实参不返回null,则该序列将是一个无限序列：

val numbers = generateSequence(6){
    it + 2
}

使用generateSequence()提供有限序列：

val numbers = generateSequence(6){
    if (it < 10) 
        it + 2 
    else 
        null
}

• 4、使用sequence()函数.该函数接收一个函数类型为 SequenceScope<T>.() -> Unit的实参。可以在传递给sequence()函数的lambda表达式中使用SequenceScope对象的 yield() 和 yieldAll() 添加序列元素。yield()用于添加单个序列元素; yieldAll()用于将列表或序列中的元素转化为新序列的元素。

val numbers = sequence{
    yield(1)
    yieldAll(listOf(2,3))
    yieldAll(setOf(4,5))
    yieldAll(generateSequence(6){
        if (it < 10)
            it + 1
        else
            null
    })
}

中间操作和终端操作

      序列一样可以像集合一样调用函数式Api，但序列的操作分为两大类：中间操作和终端操作。

      中间操作的定义：中间操作始终是惰性的，中间操作返回的是另一个序列。

可以通过函数的返回信息，判断是否为中间操作：

//filter函数，返回Sequence<T>，中间操作。
//注意这是一个带Sequence<T>接收者的函数类型参数！！
public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
    return FilteringSequence(this, true, predicate)
}

//map函数，返回Sequence<T>，中间操作
//注意这是一个带Sequence<T>接收者的函数类型参数！！
public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R> {
    return TransformingSequence(this, transform)
}

惰性怎么理解呢？执行以下例子：

val list = (1..10).toList()
list.asSequence()
    .filter {
        println("filter $it")
        it % 2 == 0
    }.map {
        println("map $it")
        it * it
    }

      结果是并无任何打印，表示filter和map函数被"延迟"了，只有配合末端操作求结果时，中间操作的才被触发。

      末端操作定义：触发执行所有的延期计算（指中间操作），并返回一个结果，结果可能是集合、数字等。

//forEach函数，返回值不是序列，末端操作
//注意这是一个带Sequence<T>接收者的函数类型参数！
public inline fun <T> Sequence<T>.forEach(action: (T) -> Unit): Unit {
    for (element in this) action(element)
}

//count函数，返回值不是序列，末端操作
//注意这是一个带Sequence<T>接收者的函数类型参数！
public inline fun <T> Sequence<T>.count(predicate: (T) -> Boolean): Int {
    var count = 0
    for (element in this) if (predicate(element)) checkCountOverflow(++count)
    return count
}

中间操作为什么是惰性的

      估计很多小伙伴应该和我一样，很好奇为什么中间操作是惰性的？想要得到答案，那就只能去查看源码进行分析了，先看asSequence()：

public fun <T> Iterable<T>.asSequence(): Sequence<T> {
    return Sequence { this.iterator() }
}

public inline fun <T> Sequence(crossinline iterator: () -> Iterator<T>): Sequence<T> = object : Sequence<T> {
    override fun iterator(): Iterator<T> = iterator()
}

      asSequence()函数会创建一个匿名的Sequence匿名类对象，并将集合的迭代器存储起来，作为自己iterator()方法的返回值。

中间操作

（可以直接跳过代码，看结果）

#filter函数
public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
    //返回一个FilteringSequence对象
    return FilteringSequence(this, true, predicate)
}

internal class FilteringSequence<T>(
    private val sequence: Sequence<T>,
    private val sendWhen: Boolean = true,
    private val predicate: (T) -> Boolean
) : Sequence<T> {

    override fun iterator(): Iterator<T> = object : Iterator<T> {
        //获取上一个序列的迭代器
        val iterator = sequence.iterator()
        // -1 for unknown, 0 for done, 1 for continue
        var nextState: Int = -1 
        var nextItem: T? = null
        
        //计算该中间操作的实现（简单说就是在）
        private fun calcNext() {
            while (iterator.hasNext()) {
                val item = iterator.next()
                //执行谓词lambda，判断是否符合条件
                if (predicate(item) == sendWhen) {
                    //符合条件则获取元素
                    nextItem = item
                    //并修改状态
                    nextState = 1
                    return
                }
            }
            nextState = 0
        }

        override fun next(): T {
            //检查机制
            if (nextState == -1)
                calcNext()
            if (nextState == 0)
                throw NoSuchElementException()
            //获取值，并将状态重置
            val result = nextItem
            nextItem = null
            nextState = -1
            @Suppress("UNCHECKED_CAST")
            //返回值
            return result as T
        }

        override fun hasNext(): Boolean {
            //在上一个序列的迭代器的基础上，进行谓词运算，判断是否有下一个
            if (nextState == -1)
                calcNext()
            return nextState == 1
        }
    }
}

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

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 {
            //沿用上一个序列的迭代器的hasNext()函数
            return iterator.hasNext()
        }
    }

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

结合其他中间操作的代码得到的结果是：

• 1、中间操作都会获取上一个序列（因为是带序列接收者的lambda）的迭代器。
• 2、自身实现Sequence接口所获得的iterator()函数，将返回一个匿名的迭代器对象。
• 3、自身的迭代器对象的hasNext()函数将调用上一个序列的迭代器的hasNext()函数，或在上一个序列的迭代器的基础上进行封装。
• 4、自身的迭代器对象的next()函数，将调用该中间操作所接收的函数类型参数进行运算，最后返回一个值。
• 总的来说，中间操作只是对迭代器的一层层封装，而内部并无使用while或for进行迭代。

末端操作

（可以直接跳过代码，看结果）

#forEach函数
public inline fun <T> Sequence<T>.forEach(action: (T) -> Unit): Unit {
    //迭代进行（注意该this，是指最后一个中端操作返回的Sequence对象）
    for (element in this) 
        action(element)
}

#count函数
public inline fun <T> Sequence<T>.count(predicate: (T) -> Boolean): Int {
    var count = 0
    //迭代进行（注意该this，是指最后一个中端操作返回的Sequence对象）
    for (element in this) 
        if (predicate(element)) 
            checkCountOverflow(++count)
    return count
}

结合其他末端操作的代码得到的结果是：

• 1、末端操作使用中间操作返回Sequence对象（因为末端操作也是带序列接收者的lambda）获取迭代器，用于forEach循环中。(这就解析了为什么要加末端操作才能是中间操作被执行，因为只有在forEach中迭代器才能被使用。这时，中间操作的返回值才能从迭代器的next()中返回。)
• 2、在forEach中对每一个元素作为值传给函数类型的参数进行运算。

整体流程如下所示：

如果在Java的角度上看，就更好理解了。先看一波反编译代码：

public static final void main(@NotNull String[] args) {
      List list = CollectionsKt.listOf(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
      Sequence $this$forEach$iv = SequencesKt.map(SequencesKt.filter(CollectionsKt.asSequence((Iterable)list), (Function1)null.INSTANCE), (Function1)null.INSTANCE);
      int $i$f$forEach = false;
      Iterator var4 = $this$forEach$iv.iterator();

      while(var4.hasNext()) {
         Object element$iv = var4.next();
         int it = ((Number)element$iv).intValue();
         int var7 = false;
         boolean var8 = false;
         System.out.println(it);
      }
   }

提取重点代码（1）：

//(1)将中间操作对呀的Sequence实例嵌套创建，得到最后一个中间操作的Sequence对象
Sequence $this$forEach$iv = SequencesKt.map(SequencesKt.filter(CollectionsKt.asSequence((Iterable)list), (Function1)null.INSTANCE), (Function1)null.INSTANCE);

将这行代码简化：

Sequence listToSequence = CollectionsKt.asSequence((Iterable)list)

Sequence filterSequence = SequencesKt.filter(listToSequence,(Function1)null.INSTANCE)

Sequence mapSequence = SequencesKt.map(filterSequence,,(Function1)null.INSTANCE)

Sequence $this$forEach$iv = mapSequence

      可以看到，各个中间操作都会产生的Sequence对象，都按照其调用的顺序进行嵌套，最后得到最后一个中间操作的Sequence对象。

提取重点代码（2）：

//获取最后一个中间操作的Sequence对象
Iterator var4 = $this$forEach$iv.iterator();

//末端操作迭代迭代器，调用迭代器的next()方法时，将按照中间操作嵌套的瞬间执行中间操作对应的迭代器next方法，得到中间操作的返回值
//。最后一个中间操作的返回值交由末端操作处理
while(var4.hasNext()) {
 Object element$iv = var4.next();
 //..
}

      末端操作的for循环会变成while循环，但还是依据迭代器进行迭代。迭代过程中不断调用各个中间操作的迭代器，执行中间操作，最后将中间操作得到的值交由末端操作进行处理。

总结

      Kotlin的序列使用装饰设计模式，对集合转换的匿名Sequence对象进行动态扩展。所谓装饰设计模式就是在不继承的情况下，使类变得更强大（例如Java的I/O流）。最后在末端操作中调用Sequence的迭代器进行迭代，触发中间操作，并获取其返回值进行处理并输出。

参考资料：

• 《Kotlin实战》
• Kotlin官网

android Kotlin系列：

Kotlin知识归纳（一） —— 基础语法

Kotlin知识归纳（二） —— 让函数更好调用

Kotlin知识归纳（三） —— 顶层成员与扩展

Kotlin知识归纳（四） —— 接口和类

Kotlin知识归纳（五） —— Lambda

Kotlin知识归纳（六） —— 类型系统

Kotlin知识归纳（七） —— 集合

Kotlin知识归纳（八） —— 序列

Kotlin知识归纳（九） —— 约定

Kotlin知识归纳（十） —— 委托

Kotlin知识归纳（十一） —— 高阶函数

Kotlin知识归纳（十二） —— 泛型

Kotlin知识归纳（十三） —— 注解

Kotlin知识归纳（十四） —— 反射