第Kotlin中的惰性操作容器Sequence序列使用原理詳解目錄Sequence序列執(zhí)行的順序只做最少的操作序列可以是無(wú)限的序列不會(huì)在每個(gè)步驟創(chuàng)建集合Sequence的基本使用序列的創(chuàng)建序列的操作Sequence源碼分析Sequence是什么？序列的創(chuàng)建方式分析序列的惰性原理總結(jié)

Sequence序列

Sequence是Kotlin標(biāo)準(zhǔn)庫(kù)提供的一種容器類型。它和Iterable一樣具備對(duì)集合進(jìn)行多步驟操作能力，但是卻是采用了一種完全不同于Iterable的實(shí)現(xiàn)方式：

valmap=(0..3).filter{

println("filter:$it")

it%2==0

}.map{

println("map:$it")

it+1

println(map)

上面的代碼用來(lái)演示Iterable進(jìn)行連續(xù)操作的情況。它的輸出如下：

filter:0

filter:1

filter:2

filter:3

map:0

map:2

[1,3]

像map和filter這些鏈?zhǔn)郊虾瘮?shù)它們都會(huì)立即執(zhí)行并創(chuàng)建中間臨時(shí)集用來(lái)保存數(shù)據(jù)。當(dāng)原始數(shù)據(jù)不多時(shí)，這并不會(huì)有什么影響。但是，當(dāng)原始數(shù)據(jù)量非常大的時(shí)候。這就會(huì)變的非常低效。而此時(shí)，就可以借助Sequence提高效率。

valsequence=(0..3).asSequence().filter{

println("filter:$it")

it%2==0

}.map{

println("map:$it")

it+1

println("準(zhǔn)備開始執(zhí)行")

println(sequence.toList())

上面的代碼執(zhí)行結(jié)果如下：

準(zhǔn)備開始執(zhí)行

filter:0

map:0

filter:1

filter:2

map:2

filter:3

[1,3]

對(duì)比Iterable和Sequence：

Iterable是即時(shí)的、Sequence是惰性的：前者會(huì)要求盡早的計(jì)算結(jié)果，因此在多步驟處理鏈的每一環(huán)都會(huì)有中間產(chǎn)物也就是新的集合產(chǎn)生；后者會(huì)盡可能的延遲計(jì)算結(jié)果，Sequence處理的中間函數(shù)不進(jìn)行任何計(jì)算。相反，他們返回一個(gè)新Sequence的，用新的操作裝飾前一個(gè)，所有的這些計(jì)算都只是在類似toList的終端操作期間進(jìn)行。

區(qū)分中間操作符和末端操作符的方式也很簡(jiǎn)單：如果操作符返回的是一個(gè)Sequence類型的數(shù)據(jù)，它就是中間操作符。

在操作的執(zhí)行方式上也有所不同：Iterable每次都是在整個(gè)集合執(zhí)行完操作后再進(jìn)行下一步操作采用第一個(gè)操作并將其應(yīng)用于整個(gè)集合，然后移動(dòng)到下一個(gè)操作，官方將其稱呼為急切式或者按步驟執(zhí)行（Eager/step-by-step）；**而Sequence則是逐個(gè)對(duì)每個(gè)元素執(zhí)行所有操作。是一種惰性順序取第一個(gè)元素并應(yīng)用所有操作，然后取下一個(gè)元素，依此類推。**官方將其稱呼為惰性式或者按元素執(zhí)行（Lazy/element-by-element)

序列的惰性會(huì)帶來(lái)一下幾個(gè)優(yōu)點(diǎn)：

它們的操作按照元素的自然順序進(jìn)行；只做最少的操作；元素可以是無(wú)限多個(gè)；不需要在每一步都創(chuàng)建集合

Sequence可避免生成中間步驟的結(jié)果，從而提高了整個(gè)集合處理鏈的性能。但是，惰性性質(zhì)也會(huì)帶來(lái)一些運(yùn)行開銷。所以在使用時(shí)要權(quán)衡惰性開銷和中間步驟開銷，在Sequence和Iterable中選擇更加合適的實(shí)現(xiàn)方式。

執(zhí)行的順序

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的執(zhí)行時(shí)按照元素進(jìn)行的，依次對(duì)元素執(zhí)行所有的操作，對(duì)一個(gè)元素而言，所有操作時(shí)依次全部執(zhí)行的。而普通集合操作則是以操作步驟進(jìn)行的，當(dāng)所有的元素執(zhí)行完當(dāng)前操作后才會(huì)進(jìn)入下一個(gè)操作。

只做最少的操作

試想一下我們有一千萬(wàn)個(gè)數(shù)字，我們要經(jīng)過(guò)幾次變換取出20個(gè)，使用下面的代碼對(duì)比一下序列和不同集合操作的性能：

funmain(){

valfFlow=FFlow()

fFlow.demoList()

fFlow.demoSequence()

fundemoSequence(){

valcurrentTimeMillis=System.currentTimeMillis()

vallist=

(0..10000000).asSequence().map{it*2}.map{it-1}.take(20).toList()

println("demoSequence:${System.currentTimeMillis()-currentTimeMillis}：$list")

fundemoList(){

valcurrentTimeMillis=System.currentTimeMillis()

vallist=

(0..10000000).map{it*2}.map{it-1}.take(20).toList()

println("demoList:${System.currentTimeMillis()-currentTimeMillis}：$list")

輸出的結(jié)果如下：

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]

這就是只執(zhí)行最少操作的意思，序列按照元素順序執(zhí)行，當(dāng)取夠29個(gè)元素之后便會(huì)立即停止計(jì)算。而不同的集合則不同，沒(méi)有中間操作的概念。它的每次操作都會(huì)對(duì)整個(gè)數(shù)組中的所有元素執(zhí)行完才會(huì)進(jìn)行下一個(gè)也就是前兩個(gè)map都要執(zhí)行一千萬(wàn)次。

序列可以是無(wú)限的

看如下代碼：

varlist=emptyArrayInt()

vari=0

while(true){

list[i]=i++

list.take(10)

很明顯，這段代碼是沒(méi)法正常運(yùn)行的，因?yàn)檫@里有一個(gè)死循環(huán)。我們也無(wú)法創(chuàng)建一個(gè)無(wú)限長(zhǎng)度的集合。但是：因?yàn)樾蛄惺桨床襟E依照需求進(jìn)行處理的，所喲我們可以創(chuàng)建無(wú)限序列：

valnoEnd=sequence{

vari=1

while(true){

yield(i)

i*=2

noEnd.take(4).toList()

//輸出:[1,2,4,8]

但是一定要注意，我們雖然可以這么寫，但是務(wù)必不能真的讓while一直循環(huán)。我們不能直接使用toList。必須提供一個(gè)能結(jié)束循環(huán)的操作符，也就是不能取出所有元素（無(wú)限個(gè)）要么使用類似take的操作來(lái)限制它們的數(shù)量，要么使用不需要所有元素的終端操作，例如first,find,any,all,indexOf等。

序列不會(huì)在每個(gè)步驟創(chuàng)建集合

普通的集合會(huì)在每次變換之后都會(huì)創(chuàng)建新的集合取存儲(chǔ)所有變換后的元素。而每次創(chuàng)建集合和填入數(shù)據(jù)都會(huì)帶來(lái)不小的性能開銷。尤其是當(dāng)我們處理大量或大量的集合時(shí)，性能問(wèn)題會(huì)愈發(fā)凸顯。而序列的按元素操作，則不會(huì)有這個(gè)問(wèn)題。除非手動(dòng)調(diào)用了終端操作符，否則不會(huì)生成新的集合。

Sequence的基本使用

Sequence序列的使用和普通的Iterable極其相似，實(shí)際上其內(nèi)部也還是借助Iterable實(shí)現(xiàn)的。在研究它的內(nèi)部實(shí)現(xiàn)原理之前，想從Sequence的創(chuàng)建和基本的序列操作來(lái)演示Sequence的基本用法。

序列的創(chuàng)建

創(chuàng)建Sequence的方式大概可以分為。分別是由元素創(chuàng)建、通過(guò)Iterable、借助函數(shù)以及由代碼塊創(chuàng)建。

由元素創(chuàng)建：通過(guò)調(diào)用頂級(jí)函數(shù)sequenceOf實(shí)現(xiàn)：

valints=sequenceOf(1,2,3,4,5,6,7)

valstrings=sequenceOf("a","b","c","d","e")

通過(guò)Iterable轉(zhuǎn)化：借助Iterable的擴(kuò)展函數(shù)asSequence實(shí)現(xiàn)：

valints=listOf(1,2,3,4,5,6,7).asSequence()

valstrings=listOf("a","b","c","d","e").asSequence()

通過(guò)generateSequence實(shí)現(xiàn)：該方法有三個(gè)：

generateSequence(seedFunction:()-T,nextFunction:(T)-T):SequenceT

generateSequence(seed:T,nextFunction:(T)-T):SequenceT

generateSequence(nextFunction:()-T):SequenceT

最終都是通過(guò)GeneratorSequence實(shí)現(xiàn)的，這里先不進(jìn)行源碼分析。只討論使用方式：

其中三個(gè)函數(shù)都有的形參nextFunction可以理解為元素生成器，序列里的元素都通過(guò)調(diào)用該函數(shù)生成，當(dāng)它返回為null是，序列停止生成（所以，nextFunction必須要在某個(gè)情況下返回null，否則會(huì)因?yàn)樾蛄性厥菬o(wú)限多個(gè)觸發(fā)java.lang.OutOfMemoryError:Javaheapspace異常）。而另外兩個(gè)的seedFunction和seed形參都是為了確定數(shù)據(jù)初始值的。區(qū)別在于一個(gè)直接指明，一個(gè)通過(guò)調(diào)用函數(shù)獲取。

分別用這三個(gè)函數(shù)生成0~100的序列，代碼如下：

valgenerateSequenceOne=generateSequence{

if(i100){

}else{

null

valgenerateSequenceTwo=generateSequence(0){

if(it100){

it+1//此處的it是上一個(gè)元素

}else{

null

valgenerateSequenceThree=generateSequence({0}){

if(it100){

it+1//此處的it是上一個(gè)元素

}else{

null

由代碼塊生成：借助sequence(block:suspendSequenceScope.()-Unit)函數(shù)。該函數(shù)接受一個(gè)掛起函數(shù)，該函數(shù)會(huì)接受一個(gè)SequenceScope實(shí)例，這個(gè)實(shí)例無(wú)需我們創(chuàng)建（后面源碼分析會(huì)講到）。SequenceScope提供了yield和yieldAll方法復(fù)雜返回序列元素給調(diào)用者，并暫停序列的執(zhí)行，直到使用者請(qǐng)求下一個(gè)元素。

用該函數(shù)生成0~100的序列，代碼如下：

valints=sequence{

repeat(100){

yield(it)

序列的操作

對(duì)序列的操作可以分為中間操作和末端操作兩種。它們只要有一下另種區(qū)別：

中間操作返回惰性生成的一個(gè)新的序列，而末端序列則為其他普通的數(shù)據(jù)類型；中間操作不會(huì)立刻執(zhí)行代碼，僅當(dāng)執(zhí)行了末端操作序列才會(huì)開始執(zhí)行。

常見(jiàn)的中間操作包括：map、fliter、first、last、take等；它們會(huì)序列提供數(shù)據(jù)變化過(guò)濾等增強(qiáng)功能基本上和kotlin提供的集合操作符有著相同的功能。

常見(jiàn)的末端操作有：toList、toMutableList、sum、count等。它們?cè)谔峁┬蛄胁僮鞴δ艿耐瑫r(shí)，還會(huì)觸發(fā)序列的運(yùn)行。

Sequence源碼分析

上文對(duì)序列做了簡(jiǎn)單的入門介紹。接下來(lái)深入源碼去了解一下Sequence的實(shí)現(xiàn)方式。

Sequence是什么？

Kotlin對(duì)的定義Sequence很簡(jiǎn)單：

publicinterfaceSequenceoutT{

publicoperatorfuniterator():IteratorT

就是一個(gè)接口，定義了一個(gè)返回Iterator的方法。接口本身只定義了Sequence具有返回一個(gè)迭代器的能力。具體的功能實(shí)現(xiàn)還是靠它的實(shí)現(xiàn)類完成。

可以概括一些：序列就是一個(gè)具備提供了迭代器能力的類。

序列的創(chuàng)建方式分析

結(jié)合上文中提到的序列的四種創(chuàng)建方式，我們依次分析一下它的創(chuàng)建流程。

我們首先以比較常用的通過(guò)Iterable轉(zhuǎn)化獲取序列，它需要借助asSequence方法分析一下，使用listOf(a,b,c,d,e).asSequence()生成一個(gè)序列。調(diào)用鏈如下：

publicfunTIterableT.asSequence():SequenceT{

returnSequence{this.iterator()}

publicinlinefunTSequence(crossinlineiterator:()-IteratorT):SequenceT=object:SequenceT{

overridefuniterator():IteratorT=iterator()

流程很簡(jiǎn)單，一個(gè)擴(kuò)展函數(shù)加一個(gè)內(nèi)聯(lián)函數(shù)。最終通過(guò)匿名內(nèi)部類的方式創(chuàng)建一個(gè)Sequence并返回。代碼很好理解，實(shí)際上它的實(shí)現(xiàn)邏輯等同于下面的代碼：

valsequence=MySequence(listOf("a","b","c","d","e").iterator())

classMySequenceT(privatevaliterator:IteratorT):SequenceT{

overridefuniterator():IteratorT{

returniterator

接著看一下通過(guò)調(diào)用頂級(jí)函數(shù)sequenceOf實(shí)現(xiàn)，以sequenceOf(a,b,c,d,e)為例，它的調(diào)用邏輯如下：

publicfunTsequenceOf(varargelements:T):SequenceT=if(elements.isEmpty())emptySequence()elseelements.asSequence()

可以看到依舊是借助asSequence實(shí)現(xiàn)的。

接下來(lái)看一下代碼塊和generateSequence的實(shí)現(xiàn)方式，這兩個(gè)方式會(huì)比較復(fù)雜一點(diǎn)，畢竟前面兩個(gè)都是借助List進(jìn)行轉(zhuǎn)換，而List本身就能提供迭代器Iterator。后面兩個(gè)明顯需要提供新的迭代器。首先看一下代碼看的實(shí)現(xiàn)方式：

valints=sequence{

repeat(100){

yield(it)

其中sequence的調(diào)用邏輯如下：

publicfunTsequence(@BuilderInferenceblock:suspendSequenceScopeT.()-Unit):SequenceT=Sequence{iterator(block)}

publicfunTiterator(@BuilderInferenceblock:suspendSequenceScopeT.()-Unit):IteratorT{

//創(chuàng)建迭代器

valiterator=SequenceBuilderIteratorT()

iterator.nextStep=block.createCoroutineUnintercepted(receiver=iterator,completion=iterator)

returniterator

publicinlinefunTSequence(crossinlineiterator:()-IteratorT):SequenceT=object:SequenceT{

overridefuniterator():IteratorT=iterator()

可以發(fā)現(xiàn)：該方法和asSequence一樣最終也是通過(guò)匿名內(nèi)部類的方式創(chuàng)建了一個(gè)Sequence。不過(guò)區(qū)別在于，該方法需要?jiǎng)?chuàng)建一個(gè)新的迭代器，也就是SequenceBuilderIterator。同樣以MySequence為例，它的創(chuàng)建流程等同于一下代碼：

funmian(){

createInt{myblock()}

suspendfunSequenceScopeInt.myblock(){

repeat(100){

yield(it)

funIntcreate(block:suspendSequenceScopeInt.()-Unit):SequenceInt{

valiterator=SequenceBuilderIteratorInt()

iterator.nextStep=block.createCoroutineUnintercepted(receiver=iterator,completion=iterator)

returnMySequence(iterator)

當(dāng)然，這是不可能實(shí)現(xiàn)的，因?yàn)镾equenceBuilderIterator是被private修飾了，我們是無(wú)法直接訪問(wèn)的。這里強(qiáng)制寫出來(lái)演示一下它的流程。

最后看一下通過(guò)generateSequence方法創(chuàng)建序列的源碼，一共有三個(gè)：

publicfunT:AnygenerateSequence(seedFunction:()-T,nextFunction:(T)-T):SequenceT=

GeneratorSequence(seedFunction,nextFunction)

publicfunT:AnygenerateSequence(seed:T,nextFunction:(T)-T):SequenceT=

if(seed==null)

EmptySequence

else

GeneratorSequence({seed},nextFunction)

publicfunT:AnygenerateSequence(nextFunction:()-T):SequenceT{

returnGeneratorSequence(nextFunction,{nextFunction()}).constrainOnce()

最終都是創(chuàng)建了GeneratorSequence的一個(gè)實(shí)例并返回，而GeneratorSequence實(shí)現(xiàn)了Sequence接口并重寫了iterator()方法：

privateclassGeneratorSequenceT:Any(privatevalgetInitialValue:()-T,privatevalgetNextValue:(T)-T):SequenceT{

overridefuniterator():IteratorT=object:IteratorT{

varnextItem:T=null

varnextState:Int=-2//-2forinitialunknown,-1fornextunknown,0fordone,1forcontinue

privatefuncalcNext(){

nextItem=if(nextState==-2)getInitialValue()elsegetNextValue(nextItem!!)

nextState=if(nextItem==null)0else1

overridefunnext():T{

if(nextState0)

calcNext()

if(nextState==0)

throwNoSuchElementException()

valresult=nextItemasT

//DonotcleannextItem(toavoidkeepingreferenceonyieldedinstance)--needtokeepstateforgetNextValue

nextState=-1

returnresult

overridefunhasNext():Boolean{

if(nextState0)

calcNext()

returnnextState==1

總結(jié)一下Sequence的創(chuàng)建大致可以分為三類：

使用List自帶的迭代器通過(guò)匿名的方式創(chuàng)建Sequence實(shí)例，sequenceOf(a,b,c,d,e)和listOf(a,b,c,d,e).asSequence()就是這種方式；創(chuàng)建新的SequenceBuilderIterator迭代器，并通過(guò)匿名的方式創(chuàng)建Sequence實(shí)例。例如使用代碼塊的創(chuàng)建方式。創(chuàng)建GeneratorSequence，通過(guò)重寫iterator()方法，使用匿名的方式創(chuàng)建Iterator。GeneratorSequence方法就是采用的這種方式。

看完創(chuàng)建方式，也沒(méi)什么奇特的，就是一個(gè)提供迭代器的普通類。還是看不出是如何惰性執(zhí)行操作的。接下來(lái)就分析一下惰性操作的原理。

序列的惰性原理

以最常用的map操作符為例：普通的集合操作源碼如下：

publicinlinefunT,RIterableT.map(transform:(T)-R):ListR{

//出啊年一個(gè)新的ArrayList，并調(diào)用mapTo方法

returnmapTo(ArrayListR(collectionSizeOrDefault(10)),transform)

publicinlinefunT,R,C:MutableCollectioninRIterableT.mapTo(destination:C,transform:(T)-R):C{

//遍歷原始的集合，進(jìn)行變換操作，然后將變換后的數(shù)據(jù)依次加入到新創(chuàng)建的集合

for(iteminthis)

destination.add(transform(item))

//返回新集合

returndestination

可以看到：當(dāng)List.map被調(diào)用后，便會(huì)立即創(chuàng)建新的集合，然后遍歷老數(shù)據(jù)并進(jìn)行變換操作。最后返回一個(gè)新的數(shù)據(jù)。這印證了上面提到的普通集合的操作時(shí)按照步驟且會(huì)立刻執(zhí)行的理論。

接下來(lái)看一下序列的map方法，它的源碼如下：

publicfunT,RSequenceT.map(transform:(T)-R):SequenceR{

returnTransformingSequence(this,transform)

internalclassTransformingSequenceT,R

constructor(privatevalsequence:SequenceT,privatevaltransformer:(T)-R):SequenceR{

overridefuniterator():IteratorR=object:IteratorR{

//注釋一：TransformingSequence的iterator持有上一個(gè)序列的迭代器

valiterator=sequence.iterator()

overridefunnext():R{

//注釋二：在開始執(zhí)行迭代時(shí)，向上調(diào)用前一個(gè)序列的迭代器。

returntransformer(iterator.next())

overridefunhasNext():Boolean{

returniterator.hasNext()

internalfunEflatten(iterator:(R)-IteratorE):SequenceE{

returnFlatteningSequenceT,R,E(sequence,transformer,iterator)

代碼并不復(fù)雜，它接收用戶提供的變換函數(shù)和序列，然后創(chuàng)建了一個(gè)TransformingSequence并返回。TransformingSequence本身和上文中提到的序列沒(méi)什么區(qū)別，唯一的區(qū)別在于它的迭代器：在通過(guò)next依次取數(shù)據(jù)的時(shí)候，并不是直接返回元素。而是先調(diào)用調(diào)用者提供的函數(shù)進(jìn)行變換。返回變換后的數(shù)據(jù)這也沒(méi)什么新鮮的，和普通集合的map操作符和RxJava的Map都是同樣的原理。

但是，這里卻又有點(diǎn)不一樣。操作符里沒(méi)有任何開啟迭代的代碼，它只是對(duì)序列以及迭代進(jìn)行了嵌套處理，并不會(huì)開啟迭代.如果用戶不手動(dòng)調(diào)用（后者間接調(diào)用）迭代器的next函數(shù)，序列就不會(huì)被執(zhí)行這就是惰性執(zhí)行的機(jī)制的原理所在。

而且，由于操作符返回的是一個(gè)Sequence類型的值，當(dāng)你重復(fù)不斷調(diào)用map時(shí)，例如下面的代碼：

(0..10).asSequence().map{add(it)}.map{add(it)}.map{add(it)}.toList()

//等同于

valsequence1=(0..10).asSequence()

valsequence2=sequence1.map{it+1}

valsequence3=sequence2.map{it+1}

sequence3.toList()

最終，序列sequence3的結(jié)構(gòu)持有如下：sequence3-sequence2-sequence1。而它們都有各自的迭代器。迭代器里都重寫了各自的變換邏輯:

overridefunnext():R{

returntransformer(iterator.next())

//由于這里都是執(zhí)行的+1操作，所以變換邏輯transformer可以認(rèn)為等同于如下操作:

overridefunnext():R{

returniterator.next()+1

而當(dāng)我們通過(guò)sequence3.toList執(zhí)行代碼時(shí)，它的流程如下：

publicfunTSequenceT.toList():ListT{

returnthis.toMutableList().optimizeReadOnlyList(