为什么矢量太浅？

Question

Scala的向量分支因子为32,而不是其他数字的原因是什么？小分支因素不会实现更多的结构共享吗？Clojure似乎使用相同的分支因子.我错过了分支因子32有什么神奇之处吗？

Answer 1

如果你解释了分支因素是什么会有所帮助:

树或图的分支因子是每个节点处的子节点数.

所以,答案似乎主要在于:

http://www.scala-lang.org/docu/files/collections-api/collections_15.html

载体表示为具有高分支因子的树.每个树节点最多包含32个向量元素或最多包含32个其他树节点.具有多达32个元素的向量可以在单个节点中表示.具有多达32*32 = 1024个元素的向量可以用单个间接表示.从树的根到最终元素节点的两跳足以用于具有多达2 ^15个元素的向量,用于具有2 ^20的向量的三个跃点,用于具有2 ^25个元素的向量的四个跃点以及用于具有高达2 ^30的向量的五个跃点.元素.因此,对于所有合理大小的向量,元素选择涉及最多5个基本数组选择.当我们写出元素访问是"有效的恒定时间"时,这就是我们的意思.

所以,基本上,他们必须做出设计决定,确定每个节点有多少孩子.正如他们所解释的那样,32似乎是合理的,但是,如果你发现它对你来说太严格了,那么你总是可以写自己的班级.

有关为什么它可能是32的更多信息,你可以看一下这篇论文,就像它们在上面做出的声明一样,关于它几乎是不变的时间,但是这篇论文似乎比Scala更多地处理了Clojure.

http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf

Answer 2

詹姆斯布莱克的回答是正确的.选择32项的另一个理由可能是许多现代处理器中的高速缓存行大小为64字节,因此两行可以容纳32个int,每个4字节或32位机器上的32个指针或64位JVM,堆大小最多为由于指针压缩,32GB.