Scala 的向量的分支因子为 32 而不是其他数字的基本原理是什么？较小的分支因子不会实现更多的结构共享吗？Clojure 似乎使用相同的分支因子。我缺少的分支因子 32 有什么神奇之处吗？
问问题
456 次
4 回答
13
如果您解释什么是分支因子会有所帮助：
树或图的分支因子是每个节点的子节点数。
因此，答案似乎主要在这里：
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 的更多信息，您可以查看这篇论文，因为在介绍中他们做了与上面相同的声明，关于它几乎是恒定的时间，但这篇论文似乎更多地处理 Clojure，而不是 Scala。
于 2012-09-17T16:45:42.560 回答
8
詹姆斯布莱克的回答是正确的。选择 32 项的另一个论据可能是，许多现代处理器中的高速缓存行大小为 64 字节，因此在 32 位机器或 64 位 JVM 上，两行可以容纳 32 个整数，每个 4 字节，或 32 个指针，堆大小高达32GB 由于指针压缩。
于 2012-09-17T16:58:09.300 回答
4
这是更新的“有效恒定时间”。有了这么大的分支因子，您永远不必超过 5 个级别，即使是 TB 级的向量也是如此。这是 Rich 在第 9 频道上谈论 Clojure 的其他方面的视频。http ://channel9.msdn.com/Shows/Going+Deep/Expert-to-Expert-Rich-Hickey-and-Brian-Beckman-Inside -Clojure
于 2012-09-17T16:47:59.267 回答
4
只是在詹姆斯的回答中添加一点。
从算法分析的角度来看，
因为这两个函数的增长是对数的，所以它们的缩放方式相同。
但是，在实际应用中，与
例如以 2 为基数相比，具有跳数的跳数要少得多，足以使其更接近于恒定时间，即使对于相当大的 N 值也是如此。
我敢肯定，由于某些内存块大小，他们准确地选择了 32 个（而不是更高的数字），但主要原因是与较小的大小相比，跳数较少。
我还建议您在 InfoQ 上观看此演示文稿，Daniel Spiewak 从大约 30 分钟开始讨论 Vectors：http: //www.infoq.com/presentations/Functional-Data-Structures-in-Scala
于 2012-09-17T17:06:12.917 回答