Scala für das Verständnis Effizienz?

Question

In dem Buch "Programmieren in Scala", Kapitel 23, der Autor ein Beispiel geben, wie:

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

Der Autor sagte, wird dies übersetzt in:

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

Aber wenn Sie die Karte und flatmap Methodendefinition prüfen ( TraversableLike.scala ), Sie finden können, werden sie als für Schleifen definiert:

   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
  }

Nun, ich denke, dies wird ständig foreach übersetzt wird und dann übersetzt, während Aussage, die ein Konstrukt ist kein Ausdruck, scala nicht über einen für Konstrukt, weil es die für immer nachgeben etwas will.

Also, was ich mit Ihnen besprechen möchte, ist, dass, warum Scala diese „Für Übersetzung“ tun? Der Author dieses Beispiel 4 verwendeten Generatoren, die in 4 Pegel für Schleife am Ende verschachtelt übersetzt wird, denke ich, es wird wirklich schrecklich Leistung haben, wenn die books groß ist.

Scala Menschen zu ermutigen, diese Art von „syntaktischem Zucker“ zu verwenden, können Sie immer Codes sehen, die stark Verwendung von Filter, Karte und flatmap machen, die Programmierer scheint vergessen, was sie wirklich tun, ist Verschachtelung einer Schleife in einer anderen, und was erreicht nur Codes machen sieht ein bisschen kürzer. Was ist deine Idee?

Answer 1

Für Comprehensions sind syntaktischer Zucker für monadische Transformation und als solche nützlich sind, in allen möglichen Orten. Darauf sind sie viel ausführlicher in Scala als das Äquivalent Haskell-Konstrukt (natürlich Haskell ist nicht streng standardmäßig, so dass man nicht über die Leistung des Konstrukts wie in Scala sprechen kann).

Auch wichtig, dieses Konstrukt hält, was klar gemacht wird, und vermeidet schnell eskalierenden Vertiefung oder unnötige private Methode Verschachtelung.

In Bezug auf die letzte Überlegung, ob diese verbirgt die Komplexität oder nicht, werde ich postuliert diese:

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

Es ist sehr einfach, zu sehen, was getan wird, und die Komplexität ist klar: b ^ 2 * a ^ 2 (die Filter werden die Komplexität nicht ändern), für die Anzahl der Bücher und die Anzahl der Autoren. Nun schreiben Sie den gleichen Code in Java, entweder mit tiefem Einschnitte oder mit privaten Methoden und versuchen zu ermitteln, in einem kurzen Blick, was die Komplexität des Codes ist.

Also, imho, dies nicht versteckt die Komplexität, sondern, im Gegenteil, es macht löschen.

Wie für die map / flatMap / filter Definitionen, die Sie erwähnen, sie nicht gehören in List oder jede andere Klasse, so werden sie nicht angewendet werden. Grundsätzlich

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

Übersetzung

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

und das ist nicht dasselbe wie

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

das ist, wie die Definition, die Sie genannt würde übergeben. Für die Aufzeichnung ist die tatsächliche Umsetzung von map auf 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

Ich schreibe Code, so dass es leicht zu verstehen und zu pflegen. Ich habe dann das Profil. Wenn es ein Engpass ist das ist, wo ich meine Aufmerksamkeit widmen. Wenn es in etwas ist, wie Sie beschrieben haben werde ich das Problem auf eine andere Art und Weise angreifen. Bis dahin, ich liebe den „Zucker“. Es erspart mir die Mühe, die Dinge aus oder denken schwer, darüber zu schreiben.

Answer 3

Es gibt tatsächlich 6 Schleifen. Eine Schleife für jeden Filter / flatMap / Karte

Die Filter-> Kartenpaare können mit lazy Ansichten der Sammlungen (Iteratormethode)

Generell tt 2 ausgeführt wird, verschachtelte Schleifen für Bücher alle Buchpaare zu finden und dann zwei verschachtelte Schleifen zu finden, wenn der Autor eines Buches in der Liste der Autoren des anderen ist.

Mit einfachen Datenstrukturen, Sie würden das gleiche tun, wenn explizit Codierung.

Und natürlich das Beispiel ist hier um einen Komplex zu zeigen ‚für‘ Schleife, nicht den effizientesten Code zu schreiben. Zum Beispiel statt einer Folge von Autoren, könnte man ein Set verwenden und dann finden, wenn die Kreuzung nicht leer ist:

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

Answer 4

Beachten Sie, dass der filter Anruf in 2,8, wurde auf withFilter geändert, die faul ist und vermeiden würde eine Zwischenstruktur zu konstruieren. Siehe Leitfaden für aus dem Filter bewegen zu withFilter? .

Ich glaube, der Grund dafür, dass for zu map, flatMap und withFilter übersetzt wird (wie auch Wertdefinitionen falls vorhanden) ist die Verwendung von Monaden leichter zu machen.

Generell denke ich, wenn die Berechnung Sie tun 4mal beinhaltet Looping, es in Ordnung ist, die for Schleife. Wenn die Berechnung effizienter durchgeführt werden kann und die Leistung ist wichtig, dann sollten Sie den effizienteren Algorithmus verwenden.

Answer 5

Eine Follow-up @ IttayD Antwort auf die Effizienz des Algorithmus. Es ist erwähnenswert, dass der Algorithmus in der ursprünglichen Nachricht (und im Buch) ist eine verschachtelte Schleife verbindet . In der Praxis ist dies nicht ein effizienter Algorithmus für große Datenmengen und die meisten Datenbanken würden ein Hash-Aggregat hier stattdessen verwenden. In Scala würde eine Hash-Summe in etwa so aussehen:

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