scala - 编写性能 scala 不可变集合

Question

快速提问。我目前正在设计一些数据库查询来将相当大但不是海量的数据集提取到内存中，比如大约 10k-100k 记录。

到目前为止，我一直在测试将这些结果集加载到 scala.collection.immutable.Seq 中，并发现构建集合似乎需要很长时间。而如果我更改为 Vector 或 List，则写入内存需要几分之一秒的时间。

因此，我的问题是为什么 Seq 在这种情况下如此缓慢？如果是这样，在什么情况下使用 Seq 比使用 Vector 更合适？

谢谢

Answer 1

如果您发布相关代码段以及您对序列调用哪些操作会有所帮助 - immutable.Seq 使用 List 表示(请参阅 https://github.com/scala/scala/blob/v2.10.2/src/library/scala/collection/immutable/Seq.scala#L42 )。我的猜测是你一直在 :+ 上使用 immutable.Seq ，它通过复制它(可能会给你二次整体性能)附加到列表的末尾，当你切换到直接使用 immutable.List 时，你已经使用 :: 附加到开头(为您提供线性性能)。

由于 Seq 只是引擎盖下的 List，因此您应该在附加到序列的开头时使用它——cons 运算符 :: 仅创建一个节点并将其链接到列表的其余部分，这与它一样快当涉及到不可变的数据结构时，可以获得。否则，如果您添加到最后，并且您坚持不变性，则应该使用 Vector(或即将推出的 Conc 列表!)。

如果您想验证这些声明，请参阅此 link，其中使用 ScalaMeter 比较了两个操作的性能——当您添加到开头时，列表比向量快 8 倍。

但是，最合适的数据结构应该是 ArrayBuffer 或 VectorBuilder 。这些是动态调整大小的可变数据结构，如果您使用 += 构建它们，您将获得合理的性能。这是假设您没有存储原语。