concatenate scala vector scala-collections

concatenate - ¿Cuándo debería elegir Vector in Scala?



scala mutable collections (6)

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

En Java ArrayList es la colección predeterminada: podría usar LinkedList pero solo cuando haya pensado en un algoritmo y me haya preocupado lo suficiente como para optimizarlo. En Scala, ¿debería utilizar Vector como mi Seq predeterminado o intentar resolver cuando List es realmente más apropiado?

Algunas de las declaraciones aquí son confusas o incluso erróneas, especialmente la idea de que inmutable. Vector en Scala es algo así como una ArrayList. List y Vector son estructuras de datos inmutables, persistentes (es decir, "barato para obtener una copia modificada"). No existe una elección predeterminada razonable, ya que podría ser para estructuras de datos mutables, sino que más bien depende de lo que esté haciendo su algoritmo. List es una lista unida individualmente, mientras que Vector es un trie entero base 32, es decir, es un tipo de árbol de búsqueda con nodos de grado 32. Utilizando esta estructura, Vector puede proporcionar operaciones más comunes razonablemente rápido, 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 pre-tiempo constante, descomposición en cabeza / cola. Todo lo demás toma en tiempo lineal general.

Esto podría parecer como si Vector fuera un buen reemplazo para la Lista en casi todos los casos, pero la operación previa, la descomposición y la iteración son a menudo las operaciones cruciales en las secuencias en un programa funcional, y las constantes de estas operaciones son (mucho) más altas para el vector a su estructura más complicada. Hice algunas mediciones, por lo que la iteración es aproximadamente dos veces más rápida para la lista, preceder es aproximadamente 100 veces más rápida en las listas, la descomposición en la cabeza / cola es 10 veces más rápida en las listas y la generación en un traversible es aproximadamente 2 veces más rápida para los vectores. (Probablemente esto se deba a que Vector puede asignar matrices de 32 elementos a la vez cuando lo construye utilizando un generador en lugar de anteponer o agregar elementos uno por uno). Por supuesto, todas las operaciones que toman el tiempo lineal en las listas, pero efectivamente el tiempo constante en los vectores (como el acceso aleatorio o el anexo) serán prohibitivamente lentas en las listas grandes.

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

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

Bueno, una List puede ser increíblemente rápida si el algoritmo se puede implementar únicamente con :: , head y tail . Tuve una lección objetiva de eso muy recientemente, cuando gané la split de Java generando una List lugar de una Array , y no pude vencer eso con cualquier otra cosa.

Sin embargo, List tiene un problema fundamental: no funciona con algoritmos paralelos. No puedo dividir una List en múltiples segmentos, ni volver a concatenarla, de manera eficiente.

Hay otros tipos de colecciones que pueden manejar el paralelismo mucho mejor, y Vector es uno de ellos. Vector también tiene una gran localidad, que la List no tiene, lo que puede ser una ventaja real para algunos algoritmos.

Entonces, teniendo en cuenta todo lo anterior, Vector es la mejor opción a menos que tenga consideraciones específicas que hagan que una de las otras colecciones sea preferible; por ejemplo, puede elegir Stream si desea una evaluación diferida y almacenamiento en caché ( Iterator es más rápido pero no almacena en caché) , o List si el algoritmo se implementa naturalmente con las operaciones que mencioné.

Por cierto, es preferible usar Seq o IndexedSeq menos que desee una pieza específica de API (como List :: s :: GenSeq , o incluso GenSeq o GenIndexedSeq si su algoritmo se puede ejecutar en paralelo.

Como regla general, por defecto usar Vector . Es más rápido que List para casi todo y más eficiente en la memoria para secuencias de tamaño más grande que trivial. Consulte esta documentation del rendimiento relativo de Vector en comparación con las otras colecciones. Hay algunas desventajas de ir con Vector . Específicamente:

  • Las actualizaciones en la cabecera son más lentas que la 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 generalizado +: y :+ extractores.

También hay una forma más abstracta y algebraica de abordar esta pregunta: ¿qué clase de secuencia tienes conceptualmente ? Además, ¿qué estás haciendo conceptualmente con esto? Si veo una función que devuelve una 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 efectivamente afirmando dos cosas. En primer lugar, mi algoritmo (y los datos) están estructurados por completo. En segundo lugar, estoy afirmando que las únicas cosas que voy a hacer con esta colección son O, n) travesías completas. Estos dos realmente van de la mano. Por el contrario, si tengo algo del tipo Vector[A] , lo único que afirmo es que mis datos tienen un orden bien definido y una longitud finita. Por lo tanto, las aserciones son más débiles con Vector , y esto conduce a su mayor flexibilidad.

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

Para IndexedSeq normalmente elegirías un Vector . Range s y WrappedString s también son IndexedSeqs.

Para LinearSeq normalmente elegiría una List o su Stream equivalente pereza. Otros ejemplos son Queue s y Stack s.

Así que en términos de Java, ArrayList usa de manera similar al Vector de Scala, y LinkedList manera similar a la List de Scala. Pero en Scala tendería a usar List más seguido que Vector, porque Scala tiene un soporte mucho mejor para funciones que incluyen el cruce de la secuencia, como mapeo, plegado, iteración, etc. Tiende a usar estas funciones para manipular la lista como un todo, en lugar de acceder aleatoriamente a elementos individuales.

Si está programando inmutablemente y necesita acceso aleatorio, Seq es el camino a seguir (a menos que desee un Set, que a menudo realmente hace). De lo contrario, List funciona bien, excepto que las operaciones no se pueden paralelizar.

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