Scala的向量分支因子为32,而不是其他数字的原因是什么？小分支因素不会实现更多的结构共享吗？ Clojure似乎使用相同的分支因子.我错过了分支因子32有什么神奇之处吗？
如果你解释了分支因素是什么会有所帮助：
树或图的分支因子是每个节点处的子节点数.
所以,答案似乎主要在这里：
http://www.scala-lang.org/docu/files/collections-api/collections_15.html
Vectors are represented as trees with a high branching factor. Every
tree node contains up to 32 elements of the vector or contains up to
32 other tree nodes. Vectors with up to 32 elements can be represented
in a single node. Vectors with up to 32 * 32 = 1024 elements can be
represented with a single indirection. Two hops from the root of the
tree to the final element node are sufficient for vectors with up to
215 elements,three hops for vectors with 220,four hops for vectors
with 225 elements and five hops for vectors with up to 230 elements.
So for all vectors of reasonable size,an element selection involves
up to 5 primitive array selections. This is what we meant when we
wrote that element access is “effectively constant time”.
因此,基本上,他们必须就每个节点有多少孩子做出设计决定.正如他们解释的那样,32似乎是合理的,但是,如果你发现它对你来说太严格了,那么你总是可以写自己的班级.
有关为什么它可能是32的更多信息,你可以看一下这篇论文,就像它们在上面做出相同陈述的介绍一样,关于它几乎是不变的时间,但是这篇论文看起来比看起来更像是Scala.
http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
