Scala向量中的结构共享

Question

Scala中的结构共享List非常简单易懂.但Scala Vector是一个比列表更复杂的数据结构.如何在Scala中实现结构共享Vector？

Answer 1

Vector基本上是一个树(trie),每个级别有32个分支.如果你有一个Vector,比如3000个元素,并且你想索引元素2045,例如,它转换为100000010101二进制,它会将它分解为5位块,用作树中的索引:( 10即2)in第一个分支然后00000(即0)在下一个,最后10101(即21)在终端分支中,然后是数据.

鉴于这种结构,很容易看出如何在结构上共享内容:您可以共享任何未更改的子树.因此,如果使用不同的元素2045创建一个新向量,则必须更改并非所有3000个元素,而是重新创建"仅"三个大小为32的数组:终端一被替换为更新元素21的副本; 那么它的父母必须被索引0中这个新孩子的副本所取代; 然后必须用索引2中的正确子树替换其父级.

现在,只要你的向量中有超过32个元素,这就提供了相当多的结构共享,但它仍然是一个相当大的开销.因此,向量末尾的添加是特殊的,因此您只需添加到现有数组.旧的Vector仍然指向那个数组,但是他们认为结束时间较早(并且该部分没有变化)所以它可以正常工作.

有一个更复杂但相似的方案允许以类似的方式在向量的前面添加(基本上,通过在前面留下空间并通过索引和偏移除了索引方案来跟踪指向的位置).

然而,实现的技巧不能允许交替添加正面和背面,因此您可以在每次添加时有效地重建树.制作具有更好结构共享的版本是可能的,但访问可能会慢一些.