爲什麼矢量這麼淺？

Question

斯卡拉矢量的分支因子是32，而不是其他數字的基本原理是什麼？不會有更小的分支因素能夠實現更多的結構共享？ Clojure似乎使用相同的分支因子。對於我缺少的分支因子32有什麼魔力嗎？

Answer 1

如果你解釋什麼是分支因素是這將有助於：

樹或圖的分支因子是在每個節點的兒童人數。

所以，答案似乎是主要的位置：

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

向量表示爲高支因素的樹木。每個 樹節點最多包含32個矢量元素或最多包含32個其他樹節點。具有多達32個元素的矢量可以在單個節點中被表示爲 。具有高達32×32 = 1024個元素的矢量可以是用單個間接表示的 。從 樹對於最終元件節點的根兩個跳足以向量與多達元素，三個跳數向量與2 ，四個跳數矢量 2個^25個元件和具有多達2 元素的載體的五跳。 因此，對於合理大小的所有矢量，元素選擇涉及最多5個基元數組選擇。這就是我們的意思，當我們 寫道元素訪問是「有效的恆定時間」。

所以，基本上，他們必須做出一個設計決定，每個節點有多少個孩子。正如他們解釋的那樣，32似乎是合理的，但是，如果你發現它對你來說太嚴格了，那麼你總可以寫自己的課。

想了解更多關於它爲什麼可能是32的信息，可以看看這篇論文，就像他們在上面介紹的那樣，他們做了與上面相同的陳述，關於它幾乎是恆定的時間，但是這篇論文似乎涉及Clojure，超過斯卡拉。

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

Answer 2

這是 「有效恆定的時間」 進行更新。有了這麼大的分支因子，即使是TB級向量，也不會超過5級。這裏有一段視頻，Rich在第9頻道討論Clojure和其他方面的內容。http://channel9.msdn.com/Shows/Going+Deep/Expert-to-Expert-Rich-Hickey-and-Brian-Beckman-Inside-Clojure

Answer 3

James Black的回答是正確的。選擇32個項目的另一個參數可能是許多現代處理器中的高速緩存行大小爲64字節，因此兩行可以保持32個整數，每個4個字節，或者32位機器上的32個指針或堆大小最大爲64位的JVM 32GB由於指針壓縮。

Answer 4

只是給詹姆斯的答案增加一點點。

從算法分析的角度來看，因爲兩個函數的增長是對數的，所以它們以相同的方式進行縮放。

但是，在實際應用中，有 跳的跳變比，也就是說，基地2的數量少得多，足以使其保持它更接近於固定的時間，即使是N的相當大的值

由於某些內存塊大小，我確定他們確實選擇了32個（而不是更高的數字），但主要原因是與較小的大小相比，跳數較少。

我還建議你看相關的此演示文稿，其中丹尼爾Spiewak討論向量開始約30分鐘：http://www.infoq.com/presentations/Functional-Data-Structures-in-Scala