Scala pour l'efficacité de la compréhension?

StackOverflow https://stackoverflow.com/questions/4211103

  •  25-09-2019
  •  | 
  •  

Question

Dans le livre « Programmation Scala », chapitre 23, l'auteur donne un exemple comme: 

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

L'auteur dit, cela traduit en: 

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

Mais si vous regardez dans la carte et la définition de la méthode flatmap ( TraversableLike.scala ), vous pouvez trouver, ils sont définis comme pour les boucles: 

   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
  }

Eh bien, je suppose que cela pour sera traduit sans cesse à foreach puis traduit while qui est une construction pas une expression, scala n'a pas pour construction, car il veut la céder pour toujours quelque chose.

Alors, ce que je veux discuter avec vous est que, pourquoi Scala ceci « Pour la traduction »? L'exemple de l'auteur a utilisé 4 générateurs, qui seront traduits en 4 niveau imbriqué boucle à la fin, je pense que cela va avoir des performances vraiment horrible quand la books est grande.

Scala encourager les gens à utiliser ce genre de « Syntactic sucre », vous pouvez toujours voir les codes qui font largement l'utilisation du filtre, la carte et flatmap, qui semble les programmeurs oublient ce que dans un autre, et ce qu'ils ont vraiment fait son nid une boucle est réalisé seulement pour faire des codes semble un peu plus court. Quelle est ton idée?

Était-ce utile?

La solution

Pour compréhensions sont le sucre syntaxique pour la transformation monadique, et, en tant que tels, sont utiles dans toutes sortes d'endroits. A cela, ils sont beaucoup plus bavard à Scala que le Haskell équivalent construction (bien sûr, Haskell est non stricte par défaut, donc on ne peut pas parler de la performance de la construction comme dans Scala).

Il est également important, cette construction conserve ce qui est fait claire et évite l'escalade rapidement en retrait ou l'imbrication de méthode privée inutile.

Quant à l'examen final, que ce soit qui cache la complexité ou non, je le pose ceci: 

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

Il est très facile de voir ce qui est fait, et la complexité est claire: b ^ 2 * a ^ 2 (le filtre ne modifie pas la complexité), pour le nombre de livres et le nombre d'auteurs. Maintenant, écrire le même code en Java, que ce soit avec indentation profonde ou avec des méthodes privées, et d'essayer de déterminer, dans un rapide coup d'oeil, ce que la complexité du code est.

Alors, à mon humble avis, cela ne cache pas la complexité, mais, au contraire, fait clairement.

En ce qui concerne les map / flatMap / Définitions filter que vous mentionnez, ils ne font pas partie List ou toute autre classe, de sorte qu'ils ne seront pas appliquées. En fait, 

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

est traduit en 

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

et ce n'est pas la même chose que 

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

qui est de savoir comment la définition que vous avez passé serait appelé. Pour mémoire, la mise en œuvre effective de map sur List est: 

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
}

Autres conseils

Je vous écris du code afin qu'il soit facile à comprendre et à maintenir. Je puis profil. S'il y a un goulot d'étranglement qui est là que je consacre mon attention. Si c'est quelque chose que vous avez décrit, je vais attaquer le problème d'une manière différente. Jusque-là, j'aime le « sucre ». Il me sauve la peine d'écrire des choses ou penser sérieusement à ce sujet.

Il y a en fait 6 boucles. Une boucle pour chaque filtre / flatMap / map

Le filtre-> paires de la carte peut être effectué dans une boucle à l'aide de vues paresseux des collections (méthode d'itération)

En général, tt est en cours d'exécution 2 boucles imbriquées pour les livres pour trouver toutes les paires de livres, puis deux boucles imbriquées pour trouver si l'auteur d'un livre est dans la liste des auteurs de l'autre.

En utilisant de simples structures de données, vous feriez la même chose lors du codage explicitement.

Et bien sûr, l'exemple est ici pour montrer un complexe « pour » la boucle, ne pas écrire le code le plus efficace. Par exemple, au lieu d'une séquence d'auteurs, on peut utiliser un ensemble et trouver si l'intersection est non vide: 

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

Notez que 2.8, l'appel filter a été changé pour withFilter qui est paresseux et éviterait la construction d'une structure intermédiaire. Voir le guide pour passer du filtre à withFilter? .

Je crois que la raison pour laquelle for est traduit à map, flatMap et withFilter (ainsi que les définitions de valeur si elle est présente) est de rendre l'utilisation des monades plus facile.

En général, je pense que si le calcul que vous faites consiste en boucle 4 fois, il est très bien en utilisant la boucle de for. Si le calcul peut être effectué de manière plus efficace et la performance est importante, vous devez utiliser l'algorithme plus efficace.

Un suivi de la réponse de @ IttayD sur l'efficacité de l'algorithme. Il convient de noter que l'algorithme dans le message original (et dans le livre) est une boucle imbriquée JOIN . Dans la pratique, ce n'est pas un algorithme efficace pour les grands ensembles de données, et la plupart des bases de données utiliserait un agrégat de hachage ici à la place. En Scala, un agrégat de hachage ressemblerait à quelque chose comme: 

(for (book <- books;
      author <- book.authors) yield (book, author)
).groupBy(_._2).filter(_._2.size > 1).keys
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top