让你迷惑的 Kotlin 代码（4）
上一期 有人留言说 “就没回答对过” 。甭担心，晒一下前几期的正确率，你并不孤单 ~
期数 | 投票人数 | 正确人数 | 正确率 |
|---|---|---|---|
1 | / | / | / |
2 | 93 | 33 | 35% |
3 | 139 | 26 | 19% |
前面连续说了两期 Lambda，今天来一道集合相关的题目。上菜！
fun main(args: Array<String>) {
listOf(1, 2, 3).filter {
print("$it ")
it >= 2
}
print("- ")
listOf(1, 2, 3)
.asSequence()
.map {
print("$it")
it + 1
}
.filter {
print("$it ")
it >= 3
}
}
老规矩，先答题。
答案看起来比较绕，但题目还是比较简单的。
map 函数会逐一变换集合中的元素，其中的打印语句肯定会对所有元素都执行。
可能比较让人纠结的点是，filter 函数中的打印语句，是会对所有元素都执行？还是仅对满足过滤条件的元素执行？
对所有元素都执行，就会打印 1 2 3 - 1 2 3 2 3 4 ，选 C 。
仅对满足过滤条件的元素执行，就会打印 2 3 - 1 2 3 3 4，选 D 。
...
...
...
经过这一番理性分析（瞎胡扯），正确答案其实是 以上均不对 。
以 print("- ") 为分割线，上面的代码是对 集合 List 进行操作，下面的代码是对集合 List 调用 asSequence() ，转换为 序列 Sequence 再进行操作。这是两段代码的本质区别。
List.filter
先看上半部分代码。不知道前面的瞎胡扯有没有把你说晕，操作符 List.filter() 的逻辑是很简单的。直接看源码。
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
return filterTo(ArrayList<T>(), predicate) // 注意看参数，新建了一个 ArrayList
}
public inline fun <T, C : MutableCollection<in T>> Iterable<T>.filterTo(destination: C, predicate: (T) -> Boolean): C {
for (element in this) if (predicate(element)) destination.add(element) // 遍历集合
return destination
}
filter 函数的目的是过滤原集合，输出一个新集合。实现方式就是新建一个新集合，再遍历原集合，逐个元素按过滤条件 predicate 判断，符合条件的就加入新集合。
所以前半部分代码中，集合中的每个元素都会被打印，输出 1 2 3 。
这里要注意一点，filter 操作符会产生一个新的中间集合。其实不止 filter，所有集合操作符都会产生中间集合。如果有嵌套操作，例如 list.map{ }.filter{ }，每一步操作都会产生新的中间集合。
所以当集合元素数量巨大的情况下，会存在一定的性能问题。而下半部分代码中的 Sequence 正好解决了这个问题。
懒惰的 Sequence
回顾一下下半部分的代码。
listOf(1, 2, 3)
.asSequence()
.map {
print("$it")
it + 1
}
.filter {
print("$it ")
it >= 3
}
没用过 Sequence 的话，也看不出什么花头来，就直接源码搂起来。
先看 asSequence() 。
public fun <T> Iterable<T>.asSequence(): Sequence<T> {
return Sequence { this.iterator() } // 注意这个 Sequence 是函数
}
将 Iterable 对象转化为 Sequence 对象。但要注意第二行中 return 后面跟的 Sequence 其实是个返回值是 Sequence 对象的函数，代码如下：
public inline fun <T> Sequence(crossinline iterator: () -> Iterator<T>): Sequence<T> = object : Sequence<T> {
override fun iterator(): Iterator<T> = iterator()
}
Sequence() 函数的参数是迭代器 iterator，返回值是 Sequence 对象。Sequence 对象持有了参数中的迭代器。
public interface Sequence<out T> {
public operator fun iterator(): Iterator<T>
}
所以，集合 List 转换为序列 Sequence ，就等同于序列 Sequence 持有了集合 List 的迭代器。
接着来看序列 Sequence.map 函数。
public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R> {
return TransformingSequence(this, transform)
}
Sequence.map() 返回了序列的一个实现类 TransformingSequence ，map 函数的函数类型参数 transform 也一并传给了这个 TransformingSequence 。
internal class TransformingSequence<T, R>
constructor(private val sequence: Sequence<T>, private val transformer: (T) -> R) : Sequence<R> {
override fun iterator(): Iterator<R> = object : Iterator<R> {
val iterator = sequence.iterator() // 获取上一级的迭代器
override fun next(): R {
return transformer(iterator.next()) // 重写 next() 方法
}
override fun hasNext(): Boolean {
return iterator.hasNext()
}
}
internal fun <E> flatten(iterator: (R) -> Iterator<E>): Sequence<E> {
return FlatteningSequence<T, R, E>(sequence, transformer, iterator)
}
}
TransformingSequence 持有着上一级 Sequence 的迭代器，同时重写了 Sequence 的 iterator() 方法，定义了自己的迭代器。每取一个元素的时候，通过上一级迭代器的 next() 方法，再执行自己的 transformer() 变换操作。
所以......
Sequence.map() 仅仅只是构建了一个新的 Sequence 。所以，题目中的打印语句自然不会执行。
Sequence.filter() 也是一样，它构建的是一个 FilteringSequence 。这里就不看它的源码了。
前半部分代码会打印 1 2 3 ，后半部分代码什么也不会打印，所以最后的答案是 1 2 3 - 。
让 Sequence 跑起来
Sequence 是惰性的，它的一系列操作符仅仅只是构建了一个个新的 Sequence 。那么，如果让各个操作符跑起来呢？答案就是，再转换回集合 List 。
这个操作通过 Sequence.toList() 函数完成，其最终会调用到 Sequence.toCollection() 。
public fun <T, C : MutableCollection<in T>> Sequence<T>.toCollection(destination: C): C {
for (item in this) {
destination.add(item)
}
return destination
}
通过 Sequence 的迭代器取出所有元素，加入到集合中来。整个数据流就跑动起来了。
那么，又到了竞猜环节...
fun main() {
listOf(1, 3, 5)
.asSequence()
.map {
print("$it")
it + 1
}
.filter {
print("$it ")
it >= 3
}.toList()
}
输出结果是 1 2 3 4 5 6 ? 还是 1 3 5 2 4 6 ？
也就是说是逐个元素依次先 map 再 filter ？伪代码如下：
for (item in this) {
map(item)
filter(item)
}
还是整个集合先整体 map 再整体 filter ？伪代码如下：
for (item in this) {
map(item)
}
for (item in this) {
filter(item)
}
答案是前者。其实前面的 TransformingSequence() 的源码已经告诉了我们答案。
internal class TransformingSequence<T, R>
constructor(private val sequence: Sequence<T>, private val transformer: (T) -> R) : Sequence<R> {
override fun iterator(): Iterator<R> = object : Iterator<R> { // 定义自己的迭代器
val iterator = sequence.iterator() // 获取上一级 Sequence 的迭代器
override fun next(): R {
return transformer(iterator.next()) // 在自身的 next() 方法中调用上一个 Sequence 的迭代器的 next() 方法
}
override fun hasNext(): Boolean {
return iterator.hasNext() // 调用上一级 Sequence 的迭代器的 hasNext() 方法
}
}
...
}
在序列 Sequence 的链式操作符调用中，每一个操作符都会生成新的 Sequence，每一个新的 Sequence 又会持有上一级 Sequence ，并在调用自身的迭代器的 next() 和 hasNext() 方法时，调用上一级的 next() 和 hasNext() 方法。
当调用 toList() 操作，使用链式操作末端的操作符产生的 Sequence 的迭代器进行迭代时，会递归调用到最上层的第一个 Sequence 的迭代器，而在调用每一个上级迭代器时，同时又会执行自身操作符的对应操作，比如变换，过滤等。
所以，题目的答案是逐个对集合中的元素先 map 再 filter，输出 1 2 3 4 5 6 。
另外，如果是先 filter 再 map 的情况，相比先 map 再 filter 可以减少部分不需要的操作。因为不满足 filter 情况的元素就不会再执行 map 了。
Java 也可以？
对于安卓开发来说，可能对 Java8 的 Stream 比较陌生，因为版本限制导致我们不大可能使用 Java8 新特性。
Java8 的 Stream 提供了类似 Kotlin 的处理集合的能力，map 、filter 、skip 、flatmap 等等。
那么，它是如 Kotlin 集合一般勤快，还是如 Sequence 一般懒惰呢？
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(5);
list.stream().map(i -> {
System.out.print(i);
return i + 1;
}).filter(i -> {
System.out.print(i);
return i >= 3;
});
}
上面这段代码会输出什么呢？欢迎在评论区留下你的答案。
往期推荐