Scala para eficiência de compreensão?

Question

No livro "Programação em Scala", capítulo 23, o autor dá um exemplo 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

O autor disse que isso será traduzido em:

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

Mas se você olhar para a definição do método mapa e plana (Traversablelike.scala), você pode achar que eles são definidos como para loops:

   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
  }

Bem, acho que isso será continuamente traduzido para o foreach e depois traduzido para a declaração, que é uma construção, não uma expressão, o Scala não possui um para construto, porque deseja sempre produzir algo.

Então, o que eu quero discutir com você é que, por que Scala faz isso "para tradução"? O exemplo do autor usou 4 geradores, que serão traduzidos em 4 níveis aninhados para loop no final, acho que terá um desempenho realmente horrível quando o books é grande.

O Scala incentiva as pessoas a usar esse tipo de "açúcar sintático", você sempre pode ver códigos que usam fortemente o filtro, o mapa e o mapa plano, o que parece que os programadores estão esquecendo o que realmente fazem é aninhar um loop dentro de outro, e o que é alcançado é apenas Para fazer com que os códigos pareçam um pouco mais curtos. Qual é a sua ideia?

Answer 1

Pois as compreensões são açúcar sintático para transformação monádica e, como tal, são úteis em todos os tipos de lugares. Com isso, eles são muito mais detalhados em Scala do que o equivalente Haskell Construct (é claro, Haskell não é rigoroso por padrão, portanto, não se pode falar sobre o desempenho da construção como em Scala).

Também é importante, esse construto mantém o que está sendo feito claro e evita que o recuo escalado rapidamente ou o ninho desnecessário do método privado.

Quanto à consideração final, se isso esconde a complexidade ou não, vou postar isso:

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

É muito fácil ver o que está sendo feito, e a complexidade é clara: B^2 * a^2 (o filtro não alterará a complexidade), para o número de livros e número de autores. Agora, escreva o mesmo código em Java, com recuo profundo ou com métodos privados, e tente verificar, de uma maneira rápida, qual é a complexidade do código.

Então, IMHO, isso não esconde a complexidade, mas, pelo contrário, deixa claro.

Quanto ao map/flatMap/filter definições que você menciona, elas não pertencem List ou qualquer outra classe, para que eles não sejam aplicados. Basicamente,

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

é traduzido para

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

E isso não é a mesma coisa que

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

É assim que a definição que você passou seria chamada. Para o registro, a implementação real de map sobre List é:

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

Escrevo código para que seja fácil de entender e manter. Eu então perfil. Se houver um gargalo, é onde dedico minha atenção. Se estiver em algo como você descreveu, vou atacar o problema de uma maneira diferente. Até então, eu amo o "açúcar". Isso me salva o problema de escrever coisas ou pensar muito sobre isso.

Answer 3

Na verdade, existem 6 loops. Um loop para cada filtro/plangmap/mapa

Os pares do filtro-> mapas podem ser feitos em um loop usando vistas preguiçosas das coleções (método do iterador)

Em geral, o TT está executando 2 loops aninhados para livros para encontrar todos os pares de livros e depois dois loops aninhados para descobrir se o autor de um livro está na lista de autores do outro.

Usando estruturas de dados simples, você faria o mesmo ao codificar explicitamente.

E, é claro, o exemplo aqui é mostrar um loop 'para' complexo, para não escrever o código mais eficiente. Por exemplo, em vez de uma sequência de autores, pode -se usar um conjunto e depois descobrir se a interseção não estiver vazia:

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

Answer 4

Observe que em 2.8, o filter A chamada foi alterada para withFilter que é preguiçoso e evitaria a construção de uma estrutura intermediária. Ver Guia para passar do filtro para o filtro?.

Eu acredito na razão que for é traduzido para map, flatMap e withFilter (assim como definições de valor, se presente) é facilitar o uso de mônadas.

Em geral, acho que se o cálculo que você está fazendo envolve loop 4 vezes, tudo bem usando o for ciclo. Se o cálculo puder ser feito com mais eficiência e o desempenho for importante, você deve usar o algoritmo mais eficiente.

Answer 5

Um acompanhamento da resposta do @Ittayd sobre a eficiência do algoritmo. Vale a pena notar que o algoritmo no post original (e no livro) é um João de loop aninhado. Na prática, este não é um algoritmo eficiente para grandes conjuntos de dados, e a maioria dos bancos de dados usaria um hash agregado aqui em vez disso. Em Scala, um agregado de hash seria algo como:

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