[译]Kotlin中的龟(List)兔(Sequence)赛跑

翻译说明:

原标题: Kotlin : Slow List and Lazy Sequence

原文地址: https://medium.com/@elye.project/kotlin-slow-list-and-lazy-sequence-61691fc974c5

原文作者: Elye

自从Kotlin可以兼容Java7上后，很高兴的是我们可以轻松地在List上使用各种集合操作符并且可以链式调用它们。但是我们知道在某些情况下使用List的迭代器并不是最好的方式，那么还有另一种方式就是使用序列(sequence)

没有背景只能辛苦工作的List列表

在我们了解序列在某些情况下为什么更好之前，让我告诉你一些关于List的内容。

List内部使用Iterator进行操作。这是一个非常勤奋的群体，我链式调用它的每一个操作，它都能确保没有任何遗漏的完成。

val list = listOf(1, 2, 3, 4, 5, 6)
list.map{ it * 2 }.filter { it % 3  == 0 }.average()

image

正如你在上面的插图中看到的，对于每一步操作，List的每个元素都需要被处理。

为了证明这一点，让我们输出一些log日志:

val list = listOf(1, 2, 3, 4, 5, 6)
val result = list
        .map{ println("In Map"); it * 2 }
        .filter { println("In Filter");it % 3  == 0 }
println("Before Average")
println(result.average())

结果如下:

In Map
In Map
In Map
In Map
In Map
In Map
In Filter
In Filter
In Filter
In Filter
In Filter
In Filter
Before Average
9.0

很棒。勤奋努力地工作，并完成所有的过程。

懒惰的家伙，Sequence序列...

好的，现在让我们通过调用asSequence()扩展函数来将List转化成一个序列(Sequence)。

val list = listOf(1, 2, 3, 4, 5, 6)
val result = list.asSequence()
        .map{ println("In Map"); it * 2 }
        .filter { println("In Filter");it % 3  == 0 }
println("Before Average")
println(result.average())

结果如下:

Before Average
In Map
In Filter
In Map
In Filter
In Map
In Filter
In Map
In Filter
In Map
In Filter
In Map
In Filter
9.0

哇，有趣...,注意到 "Before Average" 是最先输出的，换句话说，如果我不调用 average() 函数，那么序列(sequence)就没有做任何操作。

它很懒，不想做任何工作，直到终端连接到它。终端就像是一种操作，实际上就是一个操作符扩展函数，会返回其他类型结果(除了Sequence<T>之外),例如 sum()，average()，first()等...。甚至toList()用于将Sequence转换为List

除此之外，你会注意到它输出的In Map和In Filter交叉出现。这意味着它会在通过链条之前一个接一个地通过链条，直到它通过终端，即平均操作，然后通过下一个元素。

image

那么，序列Sequence到底有什么好处呢？

如果你这样想，想象你想要拿到集合变换后的第一个元素。

让我们看下List处理方式:

val list = listOf(1, 2, 3, 4, 5, 6)
val result = list
        .map{ println("In Map $it"); it * 2 }
        .filter { println("In Filter $it");it % 3  == 0 }
println(result.first())

结果如下:

In Map 1
In Map 2
In Map 3
In Map 4
In Map 5
In Map 6
In Filter 2
In Filter 4
In Filter 6
In Filter 8
In Filter 10
In Filter 12
6

所有在一起总共13行，这意味着13次操作。

让我们看下Sequence处理方式:

val sequence = sequenceOf(1, 2, 3, 4, 5, 6)
val result = sequence
        .map{ println("In Map $it"); it * 2 }
        .filter { println("In Filter $it");it % 3  == 0 }
println(result.first())

结果是:

In Filter 2
In Map 2
In Filter 4
In Map 3
In Filter 6
6

仅仅7行即7次操作。这意味着它只要找到第一个元素的那一刻，就会终止整个过程。

你可以想像，这会加快整个运行的过程。

加速仅仅只适用于first()操作吗？

让我们做一些试验。

试验Map操作

val sequence = generateSequence(1) { it + 1 }.take(50000000)
val list = sequence.toList()

println("List Map Sum= " 
        + measureNanoTime { list.map { it * 2 }.sum() })
println("Sequence Map Sum " 
        + measureNanoTime { sequence.map { it * 2 }.sum() })

println("List Map Average " 
        + measureNanoTime { list.map { it * 2 }.average() })
println("Sequence Map Average " 
        + measureNanoTime { sequence.map { it * 2 }.average() })

结果是:

List Map Sum 14727907362
Sequence Map Sum 2074397969
List Map Average 11460520785
Sequence Map Average 3268960487

• List: 在Map:Sum操作上花费了14.7s，在Map:Average操作上花费了11.5s
• Sequence: 在Map:Sum操作上花费了2.1s, 在Map:Average操作上花费了3.3s

image

看上去像前面的有一个Map操作时，Sequence的性能会比List更快。也许它不需要像List那样存储map操作后的中间结果，从而会更快。

试验Filter操作

val sequence = generateSequence(1) { it + 1 }.take(50000000)
val list = sequence.toList()

println("List Filter Sum " 
        + measureNanoTime { list.filter { it % 3 == 0 }.sum() })
println("Sequence Filter Sum " 
        + measureNanoTime { sequence.filter { it % 3 == 0 }.sum() })

println("List Filter Average " 
        + measureNanoTime { list.filter { it % 3 == 0 }.average() })
println("Sequence Filter Average " 
        + measureNanoTime { sequence.filter { it % 3 == 0 }.average() })

结果是:

List Filter Sum 506351694
Sequence Filter Sum 873175271
List Filter Average 391790033
Sequence Filter Average 838510968

• List: 在Filter:Sum操作上花费了0.5s，在Filter:Average操作上花费了0.4s
• Sequence: 在Filter:Sum操作上花费了0.9s, 在Filter:Average操作上花费了0.8s

image

对于前面的Filter操作，Sequence比List更慢。 深入了解函数，看起来像Sequence的Filter操作需要有更多的开销来检查某些状态，而List的Filter则是一个简单的检查并收集新的元素。

试验Map和Filter操作

val sequence = generateSequence(1) { it + 1 }.take(50000000)
val list = sequence.toList()

println("List Map Filter Sum\t\t " + measureNanoTime { 
    list.map { it * 2 }.filter { it % 3 == 0 }.sum() })
println("Sequence Map Filter Sum\t " + measureNanoTime { 
    sequence.map { it * 2 }.filter { it % 3 == 0 }.sum() })

println("List Map Filter Average\t\t " + measureNanoTime { 
    list.map { it * 2 }.filter { it % 3 == 0 }.average() })
println("Sequence Map Filter Average\t " + measureNanoTime { 
    sequence.map { it * 2 }.filter { it % 3 == 0 }.average() })

结果是:

List Map Filter Sum 34845242323
Sequence Map Filter Sum 2820436086
List Map Filter Average 2328258876
Sequence Map Filter Average 18618444560

• List: 在Map:Filter:Sum操作上花费了34.8s，在Map:Filter:Average操作上花费了2.3s
• Sequence: 在Map:Filter:Sum操作上花费了2.8s, 在Map:Filter:Average操作上花费了18.6s

[图片上传失败...(image-321597-1529421702971)]

一个相对令人惊讶的结果，如Map:Filter:Sum，Sequence比List快得多，而Map:Filter:Average，List比Sequence要快得多。

试验直接使用Sequence和List

val sequence = generateSequence(1) { it + 1 }.take(50000000)
val list = sequence.toList()

println("List Sum " + measureNanoTime { list.sum() })
println("Sequence Sum " + measureNanoTime { sequence.sum() })

println("List Average " + measureNanoTime { list.average() })
println("Sequence Average " + measureNanoTime { sequence.average() })

结果是:

List Sum 91726022
Sequence Sum 592771887
List Average 101141460
Sequence Average 622616340

• List: 在Sum操作上花费了0.1s，在Average操作上花费了0.1s
• Sequence: 在Sum操作上花费了0.5s, 在Average操作上花费了0.6s

没有任何中间操作，明显列表List比序列Sequence要快。

总结:

• 1、当不需要中间操作时，使用List
• 2、当仅仅只有map操作时，使用sequence
• 3、当仅仅只有filter操作时，使用List
• 4、如果末端操作是first时，使用sequence
• 5、对于没有提及的其他操作符或者其他操作符的组合，请尝试使用例子去验证一下

译者有话说:

首先，说下为什么要翻译这篇博客？关于Kotlin中的Sequence和List的使用以及源码解析相关的文章我已经写过两篇了，这篇博客主要吸引我的一点就是以更多运行的例子试验和相关幽默的配图更加形象地描述了Sequence，List的区别以及各自的使用场景。

然而，这篇博客并没有深入源码去讲解Sequence的实现，这篇之前写的博客 浅谈Kotlin中的序列(Sequences)源码完全解析(十) 从源码角度带你一步步分析Sequence序列背后的原理，关于如何正确使用Sequence和List以及各自使用场景,之前翻译的一篇博客 [译]Kotlin中是应该使用序列(Sequences)还是集合(Lists)? 会有更加全面的介绍。

最后，有了这三篇文章应该更加全面理解了Sequence的原理和使用。

qrcode_for_gh_109398d5e616_430.jpg

欢迎关注Kotlin开发者联盟，这里有最新Kotlin技术文章，每周会不定期翻译一篇Kotlin国外技术文章。如果你也喜欢Kotlin，欢迎加入我们~~~