Scala para la eficiencia de la comprensión?

Question

En el libro "Programación En Scala", capítulo 23, el autor da un ejemplo como:

case class Book(title: String, authors: String*)
val books: List[Book] = // list of books, omitted here
// find all authors who have published at least two books

for (b1 <- books; b2 <- books if b1 != b2;
    a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
yield a1

El autor dijo, esto será traducido en:

books flatMap (b1 =>
   books filter (b2 => b1 != b2) flatMap (b2 =>
      b1.authors flatMap (a1 =>
        b2.authors filter (a2 => a1 == a2) map (a2 =>
           a1))))

Pero si nos fijamos en la definición mapa y flatmap método ( TraversableLike.scala ), es posible, que se definen como para bucles:

   def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    b.sizeHint(this) 
    for (x <- this) b += f(x)
    b.result
  }

  def flatMap[B, That](f: A => Traversable[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    for (x <- this) b ++= f(x)
    b.result
  }

Bueno, supongo que esto será de forma continua traducirse a foreach y luego traducido a while que no es una construcción de una expresión, Scala no tiene una para la construcción, ya que quiere que el algo para producir siempre.

Por lo tanto, lo que yo quiero hablar con ustedes es que, ¿por qué hacer esto Scala "Para la traducción"? El ejemplo del autor utilizó 4 generadores, que se traducirán en 4 niveles anidados para el lazo al final, creo que va a tener un rendimiento realmente horrible cuando el books es grande.

Scala animar a la gente a utilizar este tipo de "sintáctica azúcar", siempre se puede ver los códigos que en gran medida hacen uso de filtro, mapa y flatmap, que parece programadores están olvidando lo que realmente hacen es anidación un bucle dentro de otro, y lo logrado es sólo para hacer códigos se ve un poco más corto. ¿Cuál es tu idea?

Answer 1

Para comprensiones son azúcar sintáctica para la transformación monádico, y, como tales, son útiles en todo tipo de lugares. En ese momento, que son mucho más prolija en Scala que la construcción de Haskell equivalente (por supuesto, Haskell es no estricto de forma predeterminada, por lo que no se puede hablar sobre el desempeño de la construcción como en la Scala).

También es importante, este constructo mantiene lo que se hace clara, y evita la rápida escalada de la sangría o innecesario de anidación método privado.

Con respecto a la consideración final, ya sea que oculta la complejidad o no, voy a postular la siguiente:

for {
  b1 <- books
  b2 <- books
  if b1 != b2
  a1 <- b1.authors
  a2 <- b2.authors 
  if a1 == a2
} yield a1

Es muy fácil ver lo que se está haciendo, y la complejidad es claro: ^ b ^ 2 * 2 una (el filtro no alterará la complejidad), para el número de libros y varios autores. Ahora, escriba el mismo código en Java, ya sea con una profunda hendidura o con métodos privados, y tratar de determinar, en un vistazo rápido, lo que la complejidad del código.

Así que, en mi humilde opinión, esto no oculta la complejidad, sino que, por el contrario, deja claro.

En cuanto a la map / flatMap / filter definiciones que mencionas, no lo hacen pertenecen a List o de cualquier otra clase, por lo que no se aplicarán. Básicamente,

for(x <- List(1, 2, 3)) yield x * 2

se traduce en

List(1, 2, 3) map (x => x * 2)

y que no es lo mismo que

map(List(1, 2, 3), ((x: Int) => x * 2)))

que es la forma en la definición que ha pasado sería llamado. Para el registro, la aplicación real de map en List es:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  val b = bf(repr)
  b.sizeHint(this) 
  for (x <- this) b += f(x)
  b.result
}

Answer 2

Me escribir código para que sea más fácil de entender y mantener. Entonces perfil. Si hay un cuello de botella que es donde Dedico mi atención. Si es en algo así como lo ha descrito Voy a atacar el problema de una manera diferente. Hasta entonces, me encanta el "azúcar". Me ahorra la molestia de escribir cosas o pensar mucho sobre ello.

Answer 3

En realidad, hay 6 bucles. Un bucle para cada filtro / flatMap / mapa

El Filtro> pares mapa puede hacerse en un bucle mediante el uso de puntos de vista de descanso de las colecciones (iterador método)

En general, se ejecuta tt 2 bucles anidados para los libros para encontrar todos los pares de libros y luego dos bucles anidados para encontrar si el autor de un libro está en la lista de los autores de la otra.

El uso de estructuras de datos simples, usted haría lo mismo cuando se codifica de forma explícita.

Y, por supuesto, este ejemplo es mostrar un complejo 'para' bucle, no escribir el código más eficiente. Por ejemplo, en lugar de una secuencia de autores, se podría utilizar un set y luego encontrar si la intersección es no vacía:

for (b1 <- books; b2 <- books; a <- (b1.authors & b2.authors)) yield a

Answer 4

Tenga en cuenta que en 2.8, la llamada filter fue cambiado a withFilter que es perezoso y evitaría la construcción de una estructura intermedia. Ver para pasar de filtro para withFilter? .

Creo que la razón por la que for se traduce a map, flatMap y withFilter (así como las definiciones de valor si está presente) es hacer que el uso de las mónadas más fácil.

En general creo que si el cálculo que está haciendo implica bucle 4 veces, es muy bien usar el bucle for. Si el cálculo se puede realizar con mayor eficiencia y el rendimiento es importante, entonces debería usar el algoritmo más eficiente.

Answer 5

Un seguimiento de la respuesta de @ IttayD en la eficiencia del algoritmo. Vale la pena señalar que el algoritmo en el post original (y en el libro) es un bucle anidado . En la práctica, esto no es un algoritmo eficiente para grandes conjuntos de datos, y la mayoría de las bases de datos sería utilizar un picadillo agregada aquí en su lugar. En Scala, un agregado de hash sería algo como:

(for (book <- books;
      author <- book.authors) yield (book, author)
).groupBy(_._2).filter(_._2.size > 1).keys