0
136
VistasEliminando la mutabilidad sin perder velocidad
Tengo una función como esta:
fun randomWalk(numSteps: Int): Int { var n = 0 repeat(numSteps) { n += (-1 + 2 * Random.nextInt(2)) } return n.absoluteValue }Esto funciona bien, excepto que usa una variable mutable, y me gustaría que todo sea inmutable cuando sea posible, para mayor seguridad y legibilidad. Así que se me ocurrió una versión equivalente que no usa ninguna variable mutable:
fun randomWalk_seq(numSteps: Int): Int = generateSequence(0) { it + (-1 + 2 * Random.nextInt(2)) } .elementAt(numSteps) .absoluteValueEsto también funciona bien y produce los mismos resultados, pero toma 3 veces más.
Usé la siguiente forma de medirlo:
@OptIn(ExperimentalTime::class) fun main() { val numSamples = 100000 val numSteps = 15708 repeat(5) { val randomWalkSamples: IntArray val duration = measureTime { randomWalkSamples = IntArray(numSamples) { randomWalk(numSteps) } } println(duration) } } Sé que es un poco complicado (podría haber usado JMH, pero esto es solo una prueba rápida, al menos sé que measureTime usa un reloj monótono). Los resultados para la versión iterativa (mutable):
2.965358406s 2.560777033s 2.554363661s 2.564279403s 2.608323586sComo era de esperar, la primera línea muestra que tomó un poco más de tiempo en la primera ejecución debido al calentamiento del JIT, pero las siguientes 4 líneas tienen una variación bastante pequeña.
Después de reemplazar randomWalk con randomWalk_seq :
6.636866719s 6.980840906s 6.993998111s 6.994038706s 7.018054467sSorprendentemente, no veo ningún tiempo de calentamiento: la primera línea siempre tiene una duración menor que las siguientes 4 líneas, cada vez que ejecuto esto. Y también, cada vez que lo ejecuto, la duración sigue aumentando, siendo la línea 5 siempre la de mayor duración.
¿Alguien puede explicar los hallazgos, y también hay alguna forma de hacer que esta función no use ninguna variable mutable pero aún tenga un rendimiento cercano a la versión mutable?
3 Respuestas
Responde la pregunta0
Su solución es más lenta por dos razones principales: el encajonamiento y la complejidad del iterador utilizado por la implementación de secuencia de generateSequence() .
El boxeo ocurre porque una Secuencia usa sus tipos de manera genérica, por lo que no puede usar Ints primitivos de 32 bits directamente, sino que debe envolverlos en clases y desenvolverlos al recuperar los elementos.
Puede ver la complejidad del iterador presionando Ctrl y haciendo clic en la función generateSequence para ver el código fuente.
La sugerencia de @ Михаил Нафталь es más rápida porque evita el iterador complejo de la secuencia, pero aún tiene boxeo.
Intenté escribir una sobrecarga de sumOf que usa IntProgression directamente en lugar de Iterable<T> , por lo que no usará el boxeo, y eso resultó en un rendimiento equivalente a su código imperativo con var . Como puede ver, está en línea y cuando se combina con { -1 + 2 * Random.nextInt(2) } lambda sugerida por @Михаил Нафталь, el código compilado resultante será equivalente a su código imperativo.
inline fun IntProgression.sumOf(selector: (Int) -> Int): Int { var sum: Int = 0.toInt() for (element in this) { sum += selector(element) } return sum } En última instancia, no creo que te estés comprando mucho en cuanto a la claridad del código al eliminar una sola var en una función tan pequeña. Diría que el código de secuencia es posiblemente más difícil de leer. var s puede agregar complejidad al código en algoritmos complejos, pero no creo que lo hagan en algoritmos tan simples, especialmente cuando solo hay uno de ellos y es local para la función.
0
Equivalente inmutable de una sola línea es:
fun randomWalk2(numSteps: Int) = (1..numSteps).sumOf { -1 + 2 * Random.nextInt(2) }.absoluteValueProbablemente, aún más eficaz sería reemplazar
con
para que tengas una multiplicación y n sumas en lugar de n multiplicaciones y (2*n-1) sumas:
fun randomWalk3(numSteps: Int) = (-numSteps + 2 * (1..numSteps).sumOf { Random.nextInt(2) }).absoluteValueActualizar
Como señaló @ Tenfour04, no hay una implementación de stdlib específica para IntProgression.sumOf , por lo que se resuelve en Iterable<T>.sumOf , lo que agregará una sobrecarga innecesaria para el int boxing. Entonces, es mejor usar IntArray aquí en lugar de IntProgression :
fun randomWalk4(numSteps: Int) = (-numSteps + 2 * IntArray(numSteps).sumOf { Random.nextInt(2) }).absoluteValueAún así animo a comprobar todo esto con JMH
0
Creo que: "Eliminar la mutabilidad sin perder velocidad" es un título incorrecto. Porque la mutabilidad viene a tratar con el flujo que el programa quiere lograr. está utilizando la función var dentro .... y 100% esta var nunca cambiará desde fuera de esta función y ese es el concepto de mutabilidad. si nos deshacemos de var en todas partes, ¿por qué lo necesitamos en la programación?