¿Cuándo debo elegir Vector en Scala?

200

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?

Duncan McGregor
fuente
1
Supongo que lo que quiero decir aquí es que en Java crearía List<String> l = new ArrayList<String>()blogs de escritura Scala para que creyera que todos usan List para obtener bondades persistentes de la colección, pero ¿Vector es lo suficientemente general como para que lo usemos en lugar de List?
Duncan McGregor
9
@Debilski: Me pregunto qué quieres decir con eso. Me sale Listcuando Seq()escribo en REPL.
missingfaktor
1
Hmm, bueno, lo dice en los documentos. Quizás esto solo sea cierto para IndexedSeq.
Debilski
1
El comentario sobre el tipo de concreto predeterminado Seqes de más de tres años. A partir de Scala 2.11.4 (y anteriores), el tipo concreto predeterminado de Seqes List.
Mark Canlas
3
Para acceso aleatorio, el vector es mejor. Para el acceso de cabeza, cola, la lista es mejor. Para la operación masiva, como mapa, filtro, se prefiere el vector, ya que el vector está organizado con 32 elementos como un fragmento, mientras que la lista organizó los elementos con punteros entre sí, no hay garantía de que estos elementos estén cerca el uno del otro.
johnsam

Respuestas:

280

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.

Daniel Spiewak
fuente
2
2.10 ha estado fuera por un tiempo, ¿la coincidencia del patrón de Lista es aún mejor que Vector?
Tim Gautier
3
La coincidencia de patrones de lista ya no es mejor. De hecho, es todo lo contrario. Por ejemplo, para obtener cabeza y cola uno puede hacer case head +: tailo case tail :+ head. Para hacer coincidir contra vacío, puede hacer case Seq()y así sucesivamente. Todo lo que necesita está allí en la API, que es más versátil que la de List's'
Kai Sellgren
Listse implementa con una lista vinculada individualmente. VectorSe implementa algo como el de Java ArrayList.
Josiah Yoder
66
@JosiahYoder No se implementa como ArrayList. ArrayList envuelve una matriz que cambia de tamaño dinámicamente. Vector es un trie , donde las claves son los índices de valores.
John Colanduoni
1
Me disculpo. Estaba yendo a una fuente web que era vaga sobre los detalles. ¿Debo corregir mi declaración anterior? ¿O es esa una mala forma?
Josiah Yoder
93

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.

Daniel C. Sobral
fuente
3
Gracias por la respuesta. ¿Qué quieres decir con "tiene una gran localidad"?
Ngoc Dao
10
@ngocdaothanh Significa que los datos se agrupan estrechamente en la memoria, lo que mejora la posibilidad de que los datos estén en la memoria caché cuando los necesite.
Daniel C. Sobral
1
@ user247077 Sí, las listas pueden vencer a los vectores en el rendimiento dados los detalles que mencioné. Y no todas las acciones de los vectores se amortizan O (1). De hecho, en estructuras de datos inmutables (que es el caso), las inserciones / eliminaciones alternativas en cualquier extremo no se amortizarán en absoluto. En ese caso, el caché es inútil porque siempre está copiando el vector.
Daniel C. Sobral
1
@ user247077 ¿Quizás no sepa que Vectorhay una estructura de datos inmutable en Scala?
Daniel C. Sobral
1
@ user247077 Es mucho más complicado que eso, incluyendo algunas cosas internamente mutables para hacer que el apéndice sea más barato, pero cuando lo usas como una pila, que es el escenario óptimo de la lista inmutable, aún terminas teniendo las mismas características de memoria de una lista vinculada, pero con un perfil de asignación de memoria mucho mayor.
Daniel C. Sobral
29

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.
dth
fuente
24

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.

Luigi Plinge
fuente
Pero si la iteración de Vector es más rápida que la de List, y también puedo asignar pliegues, etc., entonces, aparte de algunos casos especializados (esencialmente todos los algoritmos FP que están especializados en List), parece que List es esencialmente heredado.
Duncan McGregor
@Duncan, ¿dónde has oído que la iteración de Vector es más rápida? Para empezar, debe realizar un seguimiento y actualizar el índice actual, que no necesita con una lista vinculada. No llamaría a las funciones de lista "casos especializados", son el pan de cada día de la programación funcional. No usarlos sería como tratar de programar Java sin for-or while-loops.
Luigi Plinge
2
Estoy bastante seguro Vectorde que la iteración es más rápida, pero alguien necesita compararla para asegurarse.
Daniel Spiewak
Creo que los elementos (?) VectorExisten físicamente juntos en la RAM en grupos de 32, que se ajustan más completamente en la memoria caché de la CPU ... por lo que hay menos pérdida de memoria caché
richizy
2

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 )

Debilski
fuente
1
Hay tanto que aprender ... ¿Qué significa Vector siendo la Seq predeterminada? Si escribo Seq (1, 2, 3) obtengo List [Int] no Vector [Int].
Duncan McGregor
2
Si tiene acceso aleatorio, use un IndexedSeq. Lo cual también es Vector, pero ese es otro asunto.
Daniel C. Sobral
@DuncanMcGregor: Vector es el valor predeterminado IndexedSeqque implementa Seq. Seq(1, 2, 3)es un LinearSeqque se implementa usando List.
pathikrit 01 de
0

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.

Joshua Hartman
fuente
Me estoy aferrando al ámbito de las colecciones inmutables y persistentes. Mi punto es que, incluso si no necesito acceso aleatorio, ¿Vector ha reemplazado efectivamente a List?
Duncan McGregor
2
Depende un poco del caso de uso. Los vectores son más equilibrados. La iteración es más rápida que la lista y el acceso aleatorio es mucho más rápido. Las actualizaciones son más lentas ya que no es solo un antecedente de lista, a menos que sea una actualización masiva de un pliegue que se puede hacer con un generador. Dicho esto, creo que Vector es la mejor opción predeterminada ya que es muy versátil.
Joshua Hartman
Creo que llega al meollo de mi pregunta: los vectores son tan buenos que también podríamos usarlos donde los ejemplos generalmente muestran Lista.
Duncan McGregor