2012-09-17 40 views
7

¿Cuál es el razonamiento detrás de los vectores de Scala que tienen un factor de bifurcación de 32, y no algún otro número? ¿No permitirían los factores de ramificación más pequeños un mayor intercambio estructural? Clojure parece usar el mismo factor de ramificación. ¿Hay algo mágico en el factor de ramificación 32 que me falta?¿Por qué los vectores son tan superficiales?

+7

culpo a los medios de comunicación. – Shmiddty

+0

Trolltember en su máxima expresión. – rlemon

Respuesta

13

Sería de gran ayuda si usted explicó lo que es un factor de ramificación es:

El factor de ramificación de un árbol o un gráfico es el número de niños en cada nodo.

Por lo tanto, la respuesta parece ser en gran parte aquí:

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

vectores se representan como los árboles con un alto factor de ramificación. Cada nodo de árbol contiene hasta 32 elementos del vector o contiene hasta 32 otros nodos de árbol. Los vectores con hasta 32 elementos se pueden representar en un solo nodo. Los vectores con hasta 32 * 32 = 1024 elementos pueden ser representados con un único direccionamiento indirecto. Dos saltos desde la raíz del árbol al nodo de elemento final son suficientes para los vectores con hasta elementos, tres saltos para vectores con 2 , cuatro saltos para vectores con 2 elementos y cinco saltos para vectores con hasta 2 elementos. Entonces, para todos los vectores de tamaño razonable, la selección de un elemento implica hasta 5 selecciones de matriz primitiva. Esto es lo que quería decir cuando escribimos que el acceso a los elementos es "efectivamente tiempo constante".

Así que, básicamente, tenían que tomar una decisión de diseño sobre cuántos niños tener en cada nodo. Como explicaron, 32 parecía razonable, pero, si considera que es demasiado restrictivo para usted, entonces siempre podría escribir su propia clase.

Para obtener más información sobre por qué puede haber sido 32, puede mirar este documento, ya que en la introducción hacen la misma afirmación que antes, sobre el tiempo casi constante, pero este documento trata sobre Clojure, parece más que Scala.

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

+0

No dude en editar mi pregunta para mejorar la claridad. – fredoverflow

8

La respuesta de James Black es correcta. Otro argumento para elegir 32 elementos podría ser que el tamaño de la línea de caché en muchos procesadores modernos es de 64 bytes, por lo que dos líneas pueden contener 32 entradas con 4 bytes cada una o 32 punteros en una máquina de 32 bits o una JVM de 64 bits con un tamaño de almacenamiento dinámico hasta 32 GB debido a la compresión del puntero.

+0

Eliminado el comentario ahora, para evitar redundancia. –

+0

La línea de caché moderna es de 64bytes. Los procesadores más nuevos y más recientes de Intel solo pueden tener 128 bytes. – Puppy

4

Simplemente agregando un poco a la respuesta de James.

Desde un punto de vista de análisis de algoritmo, http://www.texify.com/img/%5CLARGE%5C%21O%28log%20_b%20%28N%29%29%20%3D%20O%28log%20_k%20%28N%29%29.gif porque el crecimiento de las dos funciones es logarítmico, por lo que se escalan de la misma manera.

embargo, en aplicaciones prácticas, teniendo enter image description here saltos es un número mucho más pequeño de saltos que, por ejemplo, la base 2, lo suficiente para que lo mantiene más cerca de constante de tiempo, incluso para valores bastante grandes de N.

Estoy seguro de que seleccionaron 32 exactamente (a diferencia de un número mayor) debido a algún tamaño de bloque de memoria, pero la razón principal es la menor cantidad de saltos, en comparación con los tamaños más pequeños.

También recomendamos que vea este presentación sobre InfoQ, donde Daniel Spiewak discute vectores a partir de unos 30 minutos en: http://www.infoq.com/presentations/Functional-Data-Structures-in-Scala

Cuestiones relacionadas