编写性能scala不可变集合

Question

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

到目前为止,我一直在测试将这些结果集加载到scala.collection.immutable.Seq中,并发现它似乎花费了相当长的时间来构建集合.然而,如果我更改为Vector或List,则写入内存只需几分之一秒.

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

谢谢

Answer 1

如果您发布相关片段以及您在序列上调用哪些操作,将会有所帮助 - immutable.Seq使用a表示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列表!).

如果您想要验证这些声明,请参阅此链接,其中使用ScalaMeter比较两个操作的性能 - 当您添加到开头时,列表比矢量快8倍.

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