En el article written by Daniel Korzekwa, dijo que el rendimiento del siguiente código:Scala pregunta de desempeño
list.map(e => e*2).filter(e => e>10)
es mucho peor que la solución iterativa escrito utilizando Java.
¿Alguien puede explicar por qué? ¿Y cuál es la mejor solución para dicho código en Scala (espero que no sea una versión iterativa de Java que esté Scala-fied)?
La razón de que código particular es lento porque se está trabajando en primitivas, pero se trata de utilizar las operaciones genéricas, por lo que las primitivas tienen que ser en caja. (Esto podría mejorarse si List y sus antepasados estuvieran especializados.) Esto probablemente reducirá la velocidad de un factor de 5 o menos.
Además, algorítmicamente, esas operaciones son algo costosas, porque se hace una lista completa, y luego se crea una lista completamente nueva descartando algunos componentes de la lista intermedia. Si lo hicieras de una vez, estarías mejor. Se podría hacer algo como:
list collect (case e if (e*2>10) => e*2)
pero lo que si el cálculo e*2 es muy caro? Entonces podría
(List[Int]() /: list)((ls,e) => { val x = e*2; if (x>10) x :: ls else ls }
excepto que esto parecería al revés. (Podría revertirlo si fuera necesario, pero eso requiere crear una nueva lista, que de nuevo no es ideal algorítmicamente).
Por supuesto, tiene el mismo tipo de problemas algorítmicos en Java si está utilizando un solo lista enlazada: su nueva lista terminará hacia atrás, o tendrá que crearla dos veces, primero en reversa y luego hacia adelante, o debe compilarla con recursividad (sin cola) (lo cual es fácil en Scala, pero desaconsejable para este tipo de cosas en cualquier idioma, ya que se agotará la pila), o tiene que crear una lista mutable y luego pretender que no es mutable. (Lo cual, por cierto, también puede hacer en Scala - consulte mutable.LinkedList.)
Básicamente está recorriendo una lista dos veces. Una vez para multiplicar cada elemento por dos. Y luego otra vez para filtrar los resultados.
Piense en ello como un bucle mientras produce una LinkedList con los resultados intermedios. Y luego otro ciclo aplicando el filtro para producir los resultados finales.
Esto debería ser más rápido:
list.view.map(e => e * 2).filter(e => e > 10).force
Esta respuesta no entiende, aunque la solución es correcta. – Raphael
Podría ser inteligente ahora y señalar que en ninguna parte del código de muestra dice que involucra a Ints. Pero tengo que admitir que la respuesta hubiera sido mucho mejor si hubiera mencionado que hay un poco de boxeo y unboxing pasando. –
Rex Kerr indica correctamente el problema principal: Al operar en listas inmutables, el fragmento de código indicado crea listas intermedias en la memoria. Tenga en cuenta que esto no es necesariamente más lento que el código de Java equivalente; nunca se usan estructuras de datos inmutables en Java.
Wilfried Springer tiene una buena solución idónea para Scala. Utilizando view, no se crean copias (manipuladas) de toda la lista.
Tenga en cuenta que el uso de la vista puede no ser siempre el ideal. Por ejemplo, si su primera llamada es filter que se espera que elimine la mayor parte de la lista, puede valer la pena crear la versión más corta explícitamente y usar view solo después de eso para mejorar la localidad de memoria para iteraciones posteriores.
Esto no es una respuesta. Es un comentario sobre otras dos respuestas reales. –
Ah, y tal vez * usted * nunca use estructuras de datos inmutables en Java. De hecho, los uso mucho cuando es apropiado. –
1) Encontré que las dos respuestas a las que se hace referencia carecían de forma individual, por lo que decidí publicar una respuesta conjunta. El hecho de que doy las referencias adecuadas no hace que este sea un comentario. 2) El estándar [Java collections framework] (http://download.oracle.com/javase/6/docs/technotes/guides/collections/reference.html) parece ser bastante corto en implementaciones inmutables, proporcionando solo un no modificable (! = inmutable) envoltorio. Tal vez por eso. – Raphael
El enfoque de Scala es mucho más abstracto y genérico.Por lo tanto, es difícil optimizar cada caso individual.
Me imagino que el compilador HotSpot JIT podría aplicar la fusión de flujo y bucle al código en el futuro si ve que los resultados inmediatos no se utilizan.
Además, el código de Java simplemente hace mucho más.
Si realmente quiere mutar sobre una estructura de datos, considere transform. Se parece un poco a map pero no crea una nueva colección, e. g .:
val array = Array(1,2,3,4,5,6,7,8,9,10).transform(_ * 2)
// array is now WrappedArray(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)
Realmente espero que se añadirán algunas operaciones adicionales en lugar de iones el futuro ...
Para evitar que atraviesa la lista dos veces, creo que la sintaxis for es una buena opción aquí:
val list2 = for(v <- list1; e = v * 2; if e > 10) yield e
La solución se encuentra principalmente en JVM. Aunque Scala tiene una solución en la figura de @specialization, eso aumenta enormemente el tamaño de cualquier clase especializada, y solo resuelve la mitad del problema; la otra mitad es la creación de objetos temporales.
La JVM realmente hace un buen trabajo optimizando una gran cantidad, o el rendimiento sería aún más terrible, pero Java no requiere las optimizaciones que hace Scala, por lo que JVM no las proporciona. Espero que esto cambie hasta cierto punto con la introducción de SAM cierres no reales en Java.
Pero, al final, se trata de equilibrar las necesidades. El mismo bucle while que Java y Scala hacen mucho más rápido que el equivalente de función de Scala se puede hacer más rápido aún en C. Sin embargo, a pesar de lo que nos dicen las microdenominaciones, las personas usan Java.
list.filter (e => e * 2> 10) .map (e => e * 2)
Este intento reduce en primer lugar la lista. Entonces, el segundo recorrido es con menos elementos.
Esta respuesta tiene el problema, pero no ofrece una buena solución. – Raphael
@Raphael - Realmente no hay uno dado el estado actual de la biblioteca. 'view' /' force' no te va a salvar cuando trabajas con primitivos. –
Si 'e * 2' fuera costoso, entonces el costo de tener el paso intermedio disminuiría. Quizás problemas de memoria, si manejas grandes cantidades de datos. – ziggystar