¿El estilo de codificación idiomática de Scala es solo una trampa genial para escribir código ineficiente?

performance

Question

Siento que la comunidad de Scala tiene una gran obsesión por escribir códigos "concisos", "geniales", "scala idiomatic" , "one-liner", si es posible. Esto es seguido inmediatamente por una comparación con el código Java / imperativo / feo.

Si bien esto (a veces) lleva a un código fácil de entender, también conduce a un código ineficiente para el 99% de los desarrolladores. Y aquí es donde Java / C ++ no es fácil de superar.

Considere este simple problema: dada una lista de enteros, elimine el elemento más grande. El pedido no necesita ser preservado.

Aquí está mi versión de la solución (Puede que no sea la mejor, pero es lo que haría un desarrollador promedio que no sea rockstar).

def removeMaxCool(xs: List[Int]) = {
  val maxIndex = xs.indexOf(xs.max);
  xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}

Es Scala idiomático, conciso, y utiliza algunas funciones de lista agradables. También es muy ineficiente. Atraviesa la lista al menos 3 o 4 veces.

Aquí está mi solución totalmente desagradable, similar a Java. También es lo que un desarrollador razonable de Java (o un principiante de Scala) escribiría.

def removeMaxFast(xs: List[Int]) = {
    var res = ArrayBuffer[Int]()
    var max = xs.head
    var first = true;   
    for (x <- xs) {
        if (first) {
            first = false;
        } else {
            if (x > max) {
                res.append(max)
                max = x
            } else {
                res.append(x)
            }
        }
    }
    res.toList
}

Totalmente no-Scala idiomático, no funcional, no concisa, pero es muy eficiente. ¡Atraviesa la lista solo una vez!

Entonces, si el 99% de los desarrolladores de Java escriben un código más eficiente que el 99% de los desarrolladores de Scala, este es un gran obstáculo para lograr una mayor adopción de Scala. ¿Hay alguna forma de salir de esta trampa?

Estoy buscando consejos prácticos para evitar tales "trampas de ineficiencia" mientras mantengo la implementación clara y concisa.

Aclaración: esta pregunta proviene de un escenario de la vida real: tuve que escribir un algoritmo complejo. Primero lo escribí en Scala, luego "tuve que" reescribirlo en Java. La implementación de Java fue el doble de larga, y no tan clara, pero al mismo tiempo fue dos veces más rápida. Volver a escribir el código de Scala para ser eficiente probablemente llevaría un tiempo y una comprensión algo más profunda de las eficiencias internas de la scala (para el mapa vs. pliegue, etc.)

Answer 1

¿Qué hay de esto?

def removeMax(xs: List[Int]) = {
  val buf = xs.toBuffer
  buf -= (buf.max)
}

Un poco más feo, pero más rápido:

def removeMax(xs: List[Int]) = {
  var max = xs.head
  for ( x <- xs.tail ) 
  yield {
    if (x > max) { val result = max; max = x; result}
    else x
  }
}

Answer 2

Como referencia, a continuación se splitAt cómo se define splitAt en TraversableLike en la biblioteca estándar de Scala,

def splitAt(n: Int): (Repr, Repr) = {
  val l, r = newBuilder
  l.sizeHintBounded(n, this)
  if (n >= 0) r.sizeHint(this, -n)
  var i = 0
  for (x <- this) {
    (if (i < n) l else r) += x
    i += 1
  }
  (l.result, r.result)
}

No es diferente a su código de ejemplo de lo que un programador de Java podría tener.

Me gusta Scala porque, donde el rendimiento importa, la mutabilidad es un camino razonable por recorrer. La biblioteca de colecciones es un gran ejemplo; especialmente cómo oculta esta mutabilidad detrás de una interfaz funcional.

Cuando el rendimiento no es tan importante, como algunos códigos de aplicaciones, las funciones de orden superior en la biblioteca de Scala permiten una gran expresividad y eficiencia del programador.

Por curiosidad, escogí un archivo grande arbitrario en el compilador de Scala ( scala.tools.nsc.typechecker.Typers.scala ) y conté algo así como 37 para los bucles, 11 mientras que los bucles, 6 concatenaciones ( ++ ) y 1 veces ( sucede que es un foldRight ).

Answer 3

Discutamos una falacia en la pregunta:

Entonces, si el 99% de los desarrolladores de Java escriben un código más eficiente que el 99% de los desarrolladores de Scala, este es un gran obstáculo para lograr una mayor adopción de Scala. ¿Hay alguna forma de salir de esta trampa?

Esto se presume, sin ninguna evidencia que lo respalde. Si es falso, la pregunta es discutible.

¿Hay evidencia de lo contrario? Bueno, consideremos la pregunta en sí misma: no prueba nada, pero muestra que las cosas no son tan claras.

Totalmente no-Scala idiomático, no funcional, no concisa, pero es muy eficiente. ¡Atraviesa la lista solo una vez!

De las cuatro afirmaciones de la primera oración, las tres primeras son verdaderas, y la cuarta, como muestra el usuario desconocido , ¡es falsa! ¿Y por qué es falso? Porque, al contrario de lo que dice la segunda oración, atraviesa la lista más de una vez.

El código llama a los siguientes métodos:

res.append(max)
res.append(x)

y

res.toList

Consideremos primero append .

1. append toma un parámetro vararg. Eso significa que max y x se encapsulan primero en una secuencia de algún tipo (un WrappedArray , de hecho), y luego pasan como parámetro. Un mejor método hubiera sido += .

2. Ok, append llamadas ++= , que delega a += . Pero, primero, llama a ensureSize , que es el segundo error ( += llama también - ++= simplemente lo optimiza para múltiples elementos). Debido a que una Array es una colección de tamaño fijo, lo que significa que, en cada cambio de tamaño, toda la Array debe copiarse.

Así que consideremos esto. Cuando cambia el tamaño, Java primero borra la memoria almacenando 0 en cada elemento, luego Scala copia cada elemento de la matriz anterior en la nueva matriz. Dado que el tamaño se duplica cada vez, esto ocurre en log (n) veces, y la cantidad de elementos que se copian aumenta cada vez que ocurre.

Tomemos como ejemplo n = 16. Hace esto cuatro veces, copiando 1, 2, 4 y 8 elementos respectivamente. Como Java tiene que borrar cada una de estas matrices, y cada elemento debe leerse y escribirse, cada elemento copiado representa 4 recorridos de un elemento. Agregando todo lo que tenemos (n - 1) * 4, o, aproximadamente, 4 recorridos de la lista completa. Si cuentas leer y escribir como una sola pasada, como a menudo las personas lo hacen de manera errónea, entonces todavía hay tres recorridos.

Uno puede mejorar esto inicializando el ArrayBuffer con un tamaño inicial igual a la lista que será leída, menos uno, ya que descartaremos un elemento. Sin embargo, para obtener este tamaño, necesitamos atravesar la lista una vez.

Ahora consideremos toList . Para decirlo simplemente, atraviesa toda la lista para crear una nueva lista.

Entonces, tenemos 1 recorrido para el algoritmo, 3 o 4 recorridos para cambiar el tamaño y 1 recorrido adicional para toList . Eso es 4 o 5 travesías.

El algoritmo original es un poco difícil de analizar, porque take , drop y ::: atraviesan una cantidad variable de elementos. Sin embargo, al sumar todos, hace el equivalente a 3 recorridos. Si se usó splitAt , se reduciría a 2 cruces. Con 2 recorridos más para obtener el máximo, obtenemos 5 recorridos, ¡el mismo número que el algoritmo no funcional y no conciso!

Entonces, consideremos las mejoras.

En el algoritmo imperativo, si uno usa ListBuffer y += , todos los métodos son de tiempo constante, lo que lo reduce a un solo recorrido.

En el algoritmo funcional, podría reescribirse como:

val max = xs.max
val (before, _ :: after) = xs span (max !=)
before ::: after

Eso lo reduce al peor caso de tres cruces. Por supuesto, hay otras alternativas presentadas, basadas en recursión o pliegue, que lo resuelven en un recorrido.

Y, lo más interesante de todo, todos estos algoritmos son O(n) , y el único que casi incurrió (accidentalmente) en la peor complejidad fue el imperativo (debido a la copia en matriz). Por otro lado, las características de caché del imperativo bien podrían hacerlo más rápido, porque los datos son contiguos en la memoria. Eso, sin embargo, no está relacionado ni con un gran Oh o funcional versus imperativo, y es solo una cuestión de las estructuras de datos que fueron elegidas.

Por lo tanto, si nos tomamos la molestia de realizar un benchmarking, analizar los resultados, considerar el rendimiento de los métodos y buscar formas de optimizarlo, entonces podemos encontrar formas más rápidas de hacerlo de una manera imperativa que funcional.

Pero todo este esfuerzo es muy diferente de decir que el código promedio del programador Java será más rápido que el código promedio del programador Scala; si la pregunta es un ejemplo, eso es simplemente falso. E incluso descontando la pregunta, no hemos visto evidencia de que la premisa fundamental de la pregunta sea cierta.

EDITAR

Primero, permítanme reiterar mi punto, porque parece que no estaba claro. Mi punto es que el código que el programador Java promedio escribe puede parecer más eficiente, pero en realidad no lo es. O, dicho de otro modo, el estilo tradicional de Java no le proporciona rendimiento, solo el trabajo duro lo hace, ya sea Java o Scala.

Luego, tengo un punto de referencia y resultados también, incluyendo casi todas las soluciones sugeridas. Dos puntos interesantes al respecto:

1. Según el tamaño de la lista, la creación de objetos puede tener un impacto mayor que los recorridos múltiples de la lista. El código funcional original de Adrian aprovecha el hecho de que las listas son estructuras de datos persistentes al no copiar los elementos directamente del elemento máximo. Si se utilizara un Vector su lugar, tanto el lado izquierdo como el derecho se mantendrían casi sin cambios, lo que podría conducir a un mejor rendimiento.

2. Aunque los usuarios desconocidos y paradigmáticos tienen soluciones recursivas similares, las paradigmáticas son mucho más rápidas. El motivo es que evita la coincidencia de patrones. La coincidencia de patrones puede ser muy lenta.

El código de referencia está here , y los resultados están here .

Answer 4

El ejemplo que diste no es muy funcional, en realidad. Esto es lo que estás haciendo:

// Given a list of Int
def removeMaxCool(xs: List[Int]): List[Int] = {

  // Find the index of the biggest Int
  val maxIndex = xs.indexOf(xs.max);

  // Then take the ints before and after it, and then concatenate then
  xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}

Eso sí, no está mal , pero uno sabe cuándo el código funcional es óptimo cuando describe lo que quiere, en lugar de cómo lo quiere. Como crítica menor, si utilizó splitAt lugar de take y drop , podría mejorarlo ligeramente.

Otra forma de hacerlo es esta:

def removeMaxCool(xs: List[Int]): List[Int] = {
  // the result is the folding of the tail over the head 
  // and an empty list
  xs.tail.foldLeft(xs.head -> List[Int]()) {

    // Where the accumulated list is increased by the
    // lesser of the current element and the accumulated
    // element, and the accumulated element is the maximum between them
    case ((max, ys), x) => 
      if (x > max) (x, max :: ys)
      else (max, x :: ys)

  // and of which we return only the accumulated list
  }._2
}

Ahora, vamos a discutir el tema principal. ¿Es este código más lento que el de Java? ¡Seguramente! ¿Es el código de Java más lento que un equivalente de C? Puedes apostar que es JIT o no JIT. ¡Y si lo escribe directamente en ensamblador, puede hacerlo aún más rápido!

Pero el costo de esa velocidad es que obtienes más errores, pasas más tiempo tratando de comprender el código para depurarlo, y tienes menos visibilidad de lo que hace el programa en general, en comparación con lo que está haciendo un pequeño código: - lo que podría dar lugar a problemas de rendimiento propios.

Así que mi respuesta es simple: si crees que la penalización de velocidad de programación en Scala no vale las ganancias que trae, debes programar en ensamblador. Si piensas que soy radical, entonces contradigo que eliges lo familiar como el intercambio "ideal".

¿Creo que el rendimiento no importa? ¡De ningún modo! ¡Creo que una de las principales ventajas de Scala es aprovechar las ventajas que a menudo se encuentran en los lenguajes de tipado dinámico con el rendimiento de un lenguaje estáticamente tipado! El rendimiento importa, la complejidad del algoritmo importa mucho, y los costos constantes también son importantes.

Pero, siempre que haya una opción entre rendimiento y legibilidad y mantenibilidad, la última es preferible. Claro, si el rendimiento debe mejorarse, entonces no hay otra opción: hay que sacrificar algo. Y si no se pierde en legibilidad / mantenibilidad, como Scala vs lenguajes con tipado dinámico, seguro, busque el rendimiento.

Por último, para obtener rendimiento de la programación funcional, debe conocer los algoritmos funcionales y las estructuras de datos. Claro, el 99% de los programadores de Java con una experiencia de 5-10 años superará el rendimiento del 99% de los programadores de Scala con 6 meses de experiencia. Lo mismo fue cierto para la programación imperativa vs programación orientada a objetos hace un par de décadas, y la historia muestra que no importaba.

EDITAR

Como nota al margen, su algoritmo "rápido" sufre de un problema grave: utiliza ArrayBuffer . Esa colección no tiene un toList tiempo constante, y tiene tiempo lineal para toList . Si usas ListBuffer cambio, obtienes el toList time constante y toList .

Answer 5

En primer lugar, el comportamiento de los métodos que presentó no es el mismo. El primero mantiene el orden de los elementos, mientras que el segundo no.

Segundo, entre todas las soluciones posibles que podrían calificarse como "idiomáticas", algunas son más eficientes que otras. Manteniéndose muy cerca de su ejemplo, puede, por ejemplo, usar recursividad final para eliminar variables y la gestión manual del estado:

def removeMax1( xs: List[Int] ) = {
  def rec( max: Int, rest: List[Int], result: List[Int]): List[Int] = {
    if( rest.isEmpty ) result
    else if( rest.head > max ) rec( rest.head, rest.tail, max :: result)
    else rec( max, rest.tail, rest.head :: result )
  }
  rec( xs.head, xs.tail, List() )
}

o doblar la lista:

def removeMax2( xs: List[Int] ) = {
  val result = xs.tail.foldLeft( xs.head -> List[Int]() ) { 
    (acc,x) =>
      val (max,res) = acc
      if( x > max ) x -> ( max :: res )
      else max -> ( x :: res )
  }
  result._2
}

Si desea conservar el orden de inserción original, puede (a expensas de tener dos pases, en lugar de uno) sin esfuerzo escribir algo como:

def removeMax3( xs: List[Int] ) = {
  val max = xs.max
  xs.filterNot( _ == max )
}

que es más claro que tu primer ejemplo.

Answer 6

La mayor ineficiencia cuando escribe un programa es preocuparse por las cosas equivocadas. Por lo general, es algo malo de lo que preocuparse. ¿Por qué?

1. El tiempo del desarrollador generalmente es mucho más caro que el tiempo de CPU, de hecho, generalmente hay una escasez de la primera y un excedente de la última.

2. La mayoría del código no necesita ser muy eficiente porque nunca se ejecutará en conjuntos de datos de millones de ejemplares varias veces por segundo.

3. La mayoría del código no necesita errores, y menos código es menos espacio para que los errores se oculten.

Answer 7

Otro contendiente Esto usa un ListBuffer, como la segunda oferta de Daniel, pero comparte la cola post-max de la lista original, evitando copiarla.

  def shareTail(xs: List[Int]): List[Int] = {
    var res = ListBuffer[Int]()
    var maxTail = xs
    var first = true;
    var x = xs
    while ( x != Nil ) {
      if (x.head > maxTail.head) {
          while (!(maxTail.head == x.head)) {
              res += maxTail.head
              maxTail = maxTail.tail
          }
      }
      x = x.tail
    }
    res.prependToList(maxTail.tail)
  }

Answer 8

Prueba esto:

(myList.foldLeft((List[Int](), None: Option[Int]))) {
  case ((_, None),     x) => (List(),               Some(x))
  case ((Nil, Some(m), x) => (List(Math.min(x, m)), Some(Math.max(x, m))
  case ((l, Some(m),   x) => (Math.min(x, m) :: l,  Some(Math.max(x, m))
})._1

Idiomático, funcional, atraviesa una sola vez. Quizás algo críptico si no estás acostumbrado a los modismos de programación funcional.

Vamos a tratar de explicar lo que está sucediendo aquí. Trataré de hacerlo lo más simple posible, sin ningún rigor.

Un doblez es una operación en una List[A] (es decir, una lista que contiene elementos de tipo A ) que tomará un estado inicial s0: S (es decir, una instancia de un tipo S ) y una función f: (S, A) => S (es decir, una función que toma el estado actual y un elemento de la lista, y le da el siguiente estado, es decir, actualiza el estado de acuerdo con el siguiente elemento).

La operación luego iterará sobre los elementos de la lista, usando cada uno para actualizar el estado de acuerdo con la función dada. En Java, sería algo así como:

interface Function<T, R> { R apply(T t); }
class Pair<A, B> { ... }
<State> State fold(List<A> list, State s0, Function<Pair<A, State>, State> f) {
  State s = s0;
  for (A a: list) {
    s = f.apply(new Pair<A, State>(a, s));
  }
  return s;
}

Por ejemplo, si desea agregar todos los elementos de una List[Int] , el estado sería la suma parcial, que tendría que inicializarse a 0, y el nuevo estado producido por una función simplemente agregaría el estado actual a el elemento actual que se está procesando:

myList.fold(0)((partialSum, element) => partialSum + element)

Intenta escribir un doblez para multiplicar los elementos de una lista, luego otro para encontrar los valores extremos (máximo, mínimo).

Ahora, el doblez presentado anteriormente es un poco más complejo, ya que el estado se compone de la nueva lista que se está creando junto con el elemento máximo encontrado hasta ahora. La función que actualiza el estado es más o menos directa una vez que captas estos conceptos. Simplemente coloca en la nueva lista el mínimo entre el máximo actual y el elemento actual, mientras que el otro valor va al máximo actual del estado actualizado.

Lo que es un poco más complejo que entender esto (si no tienes antecedentes de FP) es llegar a esta solución. Sin embargo, esto es solo para mostrarte que existe, se puede hacer. Es solo una mentalidad completamente diferente.

EDITAR: Como ve, el primer y el segundo case en la solución que propuse se usan para configurar el doblez. Es equivalente a lo que ve en otras respuestas cuando lo hacen xs.tail.fold((xs.head, ...)) {...} . Tenga en cuenta que las soluciones propuestas hasta ahora con xs.tail/xs.head no cubren el caso en el que xs es List() y generarán una excepción. La solución anterior devolverá List() lugar. Como no especificó el comportamiento de la función en listas vacías, ambas son válidas.

Answer 9

def removeOneMax (xs: List [Int]) : List [Int] = xs match {                                  
    case x :: Nil => Nil 
    case a :: b :: xs => if (a < b) a :: removeOneMax (b :: xs) else b :: removeOneMax (a :: xs) 
    case Nil => Nil 
}

Aquí hay un método recursivo, que solo se repite una vez. Si necesita rendimiento, debe pensarlo, si no, no.

Puede hacer que sea recursivo de cola de la manera estándar: dando un carry adicional de parámetros, que es por defecto la Lista vacía, y recoge el resultado mientras se itera. Eso es, por supuesto, un poco más largo, pero si necesita rendimiento, debe pagarlo:

import annotation.tailrec 
@tailrec
def removeOneMax (xs: List [Int], carry: List [Int] = List.empty) : List [Int] = xs match {                                  
  case a :: b :: xs => if (a < b) removeOneMax (b :: xs, a :: carry) else removeOneMax (a :: xs, b :: carry) 
  case x :: Nil => carry 
  case Nil => Nil 
}

No sé cuáles son las posibilidades, que los compiladores posteriores mejorarán las llamadas de mapa más lentas para ser tan rápidos como los ciclos while. Sin embargo: rara vez necesita soluciones de alta velocidad, pero si las necesita con frecuencia, las aprenderá rápidamente.

¿Sabes qué tan grande debe ser tu colección, usar un segundo entero para tu solución en tu máquina?

Como un delineador, similar a la solución de Daniel C. Sobrals:

((Nil : List[Int], xs(0)) /: xs.tail) ((p, x)=> if (p._2 > x) (x :: p._1, p._2) else ((p._2 :: p._1), x))._1

pero eso es difícil de leer, y no midí el rendimiento efectivo. El patrón normal es (x /: xs) ((a, b) => / * algo * /). Aquí, x y a son pares de List-hasta ahora y max-tan-lejos, que resuelve el problema para llevar todo a una línea de código, pero no es muy legible. Sin embargo, puede ganar reputación en CodeGolf de esta manera, y tal vez a alguien le gusta hacer una medición de rendimiento.

Y ahora, para nuestra gran sorpresa, algunas medidas:

Un método de tiempo actualizado, para sacar la recolección de basura del camino, y calentar el compilador del punto de acceso, una fuente principal y muchos métodos de este hilo, juntos en un Objeto llamado

object PerfRemMax {

  def timed (name: String, xs: List [Int]) (f: List [Int] => List [Int]) = {
    val a = System.currentTimeMillis 
    val res = f (xs)
    val z = System.currentTimeMillis 
    val delta = z-a
    println (name + ": "  + (delta / 1000.0))
    res
  }

def main (args: Array [String]) : Unit = {
  val n = args(0).toInt
  val funs : List [(String, List[Int] => List[Int])] = List (
    "indexOf/take-drop" -> adrian1 _, 
    "arraybuf"      -> adrian2 _, /* out of memory */
    "paradigmatic1"     -> pm1 _, /**/
    "paradigmatic2"     -> pm2 _, 
    // "match" -> uu1 _, /*oom*/
    "tailrec match"     -> uu2 _, 
    "foldLeft"      -> uu3 _,
    "buf-=buf.max"  -> soc1 _, 
    "for/yield"     -> soc2 _,
    "splitAt"       -> daniel1,
    "ListBuffer"    -> daniel2
    )

  val r = util.Random 
  val xs = (for (x <- 1 to n) yield r.nextInt (n)).toList 

// With 1 Mio. as param, it starts with 100 000, 200k, 300k, ... 1Mio. cases. 
// a) warmup
// b) look, where the process gets linear to size  
  funs.foreach (f => {
    (1 to 10) foreach (i => {
        timed (f._1, xs.take (n/10 * i)) (f._2)
        compat.Platform.collectGarbage
    });
    println ()
  })
}

Cambié el nombre de todos los métodos y tuve que modificar uu2 un poco para adaptarme a la declaración de método común (Lista [Int] => Lista [Int]).

Del resultado largo, solo proporciono el resultado para las invocaciones de 1M:

scala -Dserver PerfRemMax 2000000
indexOf/take-drop:  0.882
arraybuf:   1.681
paradigmatic1:  0.55
paradigmatic2:  1.13
tailrec match: 0.812
foldLeft:   1.054
buf-=buf.max:   1.185
for/yield:  0.725
splitAt:    1.127
ListBuffer: 0.61

Los números no son completamente estables, según el tamaño de muestra, y un bit que varía de ejecución a ejecución. Por ejemplo, para carreras de 100k a 1M, en pasos de 100k, el tiempo para splitAt fue el siguiente:

splitAt: 0.109
splitAt: 0.118
splitAt: 0.129
splitAt: 0.139
splitAt: 0.157
splitAt: 0.166
splitAt: 0.749
splitAt: 0.752
splitAt: 1.444
splitAt: 1.127

La solución inicial ya es bastante rápida. splitAt es una modificación de Daniel, a menudo más rápido, pero no siempre.

La medición se realizó en un solo núcleo Centrino de 2Ghz, ejecutando xUbuntu Linux, Scala-2.8 con Sun-Java-1.6 (escritorio).

Las dos lecciones para mí son:

• siempre mide tus mejoras de rendimiento; es muy difícil estimarlo, si no lo haces a diario
• no solo es divertido escribir código funcional, a veces el resultado es aún más rápido

Aquí hay un enlace a mi código de referencia, si alguien está interesado.