Kotlin:为什么在这个例子中Sequence更具性能？

Question

目前,我正在研究Kotlin并对序列与收藏有疑问.

我读了一篇关于这个主题的博客文章,在那里你可以找到这段代码片段:

清单实施:

val list = generateSequence(1) { it + 1 }
    .take(50_000_000)
    .toList()

measure {
    list
        .filter { it % 3 == 0 }
        .average()
}
// 8644 ms

顺序实施:

val sequence = generateSequence(1) { it + 1 }
    .take(50_000_000)

measure {
    sequence
        .filter { it % 3 == 0 }
        .average()
}
// 822 ms

这里的要点是Sequence实现速度提高了大约10倍.

但是,我真的不明白为什么.我知道使用序列,你做"懒惰评估",但我找不到任何理由,这有助于减少此示例中的处理.

但是,在这里我知道为什么序列通常更快:

val result = sequenceOf("a", "b", "c")
    .map {
        println("map: $it")
        it.toUpperCase()
    }
    .any {
        println("any: $it")
        it.startsWith("B")
    }

因为使用Sequence可以"垂直"处理数据,所以当第一个元素以"B"开头时,您不必映射其余元素.这里有道理.

那么,为什么在第一个例子中它也更快？

Answer 1

让我们看看这两个实现实际上在做什么:

1. List实现首先List在内存中创建了5000万个元素.这将至少需要200MB,因为整数需要4个字节.

   (事实上​​,它可能远不止于此.正如Alexey Romanov指出的那样,因为它是一个通用的List实现而不是一个IntList,它不会直接存储整数,而是"装箱"它们 - 存储Int对象的引用.在JVM中,每个引用可以是8或16个字节,每个引用可以Int占用16个,占用1-2GB.此外,根据List创建的方式,它可能从一个小数组开始,随着列表的增长继续创建越来越大的数组,每次使用更多内存复制所有值.)

   然后它必须从列表中读回所有值,过滤它们,并在内存中创建另一个列表.

   最后,它必须再次读回所有这些值,以计算平均值.

2. 另一方面,Sequence实现不需要存储任何东西!它只是按顺序生成值,并且每个都检查它是否可以被3整除,如果可以,则将其包含在平均值中.

   (如果你手动实现它,那就是你如何做到这一点.)

您可以看到,除了可分性检查和平均计算之外,List实现正在进行大量的内存访问,这将花费大量时间.  这是它比Sequence版本慢得多的主要原因,而不是!

看到这个,你可能会问为什么我们不在任何地方使用Sequences ......但这是一个相当极端的例子.设置然后迭代序列有一些自己的开销,对于可能超过内存开销的小型列表.所以序列只有在案件具有明显的优势,当列表是非常大的,是为了严格处理,有几个中间步骤,和/或多个项目沿途过滤掉(尤其是如果序列是无限的!).

根据我的经验,这些情况并不经常发生.但这个问题表明,当他们这样做时,识别它们是多么重要!