## 惰性集合操作：[序列](http://www.kotlincn.net/docs/reference/sequences.html#%E5%BA%8F%E5%88%97) ### 通過序列提高效率 在前面一節中，你看到了許多鏈式集合函數調用的例子，比如map 和filter 。這些函數會及早地創建中間集合，也就是說每一步的中間結果都被存儲在一個臨時列表。序列給了你執行這些操作的另一種選擇，可以避免創建這些臨時中間對象。 ``` people.map(Person:: name).filter{ it.startsWith("A")｝ ``` Kotlin 標準庫參考文檔有說明， filter和map 都會返回一個列表。這意味著上面例子中的**鏈式調用會創建兩個列表： 一個保存filter 函數的結果，另一個保存map 函數的結果。如果源列表只有兩個元素，這不是什么問題，但是如果有一百萬個元素，（鏈式）調用就會變得十分低效**。 為了提高效率， 可以把操作變成使用序列，而不是直接使用集合：  應用這次操作后的結果和前面的例子一模一樣： 一個以字母A 開頭的人名列表。但是第二個例子**沒有創建任何用于存儲元素的中間集合，所以元素數量巨大的情況下性能將顯著提升**。 Kotlin惰性集合操作的入口就是Sequence接口。這個接口表示的就是一個可以逐個列舉元素的元素序列。Sequence只提供了一個方法，iterator ，用來從序列中獲取值。 Sequence 接口的強大之處在于其操作的實現方式。**序列中的元素求值是惰性的。因此，可以使用序列更高效地對集合元素執行鏈式操作，而不需要創建額外的集合來保存過程中產生的中間結果**。 **可以調用擴展函數asSequence 把任意集合轉換成序列，調用toList 來做反向的轉換**。 **為什么需要把序列轉換回集合？用序列代替集合不是更方便嗎**？特別是它們還有這么多優點。答案是：**有時候如果你只需要迭代序列中的元素，可以直接使用序列。如果你要用其他的API方法，比如用下標訪問元素，那么你需要把序列轉換成列表**。 >[info]注意：通常， 需要對一個大型集合執行鏈式操作時要使用序列。以后討論Kotlin 常規集合的及早操作高效的原因，盡管它會創建中間集合。但是如果集合擁有數量巨大的元素元，素為中間結果進行重新分配開銷巨大，所以惰性求值是更好的選擇 因為序列的操作是惰性的，為了執行它們，你需要直接送代序列元素，或者把序列轉換成一個集合。 在Kotlin中，序列中元素的求值是惰性的，這就意味著在利用序列進行鏈式求值的時候，不需要像操作普通集合那樣，每進行一次求值操作，就產生一個新的集合保存中間數據。那么惰性又是什么意思呢？先來看看它的定義： **在編程語言理論中，惰性求值（Lazy Evaluation）表示一種在需要時才進行求值的計算方式。在使用惰性求值的時候，表達式不在它被綁定到變量之后就立即求值，而是在該值被取用時才去求值。通過這種方式，不僅能得到性能上的提升，還有一個最重要的好處就是它可以構造出一個無限的數據類型**。 通過上面的定義我們可以簡單歸納出**惰性求值的兩個好處，一個是優化性能，另一個就是能夠構造出無限的數據類型**。這里只需要先知道這個概念，在后面我們會詳細介紹。 ### 執行序列操作：中間和末端操作 序列操作分為兩類：中間的和末端的。一次中間操作返回的是另一個序列，這個新序列知道如何變換原始序列中的元素。而一次末端操作返回的是一個結果，這個結果可能是集合、元素、數字，或者其他從初始集合的變換序列中獲取的任意對象。  中間操作始終都是惰性的。先看看下面這個缺少了末端操作的例子： ``` fun main(args: Array<String>) { listOf(1, 2, 3, 4).asSequence() .map { print("map($it) "); it * it } .filter { print("filter($it) "); it % 2 == 0 } } ``` 執行這段代碼并不會在控制臺上輸出任何內容。這意味著map 和filter 變換被延期了，它們只有在獲取結果的時候才會被應用（ 即末端操作被調用的時候），即惰性求值僅僅在該值被需要的時候才會真正去求值。那么這個“被需要”的狀態該怎么去觸發呢？這就需要另外一個操作了——末端操作。： #### 末端操作 在對集合進行操作的時候，大部分情況下，我們在意的只是結果，而不是中間過程。末端操作就是一個返回結果的操作，它的返回值不能是序列，必須是一個明確的結果，比如列表、數字、對象等表意明確的結果。末端操作一般都放在鏈式操作的末尾，在執行末端操作的時候，會去觸發中間操作的延遲計算，也就是將“被需要”這個狀態打開了。我們給前面的那個例子加上末端操作： ~~~ fun main(args: Array<String>) { val list = listOf(1, 2, 3, 4, 5) list.asSequence().filter { println("filter($it)") it > 2 }.map { println("map($it)") it * 2 }.toList() } ~~~ 結果 ``` filter(1) filter(2) filter(3) map(3) filter(4) map(4) filter(5) map(5) ``` 可以看到，所有的中間操作都被執行了。仔細看看上面的結果，我們可以發現一些有趣的地方。作為對比，我們先來看看上面的操作如果不用序列而用列表來實現會有什么不同之處： ~~~ fun main(args: Array<String>) { val list = listOf(1, 2, 3, 4, 5) list.filter { println("filter($it)") it > 2 }.map { println("map($it)") it * 2 } } ~~~ 輸出結果 ``` filter(1) filter(2) filter(3) filter(4) filter(5) map(3) map(4) map(5) ``` 通過對比上面的結果，我們可以發現，普通集合在進行鏈式操作的時候會先在list上調用filter，然后產生一個結果列表，接下來map就在這個結果列表上進行操作。而**序列則不一樣，序列在執行鏈式操作的時候，會將所有的操作都應用在一個元素上，也就是說，第1個元素執行完所有的操作之后，第2個元素再去執行所有的操作，以此類推**。反映到我們這個例子上面，就是第1個元素執行了filter之后再去執行map，然后第2個元素也是這樣。 通過上面序列的返回結果我們還能發現，由于列表中的元素1、2沒有滿足filter操作中大于2的條件，所以接下來的map操作就不會去執行了。所以**當我們使用序列的時候，如果filter和map的位置是可以相互調換的話，應該優先使用filter，這樣會減少一部分開銷**。 下面我們看另一個示例 ``` fun main(args: Array<String>) { listOf(1, 2, 3, 4).asSequence() .map { print("map($it) "); it * it } .filter { print("filter($it) "); it % 2 == 0 } .toList() } ``` 輸出結果 ``` map(1) filter(1) map(2) filter(4) map(3) filter(9) map(4) filter(16) ``` 末端操作觸發執行了所有的延期計算。 這個例子中另外一件值得注意的重要事情是計算執行的順序。一個笨辦法是先在每個元素上調用map 函數，然后在結果序列的每個元素上再調用filter 函數。map 和filter 對集合就是這樣做的，而序列不一樣。對序列來說，所有操作是按 順序應用在每一個元素上：處理完第一個元素（先映射再過濾），然后完成第二個元素的處理，以此類推。 這種方法意味著部分元素根本不會發生任何變換，如果在輪到它們之前就己經取得了結果。我們來看一個map 和find 的例子。首先把一個數字映射成它的平方，然后找到第一個比數字3 大的條目： ``` println(listOf(1, 2, 3, 4).asSequence().map { it * it }.filter {it >3})//4 ``` 如果同樣的操作被應用在集合而不是序列上時，那么map 的結果首先被求出來，即變換初始集合中的所有元素。第二步，中間集合中滿足判斷式的一個元素會被找出來。而對于序列來說，惰性方法意味著你可以跳過處理部分元素。下圖闡明了這段代碼兩種求值方式之間的區別， 一種是及早求值（使用集合）， 一種是惰性求值（使用序列）。  第一種情況，當你使用集合的時候，列表被變換成了另一個列表，所以map 變換應用到每一個元素上，包括了數字3 和4 。然后，第一個滿足判斷式的元素被找到了：數字2 的平方。 第二種情況， find 調用一開始就逐個地處理元素。從原始序列中取一個數字，用map 變換它，然后再檢查它是否滿足傳給find 的判斷式。當進行到數字2 時，發現它的平方己經比數字3 大，就把它作為find 操作結果返回了。不再需要繼續檢查數字3 和4 ，因為這之前你己經找到了結果。 在集合上執行操作的順序也會影響性能。假設你有一個人的集合，想要打印集合中那些長度小于某個限制的人名。你需要做兩件事： 把每個人映射成他們的名字，然后過濾掉其中那些不夠短的名字。這種情況可以用任何順序應用map 和filter操作。兩種順序得到的結果一樣，但它們應該執行的變換總次數是不一樣的，如圖所示。   如果map 在前，每個元素都被變換。而如果filter在前，不合適的元素會被盡早地過濾掉且不會發生變換。 ### 序列可以是無限的 在介紹惰性求值的時候，我們提到過一點，就是**惰性求值最大的好處是可以構造出一個無限的數據類型**。那么我們能否**使用序列來構造出一個無限的數據類型**呢？答案是肯定的。我們先思考一下，常見的無限的數據類型是什么？我們很容易就能想到數列，比如自然數數列就是一個無限的數列。 那接下來，該怎樣去實現一個自然數數列呢？采用一般的列表肯定是不行的，因為構建一個列表必須列舉出列表中元素，而我們是沒有辦法將自然數全部列舉出來的。 我們知道，自然數是有一定規律的，就是后一個數永遠是前一個數加1的結果，我們**只需要實現一個列表，讓這個列表描述這種規律，那么也就相當于實現了一個無限的自然數數列**。好在Kotlin也給我們提供了這樣一個方法，去**創建無限的數列**： ``` val naturalNumList = generateSequence(0) { it + 1} ``` 通過上面這一行代碼，我們就非常簡單地實現了自然數數列。上面我們**調用了一個方法generateSequence來創建序列**。我們知道**序列是惰性求值的，所以上面創建的序列是不會把所有的自然數都列舉出來的，只有在我們調用一個末端操作的時候，才去列舉我們所需要的列表**。比如我們要從這個自然數列表中取出前10個自然數： ``` >>> naturalNumList.takeWhile {it <= 9}.toList() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ``` >[info]注意：關于無限數列這一點，我們不能將一個無限的數據結構通過窮舉的方式呈現出來，而只是實現了一種表示無限的狀態，讓我們在使用時感覺它就是無限的。 ### 序列與Java 8 Stream對比 如果你熟悉Java 8的話，當你看到序列的時候，你一定不會陌生。因為序列看上去就和Java 8中的流（Stream）比較類似。這里我們來列舉一些Java 8 Stream中比較常見的特性，并與Kotlin中的序列進行比較 #### 1. Java也能使用函數式風格API 在前面我們介紹了Kotlin中的許多函數式風格API，這些API相比于Java中傳統的集合操作顯得優雅多了。但是當Java 8出來之后，在Java中也能像在Kotlin中那樣操作集合了，比如前面將性別為男的學生篩選出來就可以這樣去做： ``` students.stream().filter (it -> it.sex == "m").collect(toList()); ``` 在上面的Java代碼中，我們通過使用stream就能夠使用類似于filter這種簡潔的函數式API了。但是相比于Kotlin, Java的這種操作方式還是有些煩瑣，因為如果要對集合使用這種API，就必須先將集合轉換為stream，操作完成之后，還要將stream轉換為List，這種操作有點類似于Kotlin的序列。這是因為Java 8的流和Kotlin中的序列一樣，也是惰性求值的，這就意味著Java 8的流也是存在中間操作和末端操作的（事實也確實如此），所以必須通過上面的一系列轉換才行。 #### 2. Stream是一次性的 與Kotlin的序列不同，Java 8中的流是一次性的。意思就是說，**如果我們創建了一個Stream，我們只能在這個Stream上遍歷一次。這就和迭代器很相似，當你遍歷完成之后，這個流就相當于被消費掉了，你必須再創建一個新的Stream才能再遍歷一次**。 ``` Stream<Student> studentsStream = students.stream(); studentsStream.filter (it -> it.sex == "m").collect(toList()); studentsStream.filter (it -> it.sex == "f").collect(toList()); //你不能再繼續在studentsStream上進行這種遍歷操作，否則會報錯 ``` #### 3. Stream能夠并行處理數據 Java 8中的流非常強大，其中有一個非常重要的特性就是Java 8 Stream能夠在多核架構上并行地進行流的處理。比如將前面的例子轉換為并行處理的方式如下： ``` students.paralleStream().filter (it -> it.sex == "m").collect(toList()); ``` 只需要將stream換成paralleStream即可。當然使用流并行處理數據還有許多需要注意的地方，這里只是簡單地介紹一下。并行處理數據這一特性是Kotlin的序列目前還沒有實現的地方，如果我們需要用到處理多線程的集合還需要依賴Java。 >[info]流VS序列 如果你很熟悉Java 8 中的流這個概念，你會發現序列就是它的翻版。Kotlin提供了這個概念自己的版本，原因是Java 8 的流并不支持那些基于Java 老版本的平臺，例如Android。如果你的目標版本是Java 8 ，流提供了一個Kotlin 集合和序列目前還沒有實現的重要特性：在多個CPU 上并行執行流操作（比如map和filter ）的能力。可以根據Java 的目標版本和你的特殊要求在流和序列之間做出選擇。 ### 創建序列 前面的例子都是使用同一個方法創建序列： 在集合上調用asSequence()。另一種可能性是**使用generateSequence函數。給定序列中的前一個元素，這個函數會計算出下一個元素**。下面這個例子就是如何使用generateSequence計算100 以內所有自然數之和。 ``` fun main(args: Array<String>) { val naturalNumbers = generateSequence(0) { it + 1 } val numbersTo100 = naturalNumbers.takeWhile { it <= 100 } println(numbersTo100.sum())//當獲取結果sum時，所有被推遲的操作都被執行 //5050 } ``` >[info]注意，這個例子中的naturalNumbers 和numbersTo100都是有延期操作的序列。這些序列中的實際數字直到你調用末端操作（這里是sum ）的時候才會求值。 另一種常見的用例是父序列。如果元素的父元素和它的類型相同（比如人類或者Java 文件），你可能會對它所有祖先組成的序列的特質感興趣。下面這個例子可以查詢文件是否放在隱藏目錄中，通過創建一個其父目錄的序列并檢查每個目錄的屬性來實現。 ``` import java.io.File fun File.isInsideHiddenDirectory() = generateSequence(this) { it.parentFile }.any { it.isHidden } fun main(args: Array<String>) { val file = File("/Users/svtk/.HiddenDir/a.txt") println(file.isInsideHiddenDirectory())//true } ``` 又一次，你生成了一個序列，通過提供第一個元素和獲取每個后續元素的方式來實現。如果把any換成find，你還可以得到想要的那個目錄（對象〉。注意，使用序列允許你找到需要的目錄之后立即停止遍歷父目錄。