¿Cuándo debo elegir Vector en Scala?

Parece que Vectorfue tarde a la fiesta de las colecciones Scala, y todas las publicaciones influyentes del blog ya se habían ido.

En Java, ArrayListla colección predeterminada es la que puedo usar, LinkedListpero solo cuando he pensado en un algoritmo y me preocupo lo suficiente como para optimizarlo. En Scala, ¿debería usarlo Vectorpor defecto Seqo tratar de hacer ejercicio cuando Listsea ​​más apropiado?

Como regla general, uso predeterminado Vector. Es más rápido que Listpara casi todo y más eficiente en memoria para secuencias de mayor tamaño que trivial. Consulte esta documentación del rendimiento relativo de Vector en comparación con las otras colecciones. Hay algunas desventajas para ir conVector . Específicamente:

• Las actualizaciones en la cabeza son más lentas que List (aunque no tanto como se podría pensar)

Otro inconveniente antes de Scala 2.10 era que el soporte de coincidencia de patrones era mejor para List , pero esto se rectificó en 2.10 con generalizados +:y :+extractores.

También hay una forma más abstracta y algebraica de abordar esta pregunta: ¿qué tipo de secuencia tiene conceptualmente ? Además, que eres haciendo conceptualmente con él? Si veo una función que devuelve un Option[A], sé que esa función tiene algunos agujeros en su dominio (y por lo tanto es parcial). Podemos aplicar esta misma lógica a las colecciones.

Si tengo una secuencia de tipo List[A], estoy afirmando efectivamente dos cosas. Primero, mi algoritmo (y datos) está completamente estructurado en pila. En segundo lugar, estoy afirmando que lo único que voy a hacer con esta colección son los recorridos completos, O (n). Estos dos realmente van de la mano. Por el contrario, si tengo algo de tipo Vector[A], lo único que estoy afirmando es que mis datos tienen un orden bien definido y una longitud finita. Por lo tanto, las afirmaciones son más débiles Vectory esto conduce a una mayor flexibilidad.

Bueno, a Listpuede ser increíblemente rápido si el algoritmo se puede implementar únicamente con ::, heady tail. Tuve una lección objetiva de eso muy recientemente, cuando vencí a Java splital generar un en Listlugar de unArray , y no pude superar eso con nada más.

Sin embargo, Listtiene un problema fundamental: no funciona con algoritmos paralelos. No puedo dividir un Listen múltiples segmentos, o volver a concatenarlo de manera eficiente.

Hay otros tipos de colecciones que pueden manejar el paralelismo mucho mejor, y Vectores una de ellas. Vectortambién tiene una gran localidad, queList no lo es, lo que puede ser una verdadera ventaja para algunos algoritmos.

Entonces, teniendo en cuenta todo, Vectores la mejor opción a menos que tenga consideraciones específicas que hagan preferible una de las otras colecciones; por ejemplo, puede elegir Streamsi desea una evaluación y almacenamiento en caché diferidos ( Iteratores más rápido pero no almacena en caché), oList si El algoritmo se implementa naturalmente con las operaciones que mencioné.

Por cierto, es preferible usar SeqoIndexedSeq menos que desee una parte específica de la API (por ejemplo, List's ::), o incluso GenSeqo GenIndexedSeqsi su algoritmo se puede ejecutar en paralelo.

Algunas de las declaraciones aquí son confusas o incluso incorrectas, especialmente la idea de que inmutable. Vector en Scala es algo así como una ArrayList. List y Vector son estructuras de datos inmutables y persistentes (es decir, "baratas para obtener una copia modificada"). No existe una opción predeterminada razonable, ya que podría ser para estructuras de datos mutables, sino que depende de lo que esté haciendo su algoritmo. La lista es una lista enlazada individualmente, mientras que Vector es un número entero de base 32, es decir, es una especie de árbol de búsqueda con nodos de grado 32. Usando esta estructura, Vector puede proporcionar las operaciones más comunes razonablemente rápidas, es decir, en O (log_32 ( norte)). Eso funciona para anteponer, agregar, actualizar, acceso aleatorio, descomposición en cabeza / cola. La iteración en orden secuencial es lineal. La lista, por otro lado, solo proporciona iteración lineal y anteposición de tiempo constante, descomposición en cabeza / cola.

Esto podría parecer como si Vector fuera un buen reemplazo para List en casi todos los casos, pero anteponer, la descomposición y la iteración son a menudo las operaciones cruciales en secuencias en un programa funcional, y las constantes de estas operaciones son (mucho) más altas para el vector debido a su estructura más complicada. Hice algunas mediciones, por lo que la iteración es aproximadamente el doble de rápida para la lista, el antecedente es aproximadamente 100 veces más rápido en las listas, la descomposición en la cabeza / cola es aproximadamente 10 veces más rápida en las listas y la generación de un transitable es aproximadamente 2 veces más rápida para los vectores. (Esto probablemente se deba a que Vector puede asignar matrices de 32 elementos a la vez cuando lo construye usando un generador en lugar de agregar o agregar elementos uno por uno).

Entonces, ¿qué estructura de datos debemos usar? Básicamente, hay cuatro casos comunes:

• Solo necesitamos transformar secuencias por operaciones como mapa, filtro, plegado, etc.: básicamente no importa, debemos programar nuestro algoritmo genéricamente e incluso podríamos beneficiarnos de aceptar secuencias paralelas. Para operaciones secuenciales, la lista es probablemente un poco más rápida. Pero debe compararlo si tiene que optimizar.
• Necesitamos mucho acceso aleatorio y diferentes actualizaciones, por lo que debemos usar el vector, la lista será prohibitivamente lenta.
• Operamos en listas de una manera funcional clásica, construyéndolas precediendo e iterando por descomposición recursiva: use list, el vector será más lento en un factor 10-100 o más.
• Tenemos un algoritmo de rendimiento crítico que es básicamente imperativo y tiene mucho acceso aleatorio en una lista, algo así como una clasificación rápida en el lugar: use una estructura de datos imperativa, por ejemplo, ArrayBuffer, localmente y copie sus datos desde y hacia ella.

Para colecciones inmutables, si desea una secuencia, su decisión principal es si usar una IndexedSeqo una LinearSeq, lo que ofrece diferentes garantías de rendimiento. IndexedSeq proporciona acceso aleatorio rápido de elementos y una operación de longitud rápida. Un LinearSeq proporciona acceso rápido solo al primer elemento a través de head, pero también tiene un acceso rápidotail operación . (Tomado de la documentación Seq.)

Para un IndexedSeq, normalmente elegirías a Vector. Ranges yWrappedString s son también IndexedSeqs.

Para un LinearSeq, normalmente elegiría un Listo su equivalente perezoso Stream. Otros ejemplos son Queuesy Stacks.

Entonces, en términos de Java, se ArrayListusa de manera similar a la de Scala Vectory de LinkedListmanera similar a la de Scala List. Pero en Scala, tendería a usar List con más frecuencia que Vector, porque Scala tiene mucho mejor soporte para funciones que incluyen el recorrido de la secuencia, como mapeo, plegado, iteración, etc. Tiende a usar estas funciones para manipular la lista como completo, en lugar de acceder aleatoriamente a elementos individuales.

En situaciones que implican mucho acceso aleatorio y mutación aleatoria, a Vector(o, como dicen los documentos , a Seq) parece ser un buen compromiso. Esto también es lo que sugieren las características de rendimiento .

Además, la Vectorclase parece funcionar bien en entornos distribuidos sin mucha duplicación de datos porque no hay necesidad de hacer una copia en escritura para el objeto completo. (Ver: http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures )

Si está programando de manera inmutable y necesita acceso aleatorio, Seq es el camino a seguir (a menos que desee un Set, que a menudo lo hace). De lo contrario, List funciona bien, excepto que sus operaciones no pueden ser paralelas.

Si no necesita estructuras de datos inmutables, quédese con ArrayBuffer ya que es el equivalente de Scala a ArrayList.