Warum sind Vektoren so flach?
Was ist der Grund dafür, dass die Vektoren von Scala einen Verzweigungsfaktor von 32 haben und nicht irgendeine andere Zahl? Würden nicht kleinere Verzweigungsfaktoren mehr strukturelles Teilen ermöglichen? Clojure scheint den gleichen Verzweigungsfaktor zu verwenden. Gibt es irgendetwas Magisches an dem Verzweigungsfaktor 32, den ich vermisse?
4 Antworten
Es würde helfen, wenn Sie erklären würden, was ein Verzweigungsfaktor ist:
Der Verzweigungsfaktor eines Baums oder eines Graphen ist die Anzahl der untergeordneten Elemente an jedem Knoten.
Also, die Antwort scheint weitgehend hier zu sein:
Vektoren werden als Bäume mit einem hohen Verzweigungsfaktor dargestellt. Jeden Der Baumknoten enthält bis zu 32 Elemente des Vektors oder enthält bis zu 32 andere Baumknoten. Vektoren mit bis zu 32 Elementen können dargestellt werden in einem einzelnen Knoten. Vektoren mit bis zu 32 * 32 = 1024 Elementen können sein mit einer einzigen Indirektion dargestellt. Zwei Hopfen aus der Wurzel der Baum für den letzten Elementknoten sind ausreichend für Vektoren mit bis zu 2 15 Elemente, drei Hops für Vektoren mit 2 20 , vier Hops für Vektoren mit 2 25 Elementen und fünf Hops für Vektoren mit bis zu 2 30 Elementen. Also für alle Vektoren von vernünftiger Größe beinhaltet eine Elementauswahl bis zu 5 primitive Array-Auswahlen Das haben wir gemeint, als wir schrieb, dass Elementzugriff "effektiv konstante Zeit" ist.
Also mussten sie im Grunde eine Designentscheidung treffen, wie viele Kinder an jedem Knoten haben. Wie sie erklärten, 32 schien vernünftig, aber, wenn Sie finden, dass es für Sie zu einschränkend ist, könnten Sie immer Ihre eigene Klasse schreiben.
Für weitere Informationen darüber, warum es 32 gewesen sein könnte, können Sie sich dieses Papier ansehen, da sie in der Einleitung die gleiche Aussage wie oben machen, es ist fast konstante Zeit, aber diese Arbeit befasst sich mit Clojure, es scheint, mehr als Scala.
James Blacks Antwort ist richtig. Ein anderes Argument für die Auswahl von 32 Elementen könnte sein, dass die Cache-Zeilengröße in vielen modernen Prozessoren 64 Byte beträgt. Daher können zwei Zeilen 32 Ints mit je 4 Byte oder 32 Zeiger auf einer 32-Bit-Maschine oder eine 64-Bit-JVM mit einer Heap-Größe von bis zu enthalten 32GB wegen der Zeigerkomprimierung.
Es ist die "effektiv konstante Zeit" für Updates. Mit diesem großen Verzweigungsfaktor müssen Sie niemals über 5 Ebenen hinausgehen, selbst nicht für Terabyte-Vektoren. Hier ist ein Video mit Rich darüber und anderen Aspekten von Clojure auf Channel 9. Brian-Beckman-Inside-Clojure "> Ссылка
Fügen Sie James 'Antwort nur ein bisschen hinzu.
Vom Standpunkt der Algorithmusanalyse aus gesehen, 
weil das Wachstum der beiden Funktionen logarithmisch ist, so skalieren sie auf die gleiche Weise. p>
Aber in praktischen Anwendungen haben
Hops ist eine viel kleinere Anzahl von Hops als, sagen wir, Base 2, ausreichend, so dass es näher an der konstanten Zeit bleibt, sogar für ziemlich große Werte von N.
Ich bin sicher, dass sie wegen einer Speicherblockgröße genau 32 (im Gegensatz zu einer höheren Zahl) gewählt haben, aber der Hauptgrund ist die geringere Anzahl von Hops im Vergleich zu kleineren Größen.
Ich empfehle Ihnen auch, diese Präsentation auf InfoQ zu sehen, wo Daniel Spiewak über Vektoren spricht, die ungefähr 30 Minuten in: Ссылка
Tags und Links scala clojure vector tree collections