Qual è la logica dei vettori di Scala che hanno un fattore di ramificazione di 32 e non un altro numero? I fattori di ramificazione più piccoli non consentirebbero una condivisione più strutturale? Clojure sembra utilizzare lo stesso fattore di ramificazione. C'è qualcosa di magico nel fattore di ramificazione 32 che mi manca?Perché i vettori sono così poco profondi?
Sarebbe utile se lei ha spiegato quello che un fattore di ramificazione è:
Il fattore di ramificazione di un albero o un grafico è il numero di bambini in ogni nodo.
Quindi, la risposta sembra essere in gran parte qui:
http://www.scala-lang.org/docu/files/collections-api/collections_15.html
vettori sono rappresentati come alberi con un alto fattore di ramificazione. Ogni nodo dell'albero contiene fino a 32 elementi del vettore o contiene fino a 32 altri nodi dell'albero. I vettori con un massimo di 32 elementi possono essere rappresentati in un singolo nodo. I vettori con un massimo di 32 * 32 = 1024 elementi possono essere rappresentati con una singola indiretta. Due luppolo dalla radice del albero al nodo elemento finale sono sufficienti per vettori fino a elementi, tre luppolo per vettori con 2 , quattro luppolo per vettori con 2 elementi e cinque hop per vettori con un massimo di 2 elementi. Quindi per tutti i vettori di dimensioni ragionevoli, una selezione di elementi coinvolge fino a 5 selezioni di array primitive. Questo è ciò che intendevamo quando abbiamo scritto che l'accesso agli elementi è "tempo effettivamente costante".
Quindi, in pratica, hanno dovuto prendere una decisione di progettazione sul numero di figli da avere in ogni nodo. Come hanno spiegato, 32 sembra ragionevole, ma, se trovi che è troppo restrittivo per te, allora potresti sempre scrivere la tua classe.
Per ulteriori informazioni sul motivo per cui potrebbe essere stato 32, è possibile guardare questo documento, come nell'introduzione fanno la stessa dichiarazione di cui sopra, a proposito che è quasi costante, ma questo articolo si occupa di Clojure sembra, più di Scala.
Sentiti libero di modificare la mia domanda per migliorare la chiarezza. – fredoverflow
E 'il "tempo in modo efficace costante" per gli aggiornamenti. Con quel grande fattore di ramificazione, non devi mai andare oltre i 5 livelli, anche per i vettori in scala terabyte. Ecco un video con Rich parlando di questo e altri aspetti di Clojure su Canale 9. http://channel9.msdn.com/Shows/Going+Deep/Expert-to-Expert-Rich-Hickey-and-Brian-Beckman-Inside-Clojure
La risposta di James Black è corretta. Un altro argomento per la scelta di 32 elementi potrebbe essere che la dimensione della linea cache in molti processori moderni è 64 byte, quindi due righe possono contenere 32 inte con 4 byte ciascuna o 32 puntatori su una macchina a 32 bit o una JVM a 64 bit con una dimensione heap fino a 32 GB a causa della compressione del puntatore.
Eliminato ora il commento, per evitare ridondanze. –
La riga della cache moderna è 64 byte. I processori Intel più recenti e nuovissimi possono avere solo 128 byte. – Puppy
Basta aggiungere un po 'alla risposta di James.
Da un punto di vista di analisi dell'algoritmo, 
poiché la crescita delle due funzioni è logaritmica, pertanto vengono ridimensionate allo stesso modo.
Ma, nelle applicazioni pratiche, avente 
luppolo è un numero molto inferiore di luppolo rispetto, ad esempio, la base 2, in modo sufficiente che mantiene più vicino a costante di tempo, anche per abbastanza grandi valori di N.
Sono sicuro che hanno scelto 32 esattamente (a differenza di un numero più alto) a causa di alcune dimensioni del blocco di memoria, ma il motivo principale è il minor numero di hop, rispetto alle dimensioni più piccole.
vi consiglio anche di guardare questa presentazione su InfoQ, dove Daniel Spiewak discute vettori di partenza circa 30 minuti in: http://www.infoq.com/presentations/Functional-Data-Structures-in-Scala
Do la colpa dei media mainstream. – Shmiddty
Trolltember al suo culmine. – rlemon