Jaka jest racjonalność wektorów Scala o współczynniku rozgałęzienia wynoszącym 32, a nie jakaś inna liczba? Czy mniejsze czynniki rozgałęzień nie umożliwią większego podziału strukturalnego? Clojure wydaje się używać tego samego czynnika rozgałęziania. Czy jest coś magicznego w związku z czynnikiem rozgałęzienia, którego mi brakuje?Dlaczego wektory są tak płytkie?
Byłoby pomóc, jeśli wyjaśnić co to jest współczynnik rozgałęzienia:
współczynnik rozgałęzienia drzewa lub wykresu jest liczba dzieci w każdym węźle.
Tak, odpowiedź wydaje się być w dużej mierze tutaj:
http://www.scala-lang.org/docu/files/collections-api/collections_15.html
Wektory są reprezentowane jako drzewa o wysokim współczynniku rozgałęzienia. Każdy węzeł drzewa zawiera do 32 elementów wektora lub zawiera do 31 innych węzłów drzewa. Wektory z maksymalnie 32 elementami mogą być reprezentowane w jednym węźle . Wektory z maksymalnie 32 * 32 = 1024 elementami mogą być reprezentowane pojedynczym kierunkiem. Dwa chmielu z korzenia drzewa do końcowego węzła elementu są wystarczające dla wektorów maksymalnie elementów, trzy chmielu wektory z 2 , cztery chmielu wektory z 2 elementów i pięć przeskoków dla wektorów z maksymalnie 2 elementów. Tak więc dla wszystkich wektorów o rozsądnym rozmiarze, wybór elementu obejmuje do 5 prymitywnych zbiorów macierzy. To właśnie mieliśmy na myśli, gdy napisał, że dostęp do elementu jest "efektywnie stały czas".
Tak więc, w zasadzie musieli podjąć decyzję projektową, ile dzieci mają mieć w każdym węźle. Jak wyjaśnili, 32 wydawało się rozsądne, ale jeśli uznasz, że jest to zbyt restrykcyjne, możesz zawsze napisać własną klasę.
Aby uzyskać więcej informacji o tym, dlaczego mogło to być 32, można spojrzeć na ten artykuł, jak we wstępie przedstawiają one to samo zdanie co powyżej, o tym, że jest to prawie stały czas, ale w tym artykule chodzi o Clojure, jak się wydaje, więcej niż Scala.
Zapraszam do edytowania mojego pytania w celu poprawy przejrzystości. – fredoverflow
To "skutecznie Stała czasowa" aktualizacji. Przy tak dużym współczynniku rozgałęzienia nigdy nie będziesz musiał przekraczać 5 poziomów, nawet dla wektorów o skali terabajtów. Oto film z Richem opowiadający o tym i innych aspektach Clojure na Channel 9. http://channel9.msdn.com/Shows/Going+Deep/Expert-to-Expert-Rich-Hickey-and-Brian-Beckman-Inside-Clojure
Odpowiedź Jamesa Blacka jest prawidłowa. Kolejnym argumentem przemawiającym za wyborem 32 elementów może być to, że rozmiar linii pamięci podręcznej w wielu nowoczesnych procesorach wynosi 64 bajty, więc dwie linie mogą pomieścić 32 węzły z 4 bajtami każdy lub 32 wskaźniki na maszynie 32-bitowej lub 64-bitowej maszynie JVM z rozmiarem sterty do 32 GB ze względu na kompresję wskaźnika.
Usunięto komentarz teraz, aby uniknąć nadmiarowości. –
Nowoczesna linia pamięci podręcznej ma 64 bajty. Najnowsze, najnowsze procesory Intela mogą mieć tylko 128 bajtów. – Puppy
Wystarczy dodać trochę do odpowiedzi Jamesa.
Z punktu widzenia analizy algorytmów, 
, ponieważ wzrost dwóch funkcji jest logarytmiczny, więc skaluje się w ten sam sposób.
Ale w zastosowaniach praktycznych, mający 
chmielu jest znacznie mniejsza liczba przeskoków niż, powiedzmy, podstawy 2, wystarczająco tak, że utrzymuje ją bliżej stałym czasie, nawet dla dość dużych wartości N.
Jestem pewien, że wybrali dokładnie 32 (w przeciwieństwie do większej liczby) z powodu pewnego rozmiaru bloku pamięci, ale głównym powodem jest mniejsza liczba przeskoków w porównaniu do mniejszych rozmiarów.
Polecam również obejrzeć tę prezentację na InfoQ, gdzie Daniel Śpiewak omawia wektory rozpoczynając około 30 minut w: http://www.infoq.com/presentations/Functional-Data-Structures-in-Scala
winię mediach głównego nurtu. – Shmiddty
Trolltember w najlepszym wydaniu. – rlemon