Effiziente groupwise Aggregation auf Scala Sammlungen

Question

ich oft brauchen so etwas wie

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

zu tun Was ist der beste Weg, um die gleiche Wirkung zu erzielen, aber vermeiden Sie explizit die Zwischen Sammlungen mit groupBy konstruieren?

Answer 1

Sie könnten die erste Sammlung über eine Karte hält Ihre Zwischenergebnisse falten:

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)) 
    } 
    } 

Du hast gesagt, Sammlung und ich schrieb Iterable, aber Sie haben in der Falte in Ihrer Frage, ob, um Angelegenheiten zu denken.

Wenn Sie effizienten Code wünschen, verwenden Sie wahrscheinlich eine veränderliche Map wie in Rex 'Antwort.

Answer 2

Sie können es nicht wirklich als Einzeiler machen, also sollten Sie sicher sein, dass Sie es brauchen, bevor Sie etwas Komplizierteres schreiben (geschrieben von einem etwas performanceorientierten Blick, da Sie nach "effizient" gefragt haben): Hier ist ein Beispiel davon in Aktion

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) 
} 

(auf Ihrem Anwendungsfall Je Sie in eine unveränderliche Karte statt im letzten Schritt packen möchten.):

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

Jetzt könnten Sie etwas bemerken komisch hier: Ich benutze eine Java HashMap. Dies liegt daran, dass die HashMaps von Java 2-3x schneller sind als die von Scala. (Sie können das Äquivalent mit einer Scala HashMap schreiben, aber es macht die Dinge nicht schneller als Ihr Original.) Folglich ist dieser Vorgang 2-3x schneller als was Sie gepostet haben. Aber solange du nicht unter schwerem Erinnerungsdruck stehst, tut dir die Erstellung der flüchtigen Sammlungen nicht wirklich weh.