scala - Scala的Vector如何工作？

Question

我读了有关scala集合的时间复杂性的this page。就像说的那样，Vector的复杂性是所有操作的eC。

这让我想知道Vector是什么。我读了document，上面写着:

Because vectors strike a good balance between fast random selections and fast random functional updates, they are currently the default implementation of immutable indexed sequences. It is backed by a little endian bit-mapped vector trie with a branching factor of 32. Locality is very good, but not contiguous, which is good for very large sequences.

与有关Scala的所有其他内容一样，它非常模糊。 Vector实际上如何工作？

Answer 1

此处的关键字是Trie。
vector 被实现为Trie数据结构。
参见http://en.wikipedia.org/wiki/Trie。

更准确地说，它是“位映射 vector 特里”。我刚刚在这里找到了足够简洁的结构描述(以及实现-显然在Rust中):

https://bitbucket.org/astrieanna/bitmapped-vector-trie

最相关的摘录是:

A Bitmapped Vector Trie is basically a 32-tree. Level 1 is an array of size 32, of whatever data type. Level 2 is an array of 32 Level 1's. and so on, until: Level 7 is an array of 2 Level 6's.

更新:回答赖 Jade 轩关于复杂性的评论:

我将不得不假设您的意思是“深度” :-D。图例中的“eC”表示“该操作实际上需要恒定的时间，但这可能取决于某些假设，例如 vector 的最大长度或哈希键的分布。”

如果您愿意考虑最坏的情况，并且考虑到 vector 的最大大小有上限，那么可以肯定地说，复杂度是恒定的。
假设我们认为最大大小为2 ^ 32，那么这意味着在任何情况下，最坏的情况是最多7个操作。
再说一次，我们总是可以考虑任何类型的集合的最坏情况，找到一个上限并说这是恒定的复杂性，但是对于一个列表，这意味着一个40亿的常数，这不太实际。

但是Vector是相反的，7个操作比实际要多，这就是我们可以负担得起的在实践中考虑其复杂性常数的方式。

另一种看待这种情况的方式是:我们不是在谈论log(2，N)，而是在谈论log(32，N)。如果您尝试绘制，将会看到它实际上是一条水平线。因此，务实地说，随着集合的增长，您将永远看不到处理时间的大幅增加。
是的，那仍然不是真正恒定的(这就是为什么将其标记为“eC”而不仅仅是“C”的原因)，并且您将能够看到短 vector 之间的差异(但同样，由于数字运营增长如此之慢)。