Sequences
本文收錄于: https://github.com/mengdd/KotlinTutorials
Sequences是用來干什么的
Kotlin標準庫還提供了另一種容器類型: sequences.
Sequence接口和Iterable接口很像, 都是提供了遍歷操作.
不同點在于, 對于集合的多步操作, Sequences提供了不同的做法.
- 多步處理時, 對于
Iterable, 執(zhí)行是急切的(eagerly), 每一個步驟都完成和返回一個中間集合(collection), 后續(xù)的操作再在這個集合上繼續(xù)執(zhí)行. - sequences的多步處理是延遲的(lazily), 只有在整個鏈條的結(jié)果被請求的時候才會真正執(zhí)行每一步的計算.
操作符的執(zhí)行順序同樣也是不同的:
-
Iterable會對集合的所有元素先完成第一個操作, 然后整體再往下走, 對所有元素進行下一個操作. -
Sequence則按照元素, 每個元素完成一系列操作, 接著是下一個元素.
我想了一個比喻: 雙層循環(huán)嵌套, Iterable的外層遍歷操作符, 內(nèi)層遍歷元素; 而Sequence的外層遍歷元素, 內(nèi)層遍歷操作符.
一段為了輔助理解操作順序的偽代碼:
// Iterable
for (operation in operators) {
for (element in collection) {
//...
}
}
// Sequence
for (element in collection) {
for (operation in operators) {
//...
}
}
舉例說明
下面通過實際的例子來說明.
例子背景: 有一堆書, 書的類型是:
data class Book(val name: String, val author: String)
其中包含書名和作者名.
現(xiàn)在我們想要在這堆書里, 篩選出某些作者的書, 符合條件的三本就可以了, 并輸出書名.
用一般collection的實現(xiàn):
fun findBookNamesOfAuthorsUsingCollection(authors: Set<String>): List<String> {
return books
.filter {
println("filter: $it")
it.author in authors
}
.map {
println("map: $it")
it.name
}
.take(3)
}
其中books是一個List.
上面進行的操作: 從書里先根據(jù)作者過濾, 然后map變換到書名, 最后取三個書名返回.
但是需要注意的是:
- 每個操作符都會創(chuàng)建一個新的數(shù)組并輸出, 作為下一級操作的輸入.
- 如果書的數(shù)量比較多, 最后卻只取了3本, 那么前兩步過濾和映射操作會造成浪費.
這一點從console輸出結(jié)果上就可以看出來:
filter: Book(name=Brown Bear, Brown Bear, What Do You See?, author=Eric Carle)
filter: Book(name=1, 2, 3 to the Zoo, author=Eric Carle)
filter: Book(name=The Very Hungry Caterpillar, author=Eric Carle)
filter: Book(name=Pancakes, Pancakes!, author=Eric Carle)
filter: Book(name=The Tiny Seed, author=Eric Carle)
filter: Book(name=Do You Want to Be My Friend?, author=Eric Carle)
filter: Book(name=The Mixed-Up Chameleon, author=Eric Carle)
filter: Book(name=The Very Busy Spider, author=Eric Carle)
filter: Book(name=Papa, Please Get the Moon for Me, author=Eric Carle)
filter: Book(name=Today Is Monday, author=Eric Carle)
filter: Book(name=From Head to Toe, author=Eric Carle)
filter: Book(name=Does A Kangaroo Have A Mother, Too?, author=Eric Carle)
filter: Book(name=10 Little Rubber Ducks, author=Eric Carle)
filter: Book(name=Where Is Baby's Belly Button?, author=Karen Katz)
filter: Book(name=No Biting!, author=Karen Katz)
filter: Book(name=I Can Share, author=Karen Katz)
filter: Book(name=My Car, author=Byron Barton)
filter: Book(name=My Bus, author=Byron Barton)
filter: Book(name=Dear Zoo, author=Rod Campbell)
filter: Book(name=Dr. Seuss's ABC, author=Dr. Seuss)
filter: Book(name=Fox in Socks, author=Dr. Seuss)
filter: Book(name=The Cat in the Hat, author=Dr. Seuss)
filter: Book(name=Hop on Pop, author=Dr. Seuss)
map: Book(name=Brown Bear, Brown Bear, What Do You See?, author=Eric Carle)
map: Book(name=1, 2, 3 to the Zoo, author=Eric Carle)
map: Book(name=The Very Hungry Caterpillar, author=Eric Carle)
map: Book(name=Pancakes, Pancakes!, author=Eric Carle)
map: Book(name=The Tiny Seed, author=Eric Carle)
map: Book(name=Do You Want to Be My Friend?, author=Eric Carle)
map: Book(name=The Mixed-Up Chameleon, author=Eric Carle)
map: Book(name=The Very Busy Spider, author=Eric Carle)
map: Book(name=Papa, Please Get the Moon for Me, author=Eric Carle)
map: Book(name=Today Is Monday, author=Eric Carle)
map: Book(name=From Head to Toe, author=Eric Carle)
map: Book(name=Does A Kangaroo Have A Mother, Too?, author=Eric Carle)
map: Book(name=10 Little Rubber Ducks, author=Eric Carle)
map: Book(name=Where Is Baby's Belly Button?, author=Karen Katz)
map: Book(name=No Biting!, author=Karen Katz)
map: Book(name=I Can Share, author=Karen Katz)
如果換做sequence實現(xiàn):
fun findBookNamesOfAuthorsUsingSequence(authors: Set<String>): List<String> {
return books
.asSequence()
.filter {
println("filter: $it")
it.author in authors
}
.map {
println("map: $it")
it.name
}
.take(3)
.toList()
}
相比上一段代碼, 這里只加了asSequence()和toList()兩個操作符.
看console輸出:
filter: Book(name=Brown Bear, Brown Bear, What Do You See?, author=Eric Carle)
map: Book(name=Brown Bear, Brown Bear, What Do You See?, author=Eric Carle)
filter: Book(name=1, 2, 3 to the Zoo, author=Eric Carle)
map: Book(name=1, 2, 3 to the Zoo, author=Eric Carle)
filter: Book(name=The Very Hungry Caterpillar, author=Eric Carle)
map: Book(name=The Very Hungry Caterpillar, author=Eric Carle)
發(fā)現(xiàn)找到想要的3本書之后, 對后續(xù)元素就不再進行處理了.
而且省略了中間步驟中的集合建立.
創(chuàng)建和操作
創(chuàng)建Sequence除了常規(guī)能想到的列舉元素, 從list或set轉(zhuǎn)換, 還有用方法生成和塊生成兩種方法.
無狀態(tài)和有狀態(tài)
序列操作可以分為兩種:
- 無狀態(tài)的.
- 有狀態(tài)的.
大多數(shù)操作都是無狀態(tài)的, 有狀態(tài)的操作有:
- 排序操作.
- 區(qū)分操作.
intermediate和terminal操作
如果sequence的操作返回另一個sequence, 那么它是中間的(intermediate), 否則就是終結(jié)的(terminal), 比如 toList()或sum(). 只有在這種終結(jié)操作之后, 序列的元素才可以被獲取.
如果沒有terminal, 任何之前的intermediate操作都不會被執(zhí)行.
舉例:
sequenceOf("Hello", "Kotlin", "World")
.onEach { println(it) }
什么都打印不出來.
而加上toList() (terminal操作)之后:
sequenceOf("Hello", "Kotlin", "World")
.onEach { println(it) }
.toList()
就可以把詞都打印出來.
onEach()是中間操作, 如果想要終結(jié)操作, 用forEach(), 操作會被執(zhí)行.
sequenceOf("Hello", "Kotlin", "World")
.forEach { println(it) }
這是跟內(nèi)部實現(xiàn)有關(guān), sequence的intermediate操作符并不做實際的計算, 只是把sequence又包裝了一層. (裝飾器模式).
在terminal操作的時候, 所有的計算一起進行.
內(nèi)部實現(xiàn)的具體解釋可以看這篇文章: Inside Sequences: Create Your Own Sequence Operations.
選擇和取舍
使用使用sequence的好處是什么呢? 避免了中間結(jié)果的建立, 改善性能. 而且, 當我們最后的結(jié)果是指定個數(shù)的, 取夠結(jié)果之后就不用再管后面的元素, 節(jié)省了操作.
但是在處理比較小的集合或比較簡單的操作的時候, lazy的方式也有可能帶來問題. 所以究竟用Sequence還是Iterable還是要根據(jù)實際用途和數(shù)據(jù)來選擇的.
影響性能的因素:
- 操作數(shù)量. -> 操作數(shù)量越多, collection需要創(chuàng)建的中間集合越多. ->
sequence優(yōu)先. - 短路操作. 比如
take(),contains(),indexOf(),any(),none(),find(),first(). ->sequence優(yōu)先. - 大小可變的集合. 背景: 數(shù)組擴容.
map()操作時, 因為collection知道數(shù)量, 可以直接設置正確的數(shù)組大小, 所以不存在消耗. 但是sequence不知道元素數(shù)量, 所以toList()先創(chuàng)建一個默認大小的數(shù)組, 然后隨著元素增多, 按需擴容. ->collection優(yōu)先. - 有狀態(tài)的操作, 比如排序, 中間會創(chuàng)建大小可變的集合, 理由同上一條. ->
collection優(yōu)先.
當然終極的方法還是實際測量一下, 才能知道到底有多大區(qū)別. 工具: JMH
除了性能, 還有其他考慮的方面:
- 生成器. sequence沒有size, 可以生成無限長的序列. 在請求的時候生成元素.
- 可用的操作. sequence沒有從后到前的操作, 不支持反轉(zhuǎn), 切片, 集合操作, 獲取單個元素的操作等.
Sequence和Java Stream
Kotlin的sequence和Java 8引入的stream是很像的.
主要的不同點是stream有parallel模式.
Key Takeaways
sequence的關(guān)鍵點:
- 不創(chuàng)建中間集合.
- 單元素進行所有操作, 之后再到下一個元素.
- 中間操作符是lazy的.
參考
- 官方文檔: Sequences
強烈推薦這三篇文章, 里面有個蠟筆工廠的例子很形象, 配圖很棒:
- Kotlin Sequences: An Illustrated Guide: 這篇講基本.
- Inside Sequences: Create Your Own Sequence Operations 這篇講內(nèi)部是怎么實現(xiàn)的.
- When to Use Sequences 這篇講選用時候的考慮因素.
還有這個Effective Kotlin系列中sequence的這篇:
