阅读 639

[译]Effective Kotlin系列之使用Sequence来优化集合的操作(四)

简述: 今天迎来了Effective Kotlin系列的第四篇文章: 使用Sequence序列来优化大集合的频繁操作.关于Sequence这个主题应该大家都不陌生,我写过几篇有关它的文章,可以说得上很详细了。如果你对它的使用不太熟悉,欢迎查看下面几篇有关文章:

翻译说明:

原标题: Effective Kotlin: Use Sequence for bigger collections with more than one processing step

原文地址: blog.kotlin-academy.com/effective-k…

原文作者: Marcin Moskala

开发者经常会忽略了Iterable(迭代器)与Sequence(序列)的区别。这其实也很正常,特别是当你去比较IterableSequence的接口定义时,它们长得几乎一样。

interface Iterable<out T> {
    operator fun iterator(): Iterator<T>
}
interface Sequence<out T> {
    operator fun iterator(): Iterator<T>
}
复制代码

对比上面代码,你只能说出它们之间唯一不一样就是接口名不同而已。但是IterableSequence却有着完全不同的用法,因此它们操作集合的函数的工作原理也是完全不同的。

序列是基于惰性的工作原理,因此处理序列的中间操作函数是不进行任何计算的。相反,它们会返回上一个中间操作处理后产生的新序列。所有这些一系列中间计算都将在终端操作执行中被确定,例如常见的终端操作toListcount.在另一方面,处理Iterable的每个中间操作函数都是会返回一个新的集合。

fun main(args: Array<String>) {
    val seq = sequenceOf(1,2,3)
    print(seq.filter { it % 2 == 1 }) 
    // Prints: kotlin.sequences.FilteringSequence@XXXXXXXX
    print(seq.filter { it % 2 == 1 }.toList()) // Prints: [1, 3]
    val list = listOf(1,2,3)
    print(list.filter { it % 2 == 1 }) // Prints: [1, 3]
}
复制代码

序列的filter函数是一个中间操作,所以它不会做任何的计算,而是经过新的处理步骤对序列进行了加工。最终的计算将在终端操作中完成,如toList函数

正因为这样,处理操作的顺序也是不同的。在处理序列过程中,我们通常会对单个元素进行一系列的整体操作,然后再对下一个元素做进行一系列的整体操作,直到处理完集合中所有元素为止。在处理iterable过程中,我们是每一步操作都是针对整个集合进行,直到所有操作步骤执行完毕为止。

sequenceOf(1,2,3)
        .filter { println("Filter $it, "); it % 2 == 1 }
        .map { println("Map $it, "); it * 2 }
        .toList()
// Prints: Filter 1, Map 1, Filter 2, Filter 3, Map 3,
listOf(1,2,3)
        .filter { println("Filter $it, "); it % 2 == 1 }
        .map { println("Map $it, "); it * 2 }
// Prints: Filter 1, Filter 2, Filter 3, Map 1, Map 3,
复制代码

由于这种惰性处理方式以及针对每个元素进行处理的顺序,我们可以生成一个不定长的Sequence序列

generateSequence(1) { it + 1 }
        .map { it * 2 }
        .take(10)
        .forEach(::print)
// Prints: 2468101214161820
复制代码

对于具有一定经验的Kotlin开发人员来说,这应该不陌生吧,但是在大多数文章或书籍中并没有提及到有关序列一个更重要的知识点: 对于处理多个单一处理步骤的集合使用序列更高效

多个处理步骤是什么意思?我的意思不仅仅是多个处理集合的单一函数。所以如果你比较这两个函数:

fun singleStepListProcessing(): List<Product> {
    return productsList.filter { it.bought }
}

fun singleStepSequenceProcessing(): List<Product> {
    return productsList.asSequence()
            .filter { it.bought }
            .toList()
}
复制代码

你会注意到它们性能对比几乎没有任何差异,或者说处理简单的集合速度更快(因为它是内联的)。假如你对比了多个处理步骤的函数,比如先是filter处理然后进行了map处理的twoStepListProcessing函数,那么差异将是很明显了。

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

fun twoStepSequenceProcessing(): List<Double> {
    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()
复制代码

差异到底有多大呢? 让我们对比一下基准测量出来的平均操作时间吧:

twoStepListProcessing                                   81 095 ns/op
twoStepSequenceProcessing                               55 685 ns/op
twoStepListProcessingAndAcumulate                       83 307 ns/op
twoStepSequenceProcessingAndAcumulate                    6 928 ns/op
复制代码

当我们使用Sequences时, twoStepSequenceProcessing函数明显比twoStepListProcessing函数处理集合速度要快很多。在这种情况下,优化的效率约为30%左右。

当我们分别使用SequencesIterable处理集合数据来获得某个具体的数值而不是获得一个新集合时,它们之间的效率差异将会变大。因为在这种情况下,序列根本就不需要创建任何中间集合。

来看一些典型的现实生活的例子,假设我们需要计算成年人购买该产品的平均价格:

fun productsListProcessing(): Double {
    return clientsList
            .filter { it.adult }
            .flatMap { it.products }
            .filter { it.bought }
            .map { it.price }
            .average()
}
fun productsSequenceProcessing(): Double {
    return clientsList.asSequence()
            .filter { it.adult }
            .flatMap { it.products.asSequence() }
            .filter { it.bought }
            .map { it.price }
            .average()
}
复制代码

这是对比结果:

SequencesBenchmark.productsListProcessing             712 434 ns/op
SequencesBenchmark.productsSequenceProcessing         572 012 ns/op
复制代码

我们大概提高了20%的优化效率,这比直接处理没有使用flatMap的情况要低一点,但这已经是一个很大的提升了。

当你一次又一次对比测量的性能数据时,你会发现如下这个规律:

当我们有多个处理步骤时,使用序列处理集合通常比直接处理集合更快。

哪种场景下序列处理速度不会更快呢?

在有一些不常用的操作中使用序列处理速度并不会更快,因为我们需要完整地操作整个集合。来自Kotlin stdlib标准库中的sorted就是一个明显的例子。

sorted使用的最佳实现:它将Sequence中的元素转换到List中,然后使用Java stdlib标准库中的sort函数进行排序操作。这个缺点就在于相比相同操作Collection的过程,中间这个转换过程是需要花费额外的时间的(尽管如果Iterable不是Collection或数组,那么差异就并不大,因为它转换过程也是需要花费时间的)

如果Sequence序列有类似sort这样的函数是有争议的,因为它只是固定空间长度上的惰性,并且不能用于不定长的序列。之所以引进它是因为它是一种比较受欢迎的函数,并且以这种方式使用它更容易。但是Kotlin开发人员应该要记住,它不能用于不定长的序列

generateSequence(0) { it + 1 }.sorted().take(10).toList()
// 不定长的计算时间
generateSequence(0) { it + 1 }.take(10).sorted().toList()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码

sorted是一个少见处理步骤的例子,它在Collection上使用的效率会比Sequence更高。当我们使用多个处理步骤和单个排序函数是,我们可以期待使用Sequence序列处理的性能将得到提升。

// Took around 150 482 ns
fun productsSortAndProcessingList(): Double {
    return productsList
            .sortedBy { it.price }
            .filter { it.bought }
            .map { it.price }
            .average()
}

// Took around 96 811 ns
fun productsSortAndProcessingSequence(): Double {
    return productsList.asSequence()
            .sortedBy { it.price }
            .filter { it.bought }
            .map { it.price }
            .average()
}
复制代码

Java中的Stream(流)怎么样呢?

Java8中引入了流来处理集合。它们表现得看起来和Kotlin中的序列很像。

productsList.asSequence()
    .filter { it.bought }
    .map { it.price }
    .average()

productsList.stream()
    .filter { it.bought }
    .mapToDouble { it.price }
    .average()
    .orElse(0.0)
复制代码

它们也都是基于惰性求值的原理并且在最后(终端)处理集合。Java中的流对于集合的处理效率几乎和Kotlin中的序列处理集合一样高。Java中的Stream流和Kotlin中的Sequence序列两者最大的差别如下所示:

  • Kotlin中Sequence序列有更多的操作符函数(因为它们可以被定义成扩展函数)并且它们的用法也相对更简单(这是因为Kotlin的序列是已经在使用的Java流基础上设计的 - 例如我们可以使用toList()而不是collect(Collectors.toList()))
  • Java的Stream流支持可以使用parallel函数以并行模式使用Java流. 当我们拥有一台具有多个内核的计算机时,这可以为我们带来巨大的性能提升。
  • Kotlin的Sequence序列可用于通用模块、Kotlin/JS模块和Kotlin/Native模块中。

除此之外,当我们不使用并行模式时,要说Java stream和 Kotlin sequence哪个更高效,这个真的很难说。

我的建议是仅仅将Java中的Stream用于计算量较大的处理以及需要启用并行模式的场景。否则其他一般场景使用Kotlin Stdlib标准库中Sequence序列,可以给你带来相同效率并且操作函数使用起来也很简单,代码更加简洁。

译者有话说

老实说这篇文章,好的地方在于原作者把Kotlin中的序列和Java 8中的流做了一个很好的对比,以及作者给出自己的使用建议以及针对性能效率都是通过实际基准测试结果进行对比的。但是唯一美中不足的是对于Kotlin中哪种场景下使用sequence更好,并没有说的很清楚。关于这点我想补充一下:

  • 1、数据集量级是足够大,建议使用序列(Sequences)
  • 2、对数据集进行频繁的数据操作,类似于多个操作符链式操作,建议使用序列(Sequences)
  • 3、对于使用first{},last{}建议使用序列(Sequences)。补充一下,细心的小伙伴会发现当你对一个集合使用first{},last{}操作符的时候,我们IDE工具会提示你建议使用序列(Sequences) 代替 集合(Lists)
  • 4、当仅仅只有map操作时,使用sequence

这里只是简单总结了几点,具体详细内容可参考之前三篇有关Kotlin中序列的文章。好了第四篇完美收工。

Kotlin系列文章,欢迎查看:

Effective Kotlin翻译系列

原创系列:

翻译系列:

实战系列:

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

关注下面的标签,发现更多相似文章
评论