## 惰性集合操作：[序列](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，你还可以得到想要的那个目录（对象〉。注意，使用序列允许你找到需要的目录之后立即停止遍历父目录。