superponer - ¿Cómo funciona el Vector de Scala?

superponer graficas en r

Question

Leí esta página sobre la complejidad del tiempo de las colecciones de Scala. Como se dice, la complejidad de Vector es eC para todas las operaciones.

Me hizo preguntarme qué es Vector . Leí el document y dice:

Debido a que los vectores tienen un buen equilibrio entre las selecciones aleatorias rápidas y las actualizaciones funcionales aleatorias rápidas, actualmente son la implementación predeterminada de las secuencias indexadas inmutables. Está respaldado por un pequeño vector trie endian de mapa de bits con un factor de bifurcación de 32. La ubicación es muy buena, pero no contigua, lo que es bueno para secuencias muy grandes.

Como con todo lo demás sobre Scala, es bastante vago. ¿Cómo funciona Vector ?

Answer 1

Estos pueden ser interesantes para ti:

• Ideal Hash Trees por Phil Bagwell.
• Implementando vectores persistentes en Scala - Daniel Spiewak
• Vectores más persistentes: análisis de rendimiento - Daniel Spiewak
• Persistentes estructuras de datos en Scala

Answer 2

La palabra clave aquí es Trie . Vector se implementa como una estructura de datos Trie . Ver http://en.wikipedia.org/wiki/Trie .

Más precisamente, es un "trie de vector de mapa de bits". Acabo de encontrar una descripción bastante detallada de la estructura (junto con una implementación, aparentemente en Rust) aquí:

https://bitbucket.org/astrieanna/bitmapped-vector-trie

El extracto más relevante es:

Un vector de mapa de bits Trie es básicamente un árbol de 32. El nivel 1 es una matriz de tamaño 32, independientemente del tipo de datos. El nivel 2 es una matriz de 32 niveles 1. y así sucesivamente, hasta que: El nivel 7 es una matriz de 2 niveles 6.

ACTUALIZACIÓN : En respuesta al comentario de Lai Yu-Hsuan sobre la complejidad:

Tendré que suponer que querías decir "profundidad" aquí :-D. La leyenda para "eC" dice "La operación lleva tiempo efectivamente constante, pero esto podría depender de algunas suposiciones tales como la longitud máxima de un vector o la distribución de las teclas hash".

Si está dispuesto a considerar el peor de los casos, y dado que hay un límite superior al tamaño máximo del vector, entonces sí, de hecho, podemos decir que la complejidad es constante. Digamos que consideramos que el tamaño máximo es 2 ^ 32, entonces esto significa que el peor caso es 7 operaciones como máximo, en cualquier caso. Por otra parte, siempre podemos considerar el peor caso para cualquier tipo de colección, encontrar un límite superior y decir que esto es una complejidad constante, pero para una lista por ejemplo, esto significaría una constante de 4 mil millones, lo que no es muy práctico.

Pero Vector es lo opuesto, 7 operaciones son más que prácticas, y así es como podemos permitirnos considerar su complejidad constante en la práctica .

Otra forma de ver esto: no estamos hablando de log (2, N), sino de log (32, N). Si tratas de trazar eso, verás que es prácticamente una línea horizontal. Así que hablando de forma pragmática, nunca podrás ver un aumento en el tiempo de procesamiento a medida que la colección crece. Sí, eso todavía no es realmente constante (por eso está marcado como "eC" y no solo como "C"), y podrás ver la diferencia en torno a los vectores cortos (pero de nuevo, una diferencia muy pequeña porque el número de operaciones crece mucho lentamente).

Answer 3

Las otras respuestas re ''Trie'' son buenas. Pero como una aproximación cercana, solo para una comprensión rápida:

• El vector utiliza internamente una estructura de árbol, no un árbol binario, sino un árbol de 32 arios
• Cada ''nodo de 32 vías'' usa Array [32] y puede almacenar 0-32 referencias a nodos secundarios o 0-32 piezas de datos
• El árbol está estructurado para equilibrarse de cierta manera: tiene "n" niveles profundos, pero los niveles 1 a n-1 son "niveles solo índice" (100% referencias hijo, sin datos) y el nivel n contiene todos los datos (100% de datos, sin referencias secundarias). Entonces, si la cantidad de elementos de datos es "d", entonces n = log-base-32 (d) se redondea hacia arriba

¿Por qué esto? Simple: para el rendimiento.

En lugar de hacer miles / millones / gazillones de asignaciones de memoria para cada elemento de datos individual, la memoria se asigna en 32 fragmentos de elementos. En lugar de caminar kilómetros de profundidad para encontrar sus datos, la estructura es bastante superficial: es un árbol muy ancho y corto. Por ejemplo, 5 niveles de profundidad pueden contener 32 ^ 5 elementos de datos (para elementos de 4 bytes = 132GB, es decir, bastante grandes) y cada acceso de datos buscaría y recorrería 5 nodos desde la raíz (mientras que una gran matriz usaría un solo acceso a datos). El vector no asigna de manera proactiva la memoria para todo el Nivel n (datos), - asigna 32 fragmentos de elementos según sea necesario. Le da un rendimiento de lectura algo similar a un gran conjunto, mientras que tiene características funcionales (potencia y flexibilidad y eficiencia de la memoria) algo similar a un árbol binario.

:)