網站首頁 編程語言 正文
Sequence序列
Sequence 是Kotlin標準庫提供的一種容器類型。它和Iterable一樣具備對集合進行多步驟操作能力，但是卻是采用了一種完全不同于Iterable的實現方式：
val map = (0..3).filter {
println("filter:$it")
it % 2 == 0
}.map {
println("map:$it")
it + 1
}
println(map)
上面的代碼用來演示Iterable進行連續操作的情況。它的輸出如下：
filter:0
filter:1
filter:2
filter:3
map:0
map:2
[1, 3]
像map和filter這些鏈式集合函數它們都會立即執行并創建中間臨時集用來保存數據。當原始數據不多時，這并不會有什么影響。但是，當原始數據量非常大的時候。這就會變的非常低效。而此時，就可以借助Sequence提高效率。
val sequence = (0..3).asSequence().filter {
println("filter:$it")
it % 2 == 0
}.map {
println("map:$it")
it + 1
}
println("準備開始執行")
println(sequence.toList())
上面的代碼執行結果如下：
準備開始執行
filter:0
map:0
filter:1
filter:2
map:2
filter:3
[1, 3]
對比Iterable和Sequence：
Iterable是即時的、Sequence是惰性的：前者會要求盡早的計算結果，因此在多步驟處理鏈的每一環都會有中間產物也就是新的集合產生；后者會盡可能的延遲計算結果，Sequence處理的中間函數不進行任何計算。相反，他們返回一個新Sequence的，用新的操作裝飾前一個，所有的這些計算都只是在類似toList的終端操作期間進行。
區分中間操作符和末端操作符的方式也很簡單：如果操作符返回的是一個Sequence類型的數據，它就是中間操作符。
在操作的執行方式上也有所不同：Iterable每次都是在整個集合執行完操作后再進行下一步操作——采用第一個操作并將其應用于整個集合，然后移動到下一個操作，官方將其稱呼為急切式或者按步驟執行（Eager/step-by-step）；**而Sequence則是逐個對每個元素執行所有操作。是一種惰性順序——取第一個元素并應用所有操作，然后取下一個元素，依此類推。**官方將其稱呼為惰性式或者按元素執行（Lazy/element-by-element)
序列的惰性會帶來一下幾個優點：
- 它們的操作按照元素的自然順序進行；
- 只做最少的操作；
- 元素可以是無限多個；
- 不需要在每一步都創建集合
Sequence可避免生成中間步驟的結果，從而提高了整個集合處理鏈的性能。但是，惰性性質也會帶來一些運行開銷。所以在使用時要權衡惰性開銷和中間步驟開銷，在Sequence和Iterable中選擇更加合適的實現方式。
執行的順序
sequenceOf(1,2,3)
.filter { print("F$it, "); it % 2 == 1 }
.map { print("M$it, "); it * 2 }
.forEach { print("E$it, ") }
// Prints: F1, M1, E2, F2, F3, M3, E6,
listOf(1,2,3)
.filter { print("F$it, "); it % 2 == 1 }
.map { print("M$it, "); it * 2 }
.forEach { print("E$it, ") }
// Prints: F1, F2, F3, M1, M3, E2, E6,
sequence的執行時按照元素進行的，依次對元素執行所有的操作，對一個元素而言，所有操作時依次全部執行的。而普通集合操作則是以操作步驟進行的，當所有的元素執行完當前操作后才會進入下一個操作。
只做最少的操作
試想一下我們有一千萬個數字，我們要經過幾次變換取出20個，使用下面的代碼對比一下序列和不同集合操作的性能：
fun main(){
val fFlow = FFlow()
fFlow.demoList()
fFlow.demoSequence()
}
fun demoSequence() {
val currentTimeMillis = System.currentTimeMillis()
val list =
(0..10000000).asSequence().map { it * 2 }.map { it - 1 }.take(20).toList()
println("demoSequence:${System.currentTimeMillis() - currentTimeMillis}：$list")
}
fun demoList() {
val currentTimeMillis = System.currentTimeMillis()
val list =
(0..10000000).map { it * 2 }.map { it - 1 }.take(20).toList()
println("demoList:${System.currentTimeMillis() - currentTimeMillis}：$list")
}
輸出的結果如下：
demoSequence:20ms：[-1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37]
demoList:4106ms：[-1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37]
這就是只執行最少操作的意思，序列按照元素順序執行，當取夠29個元素之后便會立即停止計算。而不同的集合則不同，沒有中間操作的概念。它的每次操作都會對整個數組中的所有元素執行完才會進行下一個——也就是前兩個map都要執行一千萬次。
序列可以是無限的
看如下代碼：
var list = emptyArray<Int>()
var i = 0
while(true){
list[i] = i++
}
list.take(10)
很明顯，這段代碼是沒法正常運行的，因為這里有一個死循環。我們也無法創建一個無限長度的集合。但是：因為序列式按步驟依照需求進行處理的，所喲我們可以創建無限序列：
val noEnd = sequence {
var i = 1
while (true) {
yield(i)
i *= 2
}
}
noEnd.take(4).toList()
//輸出:[1, 2, 4, 8]
但是一定要注意，我們雖然可以這么寫，但是務必不能真的讓while一直循環。我們不能直接使用toList。必須提供一個能結束循環的操作符，也就是不能取出所有元素（無限個）——要么使用類似take的操作來限制它們的數量，要么使用不需要所有元素的終端操作，例如first, find, any, all, indexOf等。
序列不會在每個步驟創建集合
普通的集合會在每次變換之后都會創建新的集合取存儲所有變換后的元素。而每次創建集合和填入數據都會帶來不小的性能開銷。尤其是當我們處理大量或大量的集合時，性能問題會愈發凸顯。而序列的按元素操作，則不會有這個問題。除非手動調用了終端操作符，否則不會生成新的集合。
Sequence的基本使用
Sequence序列的使用和普通的Iterable極其相似，實際上其內部也還是借助Iterable實現的。在研究它的內部實現原理之前，想從Sequence的創建和基本的序列操作來演示Sequence的基本用法。
序列的創建
創建Sequence的方式大概可以分為。分別是由元素創建、通過Iterable、借助函數以及由代碼塊創建。
由元素創建：通過調用頂級函數sequenceOf實現：
val ints = sequenceOf(1, 2, 3, 4, 5, 6, 7)
val strings = sequenceOf("a","b","c","d","e")
通過Iterable轉化：借助Iterable的擴展函數asSequence實現：
val ints = listOf(1, 2, 3, 4, 5, 6, 7).asSequence()
val strings = listOf("a","b","c","d","e").asSequence()
通過generateSequence實現：該方法有三個：
generateSequence(seedFunction: () -> T?, nextFunction: (T) -> T?): Sequence<T> generateSequence(seed: T?, nextFunction: (T) -> T?): Sequence<T> generateSequence(nextFunction: () -> T?): Sequence<T>
最終都是通過GeneratorSequence實現的，這里先不進行源碼分析。只討論使用方式：
- 其中三個函數都有的形參nextFunction可以理解為元素生成器，序列里的元素都通過調用該函數生成，當它返回為null是，序列停止生成（所以，nextFunction必須要在某個情況下返回null，否則會因為序列元素是無限多個觸發java.lang.OutOfMemoryError: Java heap space異常）。
- 而另外兩個的seedFunction和seed形參都是為了確定數據初始值的。區別在于一個直接指明，一個通過調用函數獲取。
分別用這三個函數生成0~100的序列，代碼如下：
val generateSequenceOne = generateSequence {
if (i < 100) {
i++
} else {
null
}
}
val generateSequenceTwo = generateSequence(0) {
if (it < 100) {
it+1//此處的it是上一個元素
} else {
null
}
}
val generateSequenceThree = generateSequence({ 0 }) {
if (it < 100) {
it+1//此處的it是上一個元素
} else {
null
}
}
由代碼塊生成：借助sequence(block: suspend SequenceScope.() -> Unit)函數。該函數接受一個掛起函數，該函數會接受一個SequenceScope實例，這個實例無需我們創建（后面源碼分析會講到）。SequenceScope提供了yield和yieldAll方法復雜返回序列元素給調用者，并暫停序列的執行，直到使用者請求下一個元素。
用該函數生成0~100的序列，代碼如下：
val ints = sequence {
repeat(100) {
yield(it)
}
}
序列的操作
對序列的操作可以分為中間操作和末端操作兩種。它們只要有一下另種區別：
- 中間操作返回惰性生成的一個新的序列，而末端序列則為其他普通的數據類型；
- 中間操作不會立刻執行代碼，僅當執行了末端操作序列才會開始執行。
常見的中間操作包括：map、fliter、first、last、take等；它們會序列提供數據變化過濾等增強功能基本上和kotlin提供的集合操作符有著相同的功能。
常見的末端操作有：toList、toMutableList、sum、count等。它們在提供序列操作功能的同時，還會觸發序列的運行。
Sequence源碼分析
上文對序列做了簡單的入門介紹。接下來深入源碼去了解一下Sequence的實現方式。
Sequence是什么？
Kotlin對的定義Sequence很簡單：
public interface Sequence <out T> {
public operator fun iterator(): Iterator<T>
}
就是一個接口，定義了一個返回Iterator的方法。接口本身只定義了Sequence具有返回一個迭代器的能力。具體的功能實現還是靠它的實現類完成。
可以概括一些：序列就是一個具備提供了迭代器能力的類。
序列的創建方式分析
結合上文中提到的序列的四種創建方式，我們依次分析一下它的創建流程。
我們首先以比較常用的通過Iterable轉化獲取序列，它需要借助asSequence方法分析一下，使用listOf("a","b","c","d","e").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()
}
流程很簡單，一個擴展函數加一個內聯函數。最終通過匿名內部類的方式創建一個Sequence并返回。代碼很好理解，實際上它的實現邏輯等同于下面的代碼：
val sequence = MySequence(listOf("a","b","c","d","e").iterator())
class MySequence<T>(private val iterator:Iterator<T>):Sequence<T>{
override fun iterator(): Iterator<T> {
return iterator
}
}
接著看一下通過調用頂級函數sequenceOf實現，以sequenceOf("a","b","c","d","e")為例，它的調用邏輯如下：
public fun <T> sequenceOf(vararg elements: T): Sequence<T> = if (elements.isEmpty()) emptySequence() else elements.asSequence()
可以看到依舊是借助asSequence實現的。
接下來看一下代碼塊和generateSequence的實現方式，這兩個方式會比較復雜一點，畢竟前面兩個都是借助List進行轉換，而List本身就能提供迭代器Iterator。后面兩個明顯需要提供新的迭代器。 首先看一下代碼看的實現方式：
val ints = sequence {
repeat(100) {
yield(it)
}
}
其中sequence的調用邏輯如下：
public fun <T> sequence(@BuilderInference block: suspend SequenceScope<T>.() -> Unit): Sequence<T> = Sequence { iterator(block) }
public fun <T> iterator(@BuilderInference block: suspend SequenceScope<T>.() -> Unit): Iterator<T> {
//創建迭代器
val iterator = SequenceBuilderIterator<T>()
iterator.nextStep = block.createCoroutineUnintercepted(receiver = iterator, completion = iterator)
return iterator
}
public inline fun <T> Sequence(crossinline iterator: () -> Iterator<T>): Sequence<T> = object : Sequence<T> {
override fun iterator(): Iterator<T> = iterator()
}
可以發現：該方法和asSequence一樣最終也是通過匿名內部類的方式創建了一個Sequence。不過區別在于，該方法需要創建一個新的迭代器，也就是SequenceBuilderIterator 。同樣以MySequence為例，它的創建流程等同于一下代碼：
fun mian(){
create<Int> { myblock() }
}
suspend fun SequenceScope<Int>.myblock(){
repeat(100) {
yield(it)
}
}
fun <Int> create(block: suspend SequenceScope<Int>.() -> Unit):Sequence<Int>{
val iterator = SequenceBuilderIterator<Int>()
iterator.nextStep = block.createCoroutineUnintercepted(receiver = iterator, completion = iterator)
return MySequence(iterator)
}
當然，這是不可能實現的，因為SequenceBuilderIterator是被private修飾了，我們是無法直接訪問的。這里強制寫出來演示一下它的流程。
最后看一下通過generateSequence方法創建序列的源碼，一共有三個：
public fun <T : Any> generateSequence(seedFunction: () -> T?, nextFunction: (T) -> T?): Sequence<T> =
GeneratorSequence(seedFunction, nextFunction)
public fun <T : Any> generateSequence(seed: T?, nextFunction: (T) -> T?): Sequence<T> =
if (seed == null)
EmptySequence
else
GeneratorSequence({ seed }, nextFunction)
public fun <T : Any> generateSequence(nextFunction: () -> T?): Sequence<T> {
return GeneratorSequence(nextFunction, { nextFunction() }).constrainOnce()
}
最終都是創建了GeneratorSequence的一個實例并返回，而GeneratorSequence實現了Sequence接口并重寫了iterator()方法：
private class GeneratorSequence<T : Any>(private val getInitialValue: () -> T?, private val getNextValue: (T) -> T?) : Sequence<T> {
override fun iterator(): Iterator<T> = object : Iterator<T> {
var nextItem: T? = null
var nextState: Int = -2 // -2 for initial unknown, -1 for next unknown, 0 for done, 1 for continue
private fun calcNext() {
nextItem = if (nextState == -2) getInitialValue() else getNextValue(nextItem!!)
nextState = if (nextItem == null) 0 else 1
}
override fun next(): T {
if (nextState < 0)
calcNext()
if (nextState == 0)
throw NoSuchElementException()
val result = nextItem as T
// Do not clean nextItem (to avoid keeping reference on yielded instance) -- need to keep state for getNextValue
nextState = -1
return result
}
override fun hasNext(): Boolean {
if (nextState < 0)
calcNext()
return nextState == 1
}
}
}
總結一下Sequence的創建大致可以分為三類：
- 使用List自帶的迭代器通過匿名的方式創建Sequence實例，
sequenceOf("a","b","c","d","e")和listOf("a","b","c","d","e").asSequence()就是這種方式； - 創建新的
SequenceBuilderIterator迭代器，并通過匿名的方式創建Sequence實例。例如使用代碼塊的創建方式。 - 創建
GeneratorSequence，通過重寫iterator()方法，使用匿名的方式創建Iterator。GeneratorSequence方法就是采用的這種方式。
看完創建方式，也沒什么奇特的，就是一個提供迭代器的普通類。還是看不出是如何惰性執行操作的。接下來就分析一下惰性操作的原理。
序列的惰性原理
以最常用的map操作符為例：普通的集合操作源碼如下：
public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
//出啊年一個新的ArrayList，并調用mapTo方法
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.map被調用后，便會立即創建新的集合，然后遍歷老數據并進行變換操作。最后返回一個新的數據。這印證了上面提到的普通集合的操作時按照步驟且會立刻執行的理論。
接下來看一下序列的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> {
//注釋一：TransformingSequence的iterator持有上一個序列的迭代器
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)
}
}
代碼并不復雜，它接收用戶提供的變換函數和序列，然后創建了一個TransformingSequence并返回。TransformingSequence本身和上文中提到的序列沒什么區別，唯一的區別在于它的迭代器：在通過next依次取數據的時候，并不是直接返回元素。而是先調用調用者提供的函數進行變換。返回變換后的數據——這也沒什么新鮮的，和普通集合的map操作符和RxJava的Map都是同樣的原理。
但是，這里卻又有點不一樣。操作符里沒有任何開啟迭代的代碼，它只是對序列以及迭代進行了嵌套處理，并不會開啟迭代.如果用戶不手動調用（后者間接調用）迭代器的next函數，序列就不會被執行——這就是惰性執行的機制的原理所在。
而且，由于操作符返回的是一個Sequence類型的值，當你重復不斷調用map時，例如下面的代碼：
(0..10).asSequence().map{add(it)}.map{add(it)}.map{add(it)}.toList()
//等同于
val sequence1 = (0..10).asSequence()
val sequence2 = sequence1.map { it+1 }
val sequence3 = sequence2.map { it+1 }
sequence3.toList()
最終，序列sequence3的結構持有如下：sequence3-> sequence2 -> sequence1。而它們都有各自的迭代器。迭代器里都重寫了各自的變換邏輯:
override fun next(): R {
return transformer(iterator.next())
}
//由于這里都是執行的+1操作，所以變換邏輯transformer可以認為等同于如下操作:
override fun next(): R {
return iterator.next()+1
}
而當我們通過sequence3.toList執行代碼時，它的流程如下：
public fun <T> Sequence<T>.toList(): List<T> {
return this.toMutableList().optimizeReadOnlyList()
}
public fun <T> Sequence<T>.toMutableList(): MutableList<T> {
//末端操作符，此處才會開始創建新的集合
return toCollection(ArrayList<T>())
}
public fun <T, C : MutableCollection<in T>> Sequence<T>.toCollection(destination: C): C {
//執行迭代器next操作
//當調用（末端操作符）走到這里時，便會和普通結合的操作符一樣
//此時為新創建的集合賦值
for (item in this) {
destination.add(item)
}
return destination
}
經過幾次擴展函數調用，最終在toCollection里開始執行迭代(Iterator的典型的操作)，也就是獲取了sequence3的iterator實例，并不斷通過next取出數據。而在上文中的TransformingSequence源碼里可以看到，TransformingSequence會持有上一個迭代器的實例（代碼注釋一）。
并且在迭代開始后，在進行transformer操作（也就是執行+1操作）前，會調用上一個迭代器的next方法進行迭代（代碼注釋二）。這樣不斷的迭代，最終，最終會調用到sequence1的next方法。再結合上文中的序列創建里的分析——sequence1里所持有的迭代器就是就是原始數據里的迭代器。
那么當最終執行toList方法時，它會循環sequence3.iterator方法。而在每次循環內，都會首先執行sequence3所持有的sequence2.iterator的next方法。sequence2依次類推執行到sequence1的sequence1.iterator`方法，最終執行到我們原始數組的迭代器next方法：
整個流程如下：
原理就是這么簡單：中間操作符通過序列嵌套，實現對迭代器iterator的嵌套。這樣在進行迭代的時候，會依次調用各個iterator迭代器直到調用到原始集合數據里的迭代器開始并返回元素。而當元素返回時，會依次執行各個迭代器持有變換操作方法實現對數據的變換。
而其他操作符，也是遵循這個基本的規則。無非就是增加一些其他的操作。
總結
- 序列通過中間操作符對迭代器進行嵌套和復寫，以此實現按元素操作執行變換；
- 中間操作符只負責根據需求創建并嵌套迭代器，并不負責開啟迭代器。以此實現惰性操作且不產生臨時集合；
- 末端操作符負責開啟迭代，按照嵌套順序執行迭代操作。依次獲取操作后的數據，并且會創建新的集合用來存儲最終數據；
- 序列不是萬能的，因為要引入新的對象。在帶來惰性和順序執行的優勢時，這些對象必然會帶來性能開銷。所以要依需求在集合和序列之間進行選擇，使用合適的方式進行迭代。
原文鏈接：https://juejin.cn/post/7078587415748673543
相關推薦
- 2023-07-31 TypeError:cannot read property ‘getAttribute‘ of
- 2022-04-21 C語言中的柔性數組你真的了解嗎_C 語言
- 2022-07-02 jquery實現無縫輪播圖_jquery
- 2022-08-20 python深入講解魔術方法_python
- 2022-08-28 關于CLion配置visual?studio(msvc)和JOM多核編譯的問題_C 語言
- 2022-04-09 Python實現簡易的限流器介紹_python
- 2021-12-09 Linux內存管理和尋址詳細介紹_Linux
- 2022-09-30 C++?多態虛函數的底層原理深入理解_C 語言
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速