Scala的Vector是如何工作的？

Question

Scala的Vector是如何工作的？

scaladata-structures

35

我阅读了关于Scala集合时间复杂度的这篇文章，正如所说，Vector的复杂度在所有操作中都是eC。

这让我想知道Vector是什么。我读了文档，它说：

因为向量在快速随机选择和快速随机功能更新之间取得了良好的平衡，所以它们目前是不可变索引序列的默认实现。它由分支因子为32的小端位图向量字典树支持。局部性很好，但不是连续的，这对于非常大的序列很有用。

与Scala的其他方面一样，它相当模糊。 Vector实际上是如何工作的？

- Lai Yu-Hsuan

1

继续你的陈述，就像Scala的其他方面一样，你对Scala的Vector的问题也非常模糊。你想听关于向量的什么？高层次的描述已经很好了，如果想了解低层次的细节，最好查看源代码（https://github.com/scala/scala/blob/v2.10.3/src/library/scala/collection/immutable/Vector.scala#L1）。 - om-nom-nom

3

再者，如果他想知道底层使用了哪种数据结构，源代码就帮不上太多忙了（因为注释很少），你基本上需要已经掌握算法和数据结构才能从中得到有意义的信息。 - Régis Jean-Gilles

1

实际上，这相当具有描述性。使用分支因子为32的位图矢量字典树实现的方法并不多。也许可以补充说明“变异”元素会创建从元素到根节点直接线路上数组的副本，但除了源代码（当然是可用的）之外，真的没有太多可以说的了。 - Daniel C. Sobral

当前文档（2.13.6）表示：“向量是由宽度为32的基数平衡指树实现的。” - W. Zhu

3个回答

19

其他关于“Trie”的回答已经很好了。但是为了快速理解，这里提供一个接近的近似值：

向量（Vector）在内部使用一种树形结构——不是二叉树，而是32元树
每个“32路节点”使用Array[32]，可以存储0-32个子节点的引用或0-32个数据片段
树被结构化为某种平衡方式——它是“n”级深度，但级别1到n-1是仅包含索引的级别（100%子引用；无数据），级别n包含所有数据（100%数据；没有子引用）。因此，如果数据元素数量为“d”，则n = log-base-32(d)向上取整

为什么要这样呢？简单：为了性能。

与为每个单独的数据元素分配数千/数百万/数十亿次内存分配不同，内存是以32个元素块为单位分配的。与直接查找数据时要向下遍历很深的树相比，该结构非常浅——是一棵非常宽、短的树。例如，深度为5的树可以包含32^5个数据元素（对于4字节元素=132GB，即相当大），每个数据访问将从根节点查找并遍历5个节点（而大型数组将使用单个数据访问）。向量不会主动为所有n级（数据）分配内存，而是按需要以32个元素块为单位分配。它提供了类似于巨大数组的读取性能，同时具有类似于二叉树的功能特性（功率、灵活性和内存效率）。

:)

- Glen Best

1

你能同时描述一下它如何实现“eC”的追加/前置吗？ - Tvaroh

8

以下内容可能对您有所帮助：

- sourcedelica

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Régis Jean-Gilles · Accepted Answer

关键字是 Trie。向量被实现为一个 Trie 数据结构。请参见 http://en.wikipedia.org/wiki/Trie。

更准确地说，它是一种“位图向量 trie”。我在这里找到了一个足够简明的描述（似乎是用 Rust 实现的）： https://bitbucket.org/astrieanna/bitmapped-vector-trie 最相关的摘录是：

位图向量 trie 基本上是一个 32 树。第 1 层是大小为 32 的数组，数组元素可以是任何数据类型。第 2 层是大小为 32 的第 1 层的数组。以此类推，直到第 7 层是大小为 2 的第 6 层的数组。

更新：回复 Lai Yu-Hsuan 关于复杂度的评论：

我得假设你这里是指“深度” :-D。对于 "eC" 的说明说："该操作所需时间基本上是固定的，但这可能取决于某些假设，例如向量的最大长度或哈希键的分布。"

如果你能考虑到最坏情况，并假设向量的最大尺寸有一个上限，那么我们确实可以说复杂度是常数的。假设最大尺寸为 2^32，则任何情况下最多只需要 7 次操作。另一方面，我们总是可以为任何类型的集合考虑最坏情况，找到一个上限，并说这是常数复杂度，但对于列表来说，这意味着常数为 40 亿，这不太实用。

但向量相反，7 次操作足够实用，这就是我们可以认为它的复杂度在实践中是常数的原因。

另一个角度来看：我们正在谈论的不是log(2,N)，而是log(32,N)。如果你尝试绘制它，你会发现它几乎是一条水平线。因此从实用的角度来说，随着集合的增长，处理时间的增加将很难被察觉。

是的，这仍然不是真正的常数（这就是为什么它标记为“eC”而不仅仅是“C”），在较短的向量周围你将能够看到差异（但再次说明，由于操作数量增长缓慢，这种差异非常小）。