Scala per l'efficienza di comprensione?

Question

Nel libro "Programmazione In Scala", capitolo 23, l'autore dà un esempio come:

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'autore ha detto, questo sarà tradotto in:

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

Ma se si guarda nella definizione mappa e flatmap metodo ( TraversableLike.scala ), si possono trovare, essi sono definiti come per i cicli:

   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
  }

Bene, credo che questo per essere continuamente tradotto in foreach e poi tradotto in while che è un costrutto non è un'espressione, scala non ha un costrutto per, perché vuole la resa per sempre qualcosa.

Quindi, quello che voglio discutere con voi è che, perché Scala fare questo "Per la traduzione"? L'esempio del autore ha utilizzato 4 generatori, che saranno tradotti in 4 livello nidificato ciclo for, alla fine, penso che avrà prestazioni davvero orribile quando la books è grande.

Scala incoraggiare le persone ad utilizzare questo tipo di "Zucchero sintattico", si può sempre vedere codici che pesantemente fanno uso di filtri, mappa e flatmap, che sembra programmatori stanno dimenticando ciò che realmente fanno è cappio uno nidificazione all'interno di un altro, e che cosa raggiunto è solo per rendere i codici sembra un po 'più breve. Qual è la tua idea?

Answer 1

Per comprensioni sono zucchero sintattico per la trasformazione della monade, e, come tale, è utile in tutti i tipi di luoghi. A questo, sono molto più dettagliato rispetto a Scala costrutto Haskell equivalente (naturalmente, Haskell è non-strict per default, quindi non si può parlare di prestazioni del costrutto come in Scala).

Anche importante, questo costrutto mantiene ciò che viene fatto chiaro, ed evita rapidamente crescente indentazione o inutili metodo di nidificazione privato.

Per quanto riguarda la considerazione finale, sia che nasconde la complessità o no, ti poni in questo modo:

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

E 'molto facile vedere cosa è stato fatto, e la complessità è chiara: b ^ 2 * a ^ 2 (il filtro non altera la complessità), per il numero di libri e il numero di autori. Ora, scrivere lo stesso codice in Java, sia con profonda rientranza o con metodi privati, e cercare di accertare, in una rapida occhiata, ciò che la complessità del codice è.

Quindi, secondo me, questo non nasconde la complessità, ma, al contrario, mette in chiaro.

Per quanto riguarda il map / flatMap / filter definizioni si parla, non appartengono a List o di qualsiasi altra classe, in modo che non verranno applicate. In sostanza,

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

è tradotto in

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

e che non è la stessa cosa di

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

che è come la definizione che avete passato sarebbe chiamato. Per la cronaca, l'effettiva attuazione di map su 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

I scrivere codice in modo che sia facile da capire e mantenere. Ho poi profilo. Se c'è un collo di bottiglia è lì che dedico la mia attenzione. Se si tratta di qualcosa come hai descritto io attaccherò il problema in modo diverso. Fino ad allora, io amo il "Sugar". Mi fa risparmiare la fatica di scrivere cose fuori o pensiero fisso su di esso.

Answer 3

Ci sono in realtà 6 cicli. Un anello per ogni filtro / flatMap / mappa

Il Filtro-> mappa coppie può essere fatto in un loop utilizzando viste pigri delle collezioni (iteratore metodo)

In generale, TT è in esecuzione 2 cicli annidati per i libri per trovare tutte le coppie di libri e poi due cicli annidati per trovare se l'autore di un libro è nella lista degli autori l'altro.

Utilizzando semplici strutture di dati, si dovrebbe fare la stessa cosa quando si codifica in modo esplicito.

E, naturalmente, l'esempio è quello di mostrare un complesso 'per' ciclo, di non scrivere il codice più efficiente. Per esempio, invece di una sequenza di autori, si potrebbe utilizzare un set e poi trovare se l'intersezione non è vuota:

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

Answer 4

Si noti che in 2.8, la chiamata filter è stato cambiato in withFilter che è pigro e eviterebbe la costruzione di una struttura intermedia. Vedere per passare dal filtro a withFilter? .

Credo il motivo che for è tradotto in map, flatMap e withFilter (nonché definizioni del valore se presente) è quello di rendere l'uso di monadi facile.

In generale, penso che se il calcolo si sta facendo coinvolge il ciclo 4 volte, è bene utilizzare il ciclo for. Se il calcolo può essere fatto in modo più efficiente e le prestazioni è importante allora si dovrebbe utilizzare l'algoritmo più efficiente.

Answer 5

Un follow-up a @ risposta di IttayD sull'efficienza dell'algoritmo. vale la pena di notare che l'algoritmo nel post originale (e nel libro) è un join ciclo nidificato . In pratica, questo non è un algoritmo efficiente per grandi insiemi di dati, e la maggior parte dei database userebbe un hash aggregato qui invece. In Scala, un aggregato hash sarebbe simile:

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