Kotlin知識歸納（八） —— 序列

前序

??????之前探究集合的函數(shù)式Api時發(fā)現(xiàn)秦躯，這些函數(shù)都會遍歷集合并且提早創(chuàng)建新集合，每一步的中間結(jié)果會被存儲在新集合中斩披。當(dāng)數(shù)據(jù)量很大時端姚，調(diào)用十分的低效晕粪。

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

image

序列

??????序列對每個元素逐個執(zhí)行所有處理步驟，可以避免構(gòu)建中間變量渐裸，提高整個集合處理鏈的性能巫湘。序列也稱為惰性集合，序列與Java8中的Stream很像昏鹃，序列是Kotlin對流這種概念提供的實現(xiàn)尚氛。

??????Kotlin惰性集合操作的入口是 Sequence 接口。該接口只有 iterator 方法洞渤，用來從序列中獲取值阅嘶。

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

創(chuàng)建序列

創(chuàng)建序列有四種方式：

1、使用頂層函數(shù)sequenceOf()载迄，將元素作為其參數(shù)讯柔。（類似創(chuàng)建集合的那一堆頂層函數(shù)，如listOf）

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

2护昧、使用Iterable的擴(kuò)展函數(shù)asSequence()將集合轉(zhuǎn)換為序列魂迄。(常用)

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

3、使用generateSequence()惋耙。給定一個初識的元素捣炬，并提供函數(shù)計算下一個元素。該函數(shù)會一直生成序列的元素绽榛，直到函數(shù)實參返回null為止湿酸。如果函數(shù)實參不返回null,則該序列將是一個無限序列：

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

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

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

4、使用sequence()函數(shù).該函數(shù)接收一個函數(shù)類型為 SequenceScope<T>.() -> Unit的實參灭美⊥评＃可以在傳遞給sequence()函數(shù)的lambda表達(dá)式中使用SequenceScope對象的 yield() 和 yieldAll() 添加序列元素。yield()用于添加單個序列元素; yieldAll()用于將列表或序列中的元素轉(zhuǎn)化為新序列的元素冲粤。

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

中間操作和終端操作

??????序列一樣可以像集合一樣調(diào)用函數(shù)式Api美莫，但序列的操作分為兩大類：中間操作和終端操作页眯。

??????中間操作的定義：中間操作始終是惰性的梯捕，中間操作返回的是另一個序列。

可以通過函數(shù)的返回信息窝撵，判斷是否為中間操作：

//filter函數(shù)傀顾，返回Sequence<T>，中間操作碌奉。
//注意這是一個帶Sequence<T>接收者的函數(shù)類型參數(shù)６淘寒砖！
public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
    return FilteringSequence(this, true, predicate)
}

//map函數(shù)，返回Sequence<T>嫉拐，中間操作
//注意這是一個帶Sequence<T>接收者的函數(shù)類型參數(shù)Ａǘ肌！
public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R> {
    return TransformingSequence(this, transform)
}

惰性怎么理解呢婉徘？執(zhí)行以下例子：

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

image

??????結(jié)果是并無任何打印漠嵌，表示filter和map函數(shù)被"延遲"了，只有配合末端操作求結(jié)果時盖呼，中間操作的才被觸發(fā)儒鹿。

??????末端操作定義：觸發(fā)執(zhí)行所有的延期計算（指中間操作），并返回一個結(jié)果几晤，結(jié)果可能是集合约炎、數(shù)字等。

//forEach函數(shù)蟹瘾，返回值不是序列圾浅，末端操作
//注意這是一個帶Sequence<T>接收者的函數(shù)類型參數(shù)！
public inline fun <T> Sequence<T>.forEach(action: (T) -> Unit): Unit {
    for (element in this) action(element)
}

//count函數(shù)热芹，返回值不是序列贱傀，末端操作
//注意這是一個帶Sequence<T>接收者的函數(shù)類型參數(shù)！
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
}

中間操作為什么是惰性的

??????估計很多小伙伴應(yīng)該和我一樣伊脓，很好奇為什么中間操作是惰性的府寒？想要得到答案，那就只能去查看源碼進(jìn)行分析了报腔，先看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()函數(shù)會創(chuàng)建一個匿名的Sequence匿名類對象株搔，并將集合的迭代器存儲起來，作為自己iterator()方法的返回值纯蛾。

中間操作

（可以直接跳過代碼纤房，看結(jié)果）

#filter函數(shù)
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
        
        //計算該中間操作的實現(xiàn)（簡單說就是在）
        private fun calcNext() {
            while (iterator.hasNext()) {
                val item = iterator.next()
                //執(zhí)行謂詞lambda，判斷是否符合條件
                if (predicate(item) == sendWhen) {
                    //符合條件則獲取元素
                    nextItem = item
                    //并修改狀態(tài)
                    nextState = 1
                    return
                }
            }
            nextState = 0
        }

        override fun next(): T {
            //檢查機(jī)制
            if (nextState == -1)
                calcNext()
            if (nextState == 0)
                throw NoSuchElementException()
            //獲取值翻诉，并將狀態(tài)重置
            val result = nextItem
            nextItem = null
            nextState = -1
            @Suppress("UNCHECKED_CAST")
            //返回值
            return result as T
        }

        override fun hasNext(): Boolean {
            //在上一個序列的迭代器的基礎(chǔ)上炮姨，進(jìn)行謂詞運算，判斷是否有下一個
            if (nextState == -1)
                calcNext()
            return nextState == 1
        }
    }
}

#map函數(shù)
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 {
            //用函數(shù)類型參數(shù)進(jìn)行運算碰煌，返回值
            return transformer(iterator.next())
        }

        override fun hasNext(): Boolean {
            //沿用上一個序列的迭代器的hasNext()函數(shù)
            return iterator.hasNext()
        }
    }

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

結(jié)合其他中間操作的代碼得到的結(jié)果是：

1舒岸、中間操作都會獲取上一個序列（因為是帶序列接收者的lambda）的迭代器。
2芦圾、自身實現(xiàn)Sequence接口所獲得的iterator()函數(shù)蛾派，將返回一個匿名的迭代器對象。
3、自身的迭代器對象的hasNext()函數(shù)將調(diào)用上一個序列的迭代器的hasNext()函數(shù)洪乍，或在上一個序列的迭代器的基礎(chǔ)上進(jìn)行封裝眯杏。
4、自身的迭代器對象的next()函數(shù)壳澳，將調(diào)用該中間操作所接收的函數(shù)類型參數(shù)進(jìn)行運算岂贩，最后返回一個值。
總的來說巷波，中間操作只是對迭代器的一層層封裝河闰，而內(nèi)部并無使用while或for進(jìn)行迭代。

末端操作

（可以直接跳過代碼褥紫，看結(jié)果）

#forEach函數(shù)
public inline fun <T> Sequence<T>.forEach(action: (T) -> Unit): Unit {
    //迭代進(jìn)行（注意該this姜性，是指最后一個中端操作返回的Sequence對象）
    for (element in this) 
        action(element)
}

#count函數(shù)
public inline fun <T> Sequence<T>.count(predicate: (T) -> Boolean): Int {
    var count = 0
    //迭代進(jìn)行（注意該this，是指最后一個中端操作返回的Sequence對象）
    for (element in this) 
        if (predicate(element)) 
            checkCountOverflow(++count)
    return count
}

結(jié)合其他末端操作的代碼得到的結(jié)果是：

1髓考、末端操作使用中間操作返回Sequence對象（因為末端操作也是帶序列接收者的lambda）獲取迭代器部念，用于forEach循環(huán)中。(這就解析了為什么要加末端操作才能是中間操作被執(zhí)行氨菇，因為只有在forEach中迭代器才能被使用儡炼。這時，中間操作的返回值才能從迭代器的next()中返回查蓉。)
2乌询、在forEach中對每一個元素作為值傳給函數(shù)類型的參數(shù)進(jìn)行運算。

整體流程如下所示：

image

如果在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實例嵌套創(chuàng)建，得到最后一個中間操作的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

??????可以看到鹃共，各個中間操作都會產(chǎn)生的Sequence對象鬼佣，都按照其調(diào)用的順序進(jìn)行嵌套，最后得到最后一個中間操作的Sequence對象霜浴。

提取重點代碼（2）：

//獲取最后一個中間操作的Sequence對象
Iterator var4 = $this$forEach$iv.iterator();

//末端操作迭代迭代器晶衷，調(diào)用迭代器的next()方法時，將按照中間操作嵌套的瞬間執(zhí)行中間操作對應(yīng)的迭代器next方法阴孟，得到中間操作的返回值
//晌纫。最后一個中間操作的返回值交由末端操作處理
while(var4.hasNext()) {
 Object element$iv = var4.next();
 //..
}

??????末端操作的for循環(huán)會變成while循環(huán)，但還是依據(jù)迭代器進(jìn)行迭代永丝。迭代過程中不斷調(diào)用各個中間操作的迭代器锹漱，執(zhí)行中間操作，最后將中間操作得到的值交由末端操作進(jìn)行處理类溢。

總結(jié)

??????Kotlin的序列使用裝飾設(shè)計模式凌蔬，對集合轉(zhuǎn)換的匿名Sequence對象進(jìn)行動態(tài)擴(kuò)展。所謂裝飾設(shè)計模式就是在不繼承的情況下闯冷，使類變得更強(qiáng)大（例如Java的I/O流）砂心。最后在末端操作中調(diào)用Sequence的迭代器進(jìn)行迭代，觸發(fā)中間操作蛇耀，并獲取其返回值進(jìn)行處理并輸出辩诞。