kotlin修煉指南9-Sequence的祕密

語言: CN / TW / HK

人們經常忽略Iterable和Sequence之間的區別。這是可以理解的,因為即使它們的定義也幾乎是相同的。

``` interface Iterable { operator fun iterator(): Iterator }

interface Sequence { operator fun iterator(): Iterator } ```

你可以說它們之間唯一的正式區別就是名字。儘管Iterable和Sequence有著完全不同的用途(有不同的契約),它們的處理函式幾乎都以不同的方式工作。Sequence是Lazy的,所以Sequence處理的中間函式不做任何計算。相反,它們返回一個新的Sequence,用新的操作來裝飾以前的Sequence。所有這些計算在終端操作(如toList或count)中被處理。而另一方面,Iterable的處理在每一步都會返回一個類似List的集合。

``` public inline fun Iterable.filter( predicate: (T) -> Boolean ): List { return filterTo(ArrayList(), predicate) }

public fun Sequence.filter( predicate: (T) -> Boolean ): Sequence { return FilteringSequence(this, true, predicate) } ```

Sequence過濾器是一箇中間操作,所以它不做任何計算,而是用新的處理步驟來裝飾Sequence。計算是在終端操作中完成的,比如toList。

因此,集合處理操作一旦被使用就會被呼叫。Sequence處理函式直到終端操作(一個返回其他東西而不是Sequence的操作)才會被呼叫。例如,對於Sequence來說,filter是一箇中間操作,所以它不做任何計算,而是用新的處理步驟來裝飾Sequence。計算是在toList這樣的終端操作中完成的。

img

val seq = sequenceOf(1,2,3) val filtered = seq.filter { print("f$it "); it % 2 == 1 } println(filtered) // [email protected] asList = filtered.toList() // f1 f2 f3 println(asList) // [1, 3]val list = listOf(1,2,3) val listFiltered = list .filter { print("f$it "); it % 2 == 1 } // f1 f2 f3 println(listFiltered) // [1, 3]

在Kotlin中,Sequence是Lazy的,這有幾個重要的優點。

  • 它們保持了操作的自然順序

  • 它們只做最少的操作

  • 它們可以是無限的

  • 它們不需要在每個步驟中都建立集合

讓我們來逐一討論這些優點。

Order is important

由於iterable和Sequence處理的實現方式,它們的操作順序是不同的。在Sequence處理中,我們取第一個元素並應用所有的操作,然後我們取下一個元素,以此類推。我們將其稱為逐個元素或Lazy的順序。在可迭代處理中,我們取第一個操作,並將其應用於整個集合,然後轉到下一個操作。他們是一步一步被執行的。

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,

image-20221111175825125

請注意,如果我們不使用任何集合處理函式來實現這些操作,而是使用經典的迴圈和條件,我們就會像在Sequence處理中一樣是逐個元素的順序。

for (e in listOf(1,2,3)) { print("F$e, ") if(e % 2 == 1) { print("M$e, ") val mapped = e * 2 print("E$mapped, ") } } // Prints: F1, M1, E2, F2, F3, M3, E6,

因此,在Sequence處理中使用的逐個元素的順序是比較自然的。它還為低級別的編譯器優化打開了大門--Sequence處理可以被優化為基本的迴圈和條件。也許在未來,它將是這樣。

Sequences do the minimal number of operations

通常我們不需要在每一步都處理整個集合來產生結果。比方說,我們有一個有數百萬個元素的集合,在處理之後,我們只需要取前10個。為什麼要處理其他所有的元素呢?Iterable處理沒有中間操作的概念,所以整個集合的處理就像在每個操作上都要返回一樣。Sequence不需要這樣,所以它們會做最小數量的操作來獲得結果。

image-20221111175929928

看一下這個例子,我們有幾個處理步驟,我們用find來結束我們的處理。

(1..10).asSequence() .filter { print("F$it, "); it % 2 == 1 } .map { print("M$it, "); it * 2 } .find { it > 5 } // Prints: F1, M1, F2, F3, M3,(1..10) .filter { print("F$it, "); it % 2 == 1 } .map { print("M$it, "); it * 2 } .find { it > 5 } // Prints: F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, M1, M3, M5, M7, M9,

出於這個原因,當我們有一些中間處理步驟,並且我們的終端操作不一定需要遍歷所有的元素時,使用一個Sequence很可能對你的處理效能更好。所有這些,同時看起來與標準的集合處理幾乎一樣。這類操作的例子有first, find, take, any, all, none或indexOf等。

Sequences can be infinite

由於Sequence是按需進行處理的,我們可以有無限的Sequence。建立一個無限Sequence的典型方法是使用Sequence生成器,如generateSequence或sequence。第一個生成器需要第一個元素和一個指定如何計算下一個元素的函式。

generateSequence(1) { it + 1 } .map { it * 2 } .take(10) .forEach { print("$it, ") } // Prints: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,

第二個提到的Sequence生成器--sequence--使用一個suspend函式(coroutine),按要求生成下一個數字。每當我們要求下一個數字時,Sequence生成器就會執行,直到使用yield產生一個值。然後停止執行,直到我們要求得到另一個數字。下面是一個無限的下一個斐波那契數字的列表。

val fibonacci = sequence { yield(1) var current = 1 var prev = 1 while (true) { yield(current) val temp = prev prev = current current += temp } } print(fibonacci.take(10).toList()) // [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

請注意,無限Sequence在某些時候需要有有限的元素數量。我們不能在無窮大上迭代。

print(fibonacci.toList()) // Runs forever

因此,我們要麼需要使用像take這樣的操作來限制它們,要麼需要使用一個不需要所有元素的終端操作,比如first、find、any、all、none或indexOf。基本上,這些都是Sequence更有效的操作,因為它們不需要處理所有元素。儘管注意到對於大多數這些操作來說,很容易陷入無限迴圈。any操作符只能返回true或者永遠執行。同樣,all和none操作符在一個無限的集合上也只能返回false。因此,我們通常要麼通過take來限制元素的數量,要麼就用first來要求第一個元素。

Sequences do not create collections at every processing step

標準的集合處理函式在每一步都會返回一個新的集合。大多數情況下,它是一個列表。這可能是一個優勢--在每一個點之後,我們都有一些準備好的東西可以使用或儲存。但它也是有代價的。這樣的集合在每一步都需要被建立並填充資料。

numbers .filter { it % 10 == 0 } // 1 collection here .map { it * 2 } // 1 collection here .sum() // In total, 2 collections created under the hoodnumbers .asSequence() .filter { it % 10 == 0 } .map { it * 2 } .sum() // No collections created

這是個問題,特別是當我們處理大的或重的集合時。讓我們從一個極端但又常見的案例開始:檔案讀取。檔案可以達到數千兆位元組。在每個處理步驟中分配一個集合中的所有資料將是對記憶體的巨大浪費。這就是為什麼我們預設使用Sequence來處理檔案。

作為一個例子,讓我們分析一下芝加哥市的犯罪。這個城市和其他許多城市一樣,在網際網路上分享了自2001年以來發生在那裡的全部犯罪資料庫(你可以在www.data.cityofchicago.org找到這些記錄)。這個資料集目前的Size超過1.53GB。比方說,我們的任務是找出有多少犯罪行為的描述中有大麻。下面就是一個使用集合處理的天真解決方案的樣子(readLines返回List)。

// BAD SOLUTION, DO NOT USE COLLECTIONS FOR // POSSIBLY BIG FILES File("ChicagoCrimes.csv").readLines() .drop(1) // Drop descriptions of the columns .mapNotNull { it.split(",").getOrNull(6) } // Find description .filter { "CANNABIS" in it } .count() .let(::println)

我的電腦上的結果是OutOfMemoryError。

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

不難理解為什麼。我們建立了一個集合,然後我們有3箇中間處理步驟,加起來有4個集合。其中3個包含了這個資料檔案的大部分,需要1.53GB,所以它們都需要消耗超過4.59GB。這是對記憶體的巨大浪費。正確的實現應該是使用一個Sequence,我們使用函式useLines來實現,它總是在一個單行上操作。

File("ChicagoCrimes.csv").useLines { lines -> // The type of `lines` is Sequence<String> lines .drop(1) // Drop descriptions of the columns .mapNotNull { it.split(",").getOrNull(6) } // Find description .filter { "CANNABIS" in it } .count() .let { println(it) } // 318185

在我的電腦上,這需要8.3秒。為了比較這兩種方法的效率,我又做了一個實驗,我通過刪除不需要的列來減少這個資料集的大小。這樣我就得到了CrimeData.csv檔案,其中包含了同樣的罪行,但大小隻有728MB。然後我做了同樣的處理。在第一個實現中,使用集合處理,大約需要13秒;而第二個實現中,使用Sequence,大約需要4.5秒。正如你所看到的,對較大的檔案使用Sequence,不僅是為了記憶體,也是為了效能。

雖然一個集合不需要很重。事實上,每一步我們都在建立一個新的集合,這本身也是一種成本,當我們處理具有較大數量元素的集合時,這種成本就會體現出來。差別並不是非常巨大的原因是--主要是因為經過許多步驟建立的集合被初始化為預期的大小,所以當我們新增元素時,只是把它們放在下一個位置。但這種差異仍然是不可忽視的,這也是為什麼我們更願意使用Sequence來處理超過一個處理步驟的大集合的主要原因。

我所說的 "大集合 "是指許多元素和真正的大集合。它可能是一個有幾萬個元素的整數列表。它也可能是一個只有幾個字串的列表,但每個字串都很長,以至於它們都需要很多兆位元組的資料。這些情況並不常見,但它們有時會發生。

我所說的一個處理步驟,是指超過一個函式的集合處理。因此,如果你比較這兩個函式。

``` fun singleStepListProcessing(): List { return productsList.filter { it.bought } }

fun singleStepSequenceProcessing(): List { return productsList.asSequence() .filter { it.bought } .toList() } ```

你會注意到在效能上幾乎沒有差別(實際上簡單的列表處理更快,因為它的過濾功能是內聯的)。儘管當你比較有多個處理步驟的函式時,比如下面的函式,它使用了過濾器,然後是Map,對於更大的集合來說,差異將是可見的。為了看到區別,讓我們比較一下5000個產品的典型處理,有兩個和三個處理步驟。

``` fun twoStepListProcessing(): List { return productsList .filter { it.bought } .map { it.price } }

fun twoStepSequenceProcessing(): List { return productsList.asSequence() .filter { it.bought } .map { it.price } .toList() }

fun threeStepListProcessing(): Double { return productsList .filter { it.bought } .map { it.price } .average() }

fun threeStepSequenceProcessing(): Double { return productsList.asSequence() .filter { it.bought } .map { it.price } .average() } ```

下面你可以看到在MacBook Pro(處理器2.6 GHz Intel Core i7,記憶體16 GB 1600 MHz DDR3)上對產品清單中5000個產品的平均結果。

twoStepListProcessing 81 095 ns twoStepSequenceProcessing 55 685 ns twoStepListProcessingAndAcumulate 83 307 ns twoStepSequenceProcessingAndAcumulate 6 928 ns

很難預測我們應該期待什麼樣的效能改進。根據我的觀察,在一個典型的有多個步驟的集合處理中,對於至少幾千個元素,我們可以期望有20-40%左右的效能改進。

When aren’t sequences faster?

有一些操作我們不能從這種Sequence的使用中獲益,因為我們必須對整個集合進行操作,sorted是Kotlin stdlib中的一個例子(目前是唯一的例子)。sorted使用了最佳實現。它將Sequence累積到List中,然後使用Java stdlib中的sort。缺點是,如果我們將其與在一個集合上的相同處理進行比較,這個積累過程需要一些額外的時間(儘管如果Iterable不是一個集合或陣列,那麼區別並不明顯,因為它也需要進行積累)。

Sequence是否應該有sorted這樣的方法是有爭議的,因為Sequence流式的操作符中,只是部分操作符是Lazy的(當我們需要得到第一個元素時才進行計算),並且在無限的Sequence上不起作用。新增它是因為它是一個流行的函式,而且這樣使用它要容易得多。儘管Kotlin開發者應該記住它的缺陷,特別是它不能用於無限Sequence。

generateSequence(0) { it + 1 }.take(10).sorted().toList() // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] generateSequence(0) { it + 1 }.sorted().take(10).toList() // Infinite time. Does not return.

sorted是一個罕見的處理例子,它在Collection上比在Sequence上快。儘管如此,當我們做一些處理步驟和單一的排序函式(或其他需要在整個集合上工作的函式)時,我們可以期望使用Sequence處理來提高效能。

``` // Benchmarking measurement result: 150 482 ns fun productsSortAndProcessingList(): Double { return productsList .sortedBy { it.price } .filter { it.bought } .map { it.price } .average() }

// Benchmarking measurement result: 96 811 ns fun productsSortAndProcessingSequence(): Double { return productsList.asSequence() .sortedBy { it.price } .filter { it.bought } .map { it.price } .average() } ```

What about Java stream?

Java 8引入了流,允許集合處理。它們的行為和程式碼外觀類似於Kotlin的Sequence。

productsList.asSequence() .filter { it.bought } .map { it.price } .average()productsList.stream() .filter { it.bought } .mapToDouble { it.price } .average() .orElse(0.0)

Java 8的流是Lazy的,在最後一個(終端)處理步驟中開始計算。Java流和KotlinSequence的三大區別如下。

  • KotlinSequence有更多的處理函式(因為它們被定義為擴充套件函式),它們通常更容易使用(這是由於KotlinSequence是在Java streams已經被使用時設計的--例如,我們可以使用toList()來收集,而不是collectors.toList())。

  • Java流處理可以使用並行函式以並行模式啟動。當我們的機器有多個經常未使用的核心時(這在現在很常見),這可以給我們帶來巨大的效能提升。雖然要謹慎使用,因為這個功能有已知的隱患(問題來自於他們使用的常見的連線-分叉執行緒池。因為,一個Task可能會阻塞另一個Task。還有一個問題是單元素處理會阻塞其他元素。在此閱讀更多資訊:https://dzone.com/articles/think-twice-using-java-8)。

  • KotlinSequence可以在普通模組、Kotlin/JVM、Kotlin/JS和Kotlin/Native模組中使用。Java流只在Kotlin/JVM中使用,而且只在JVM版本至少為8時使用。

一般來說,當我們不使用並行模式時,很難給出一個簡單的答案,Java流和KotlinSequence哪個更有效。我的建議是很少使用Java流,只在計算量大的處理中使用,這樣可以從並行模式中獲益。否則,使用Kotlin stdlib函式,以獲得同質化的、乾淨的程式碼,可以在不同的平臺上或共同的模組上使用。

Kotlin Sequence debugging

Kotlin Sequence和Java Stream都有支援,可以幫助我們在每一步除錯元素流。對於Java Stream,它需要一個名為 "Java Stream Debugger "的外掛。KotlinSequence也需要名為 "Kotlin Sequence Debugger "的外掛,不過現在這個功能已經整合到Kotlin外掛中了。下面是一個顯示Sequence處理的每一步的螢幕。

img

Summary

Collection和Sequence的處理非常相似,都支援幾乎相同的處理方法。然而這兩者之間有重要的區別。Sequence處理更復雜,所以我們通常將元素儲存在集合中,然後轉換集合為Sequence,最後往往還需要回到所需的集合。但Sequence是Lazy的,這帶來了一些重要的優勢。

  • 它們保持操作的自然順序
  • 它們只做最少的操作
  • 它們可以是無限的
  • 它們不需要在每一步都建立集合

因此,它們更適合於處理大尺寸的物件或具有多個處理步驟的大型集合。Sequence也得到了KotlinSequence偵錯程式的支援,它可以幫助我們直觀地看到元素的處理情況。Sequence不能取代經典的集合處理。你應該只在有充分理由的情況下使用它們,而且你會得到顯著的效能優化的回報。

原文翻譯自 https://blog.kotlin-academy.com/effective-kotlin-use-sequence-for-bigger-collections-with-more-than-one-processing-step-649a15bb4bf