aggregazione groupwise efficiente su collezioni Scala

Question

ho spesso bisogno di fare qualcosa di simile

coll.groupBy(f(_)).mapValues(_.foldLeft(x)(g(_,_))) 

Qual è il modo migliore per ottenere lo stesso effetto, ma evitare esplicitamente la costruzione delle collezioni intermedi con groupBy?

Answer 1

Si potrebbe ripiegare la raccolta iniziale sopra un programma che tiene i risultati intermedi:

def groupFold[A,B,X](as: Iterable[A], f: A => B, init: X, g: (X,A) => X): Map[B,X] = 
    as.foldLeft(Map[B,X]().withDefaultValue(init)){ 
    case (m,a) => { 
     val key = f(a) 
     m.updated(key, g(m(key),a)) 
    } 
    } 

Hai detto che la raccolta e l'ho scritto Iterable, ma si deve pensare se le questioni di ordine nella piega nella sua interrogazione.

Se si desidera un codice efficiente, si utilizzerà probabilmente una mappa mutabile come nella risposta di Rex.

Answer 2

Non si può davvero farlo come one-liner, quindi dovresti essere sicuro di averne bisogno prima di scrivere qualcosa di più elaborato come questo (scritto da una visione piuttosto performante visto che hai chiesto "efficiente"):

final case class Var[A](var value: A) { } 
def multifold[A,B,C](xs: Traversable[A])(f: A => B)(zero: C)(g: (C,A) => C) = { 
    import scala.collection.JavaConverters._ 
    val m = new java.util.HashMap[B, Var[C]] 
    xs.foreach{ x => 
    val v = { 
     val fx = f(x) 
     val op = m.get(fx) 
     if (op != null) op 
     else { val nv = Var(zero); m.put(fx, nv); nv } 
    } 
    v.value = g(v.value, x) 
    } 
    m.asScala.mapValues(_.value) 
} 

(a seconda del caso d'uso si potrebbe desiderare di mettere in valigia in una mappa immutabile, invece nell'ultimo passaggio.) Ecco un esempio di esso in azione:

scala> multifold(List("salmon","herring","haddock"))(_(0))(0)(_ + _.length) 
res1: scala.collection.mutable.HashMap[Char,Int] = Map(h -> 14, s -> 6)   

Ora, si potrebbe notare qualcosa strano qui: sto usando una HashMap Java. Questo perché le HashMaps di Java sono 2-3 volte più veloci di quelle di Scala. (Puoi scrivere la cosa equivalente con Scala HashMap, ma in realtà non rende le cose più veloci del tuo originale.) Di conseguenza, questa operazione è 2-3 volte più veloce di quanto hai postato. Ma a meno che tu non sia sottoposto a forti pressioni sulla memoria, la creazione delle collezioni transitori non ti fa veramente molto male.