位图矢量如何比普通矢量快？
Meh*_*dad 18 jvm functional-programming scala clojure data-structures
它应该比矢量更快,但我真的不明白引用的局部性应该如何帮助它(因为矢量根据定义是最可能的本地打包数据 - 每个元素都打包在后续元素旁边,没有额外的空间).
基准测试是假定特定的使用模式还是类似的？
这怎么可能？
mik*_*era 11
位图矢量尝试并不比正常矢量快,至少不是一切.这取决于您正在考虑的操作.
例如,常规向量在访问特定索引处的数据元素时更快.直接索引数组查找很难打败.从缓存局部性的角度来看,如果您所做的只是按顺序循环遍历大数组,那么大数组就非常好.
然而,位图矢量trie对于其他操作将更快(由于结构共享) - 例如,创建具有单个更改元素的新副本而不影响原始数据结构是O(log32 n)与O(n)对于传统的矢量.这是一个巨大的胜利.
这是一个很好的视频非常值得关注这个主题,其中包括为什么你可能需要这种结构的动机:持久性数据结构和托管引用(由Rich Hickey讲话).
- 当你对非常大的数据进行随机访问时,我认为它胜过ArrayList. (3认同)
nic*_*kik 10
在其他答案中有很多好东西,但是nobdy回答了你的问题.PersistenVectors只能通过索引快速进行大量随机查找(当数组较大时)."怎么可能？" 你可能会问."普通的平面阵列只需要移动指针,PersistentVector必须经过多个步骤."
答案是"缓存局部性".
缓存总是从内存中获取范围.如果你有一个大数组,它不适合缓存.因此,如果要获取项目x和项目y,则必须重新加载整个缓存.那是因为数组总是在内存中是连续的.
现在与PVector不同.周围有许多小型数组,JVM很聪明,并且它们在内存中彼此靠近.所以对于随机访问,这很快; 如果你按顺序执行它会慢得多.
我不得不说我不是硬件方面的专家或者JVM如何处理缓存局部性而且我自己从未对此进行过基准测试; 我只是在重述我从其他人那里听到的东西:)
编辑:迈克拉也提到了这一点.
编辑2:请参阅有关功能数据结构的讨论,如果您只对矢量感兴趣,请跳到最后一部分.http://www.infoq.com/presentations/Functional-Data-Structures-in-Scala
位图矢量trie(又名持久矢量)是Rich Hickey为Clojure发明的数据结构,自2010年以来已在Scala中实现(v 2.8).它是一种巧妙的按位索引策略,可以高效地访问和修改大型数据集.
可变向量和ArrayLists通常只是在需要时增长和缩小的数组.当你想要可变性时,这很有用,但是当你需要持久性时,这是一个很大的问题.你会得到缓慢的修改操作,因为你必须一直复制整个数组,并且会占用大量内存.在查找值以及快速操作时,以某种方式尽可能避免冗余而不损失性能将是理想的.这正是Clojure的持久向量所做的,它是通过平衡的有序树来完成的.
这个想法是实现一个类似于二叉树的结构.唯一的区别是树中的内部节点最多有两个子节点,并且本身不包含任何元素.叶节点最多包含两个元素.元素按顺序排列,这意味着第一个元素是最左边叶子中的第一个元素,最后一个元素是最右边叶子中最右边的元素.目前,我们要求所有叶节点都处于相同的深度2.举个例子,看一下下面的树:它有0到8的整数,其中0是第一个元素,8是最后一个元素.数字9是矢量大小:
如果我们想在这个向量的末尾添加一个新元素并且我们处于可变世界中,我们将在最右边的叶节点中插入9,如下所示:
但问题在于:如果我们想坚持下去,我们就不能这样做.如果我们想要更新元素,这显然不会起作用!我们需要复制整个结构,或至少部分结构.
为了在保留完全持久性的同时最小化复制,我们执行路径复制:我们将路径上的所有节点复制到我们即将更新或插入的值,并在我们位于底部时将值替换为新值.多次插入的结果如下所示.这里,具有7个元素的向量与具有10个元素的向量共享结构:
粉红色的节点在矢量之间共享,而棕色和蓝色是分开的.未可视化的其他矢量也可以与这些矢量共享节点.
更多信息
除了了解Clojure的持久向量之外,这个数据结构及其用例背后的想法也在David Nolen 2014年讲座Immutability,interactiveity和JavaScript中得到了很好的解释,下面是截图.或者,如果您真的想深入了解技术细节,请参阅Phil Bagwell的理想哈希树,这是Hickey最初的Clojure实现所依据的论文.
