Bueno, realmente depende de lo que el tipo real del mapa que está utilizando. Probablemente HashMap
. Ahora, las estructuras mutables como esa ganan rendimiento al preasignar la memoria que espera usar. Estás uniendo un millón de mapas, por lo que el mapa final será algo grande. Vamos a ver cómo se añaden estas claves/valores:
protected def addEntry(e: Entry) {
val h = index(elemHashCode(e.key))
e.next = table(h).asInstanceOf[Entry]
table(h) = e
tableSize = tableSize + 1
if (tableSize > threshold)
resize(2 * table.length)
}
Véase el 2 *
en la línea resize
? El mutable HashMap
crece duplicándose cada vez que se queda sin espacio, mientras que el inmutable es bastante conservador en el uso de memoria (aunque las claves existentes ocuparán normalmente el doble del espacio cuando se actualicen).
Ahora, en cuanto a otros problemas de rendimiento, está creando una lista de claves y valores en las dos primeras versiones. Eso significa que, antes de unirse a cualquier mapa, ¡ya tiene cada Tuple2
(pares de clave/valor) en la memoria dos veces! Además de la sobrecarga de List
, que es pequeña, pero estamos hablando de más de un millón de elementos multiplicados por la sobrecarga.
Es posible que desee utilizar una proyección que lo evite. Lamentablemente, la proyección se basa en Stream
, que no es muy confiable para nuestros propósitos en Scala 2.7.x. Aún así, probar este lugar:
for (m <- listOfMaps.projection; kv <- m) yield kv
Un Stream
no calcula un valor hasta que se necesite. El recolector de basura también debe recopilar los elementos no utilizados, siempre y cuando no guardes una referencia al encabezado Stream
, que parece ser el caso en tu algoritmo.
EDITAR
Como complemento, una para/rendimiento comprensión toma una o más colecciones y regresar una nueva colección. Siempre que tenga sentido, la colección que regresa es del mismo tipo que la colección original. Entonces, por ejemplo, en el siguiente código, la comprensión forzada crea una nueva lista, que luego se almacena dentro de l2
. No es val l2 =
que crea la nueva lista, sino la comprensión.
val l = List(1,2,3)
val l2 = for (e <- l) yield e*2
Ahora, veamos el código que se utiliza en los dos primeros algoritmos (menos el mutable
palabra clave):
(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv))
El operador foldLeft
, aquí escrito con su /:
sinónimo, se invocarán en el objeto devuelto por la comprensión forzosa. Recuerde que un :
al final de un operador invierte el orden del objeto y los parámetros.
Ahora, consideremos qué objeto es este, en el que se llama foldLeft
. El primer generador en este for-comprensión es m <- listOfMaps
. Sabemos que listOfMaps
es una colección de tipo Lista [X], donde X no es realmente relevante aquí. El resultado de una comprensión forzosa en un List
es siempre otro List
. Los otros generadores no son relevantes.
Por lo tanto, se toma esta List
, obtiene todas las claves/valores dentro de cada Map
que es un componente de este List
, y hacer una nueva List
con todo eso. Es por eso que estás duplicando todo lo que tienes.
(de hecho, es incluso peor que eso, porque cada generador crea una nueva colección; las colecciones creadas por el segundo generador son sólo el tamaño de cada elemento de la listOfMaps
sin embargo, y se descartan inmediatamente después de su uso)
La siguiente pregunta - en realidad, la primera, pero fue más fácil invertir la respuesta - es cómo ayuda el uso de projection
.
Cuando llama al projection
en un List
, devuelve un objeto nuevo, del tipo Stream
(en Scala 2.7.x). Al principio, puede pensar que esto solo empeorará las cosas, porque ahora tendrá tres copias del List
, en lugar de una sola. Pero un Stream
no está precalculado. Es perezosamente calculado.
Lo que significa esto es que el objeto resultante, la Stream
, no es una copia de la List
, sino, más bien, una función que se puede utilizar para calcular la Stream
cuando sea necesario. Una vez calculado, el resultado se mantendrá para que no sea necesario volver a calcularlo.
Además, map
, flatMap
y filter
de toda una Stream
devolver una nueva Stream
, lo que significa que todos ellos puede encadenar juntos sin hacer una sola copia del List
el que los creó. Dado que for-comprehensions con yield
utiliza estas mismas funciones, el uso de Stream
dentro de la evita copias innecesarias de datos.
Ahora, supongamos que usted escribió algo como esto:
val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv
(Map[A,B]() /: kvs) { ... }
En este caso, no está ganando nada. Después de asignar Stream
a kvs
, los datos aún no se han copiado. Sin embargo, una vez que se ejecuta la segunda línea, kvs habrá calculado cada uno de sus elementos y, por lo tanto, contendrá una copia completa de los datos.
Consideremos ahora la forma original ::
(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv))
En este caso, el Stream
se usa al mismo tiempo que se calcula. Veamos brevemente cómo se define foldLeft
para un Stream
:
override final def foldLeft[B](z: B)(f: (B, A) => B): B = {
if (isEmpty) z
else tail.foldLeft(f(z, head))(f)
}
Si el Stream
está vacía, simplemente devuelva el acumulador. De lo contrario, calcule un nuevo acumulador (f(z, head)
) y luego páselo y la función al tail
del Stream
.
Una vez que se haya ejecutado f(z, head)
, no habrá ninguna referencia restante al head
. O, en otras palabras, nada en ninguna parte del programa apunta al head
del Stream
, y eso significa que el recolector de basura puede recopilarlo, liberando así la memoria.
El resultado final es que cada elemento producido por la comprensión forzada existirá solo brevemente, mientras que usted lo usa para calcular el acumulador. Y así es como guarda guardando una copia de toda su información.
Finalmente, está la cuestión de por qué el tercer algoritmo no se beneficia de ello. Bueno, el tercer algoritmo no usa yield
, por lo que no se está realizando ninguna copia de ningún dato. En este caso, usar projection
solo agrega una capa indirecta.
Interesante. Seguí tu consejo y cambié las Listas a Streams, y no hubo mejoría en el rendimiento. De hecho, la implementación imperativa se duplicó en el tiempo requerido. Sin embargo, las implementaciones mutables dejaron de quedarse sin memoria. – Jeff
Además, quizás esta es una pregunta noobish, pero ¿cómo crean las primeras dos versiones listas de claves y valores? ¿Esto es porque la comprensión de rendimiento for() crea una nueva lista? No estoy seguro de cómo llamar .projection() dentro de la expresión for evita esto también. ¿Esto es porque la comprensión devuelve el mismo tipo de secuencia que se aprobó? – Jeff
Completaré mi respuesta, ya que es demasiado para guardarla como comentario. –