附加向量的效率

Question

将元素附加到百万元素上会产生ArrayList现在设置一个引用的成本,并且在ArrayList必须调整大小时将来复制一个引用.

据我所知,追加的元件到百万元件PersistenVector必须创建一个新的路径,其由4个阵列大小32的这意味着超过120名的引用必须触碰的.

Clojure如何设法将矢量开销保持在"2.5倍差"或"4倍差"(而不是"差60倍"),这在我最近看过的几个Clojure视频中已经声明了？它与缓存或引用的位置或我不知道的东西有关吗？

或者它是否有可能在内部构建带有变异的载体,然后在将其暴露给外部世界之前将其变为不可变的？

我也标记了scala这个问题,因为scala.collection.immutable.vector基本上是一样的,对吧？

Answer 1

Clojure的PersistentVector具有特殊的尾部缓冲区,可以在向量的末尾实现高效操作.只有在填充了这个32元素数组之后,才会将其添加到树的其余部分.这使摊销成本保持在较低水平.这是一篇关于实施的文章.该源也值得一读.

关于,"在某种程度上是否有可能在内部构建带有变异的载体,然后在向外界揭示它之前将其变为不可变？",是的!这些在Clojure 中称为瞬变,用于有效的批量更改.

Answer 2

不能讲述Clojure,但我可以对Scala Vectors做一些评论.

持久性的Scala载体(scala.collection.immutable.VectorS)的多比阵列缓冲慢,当涉及到追加.实际上,它们比List前置操作慢10倍.它们比追加到我们在并行集合中使用的Conc-tree慢2倍.

但是,Scala也有可变的向量 - 它们隐藏在课堂上VectorBuilder.附加到可变向量不会保留向量的先前版本,而是通过将指针保持在向量中最右边的叶子来使其变异.所以,是的 - 在内部保持向量可变,而不是返回不可变引用正是在Scala集合中完成的.

该VectorBuilder比稍快ArrayBuffer,因为它需要一次分配的阵列,而ArrayBuffer需要做两次平均(因为越来越多的).Conc.Buffer我们用作并行阵列组合器的VectorBuilders的速度是s的两倍.

基准在这里.没有任何基准涉及任何拳击,它们与参考对象一起使用以避免任何偏见:

这里有更多的收藏基准.

这些测试使用ScalaMeter执行.