scala - Scala コレクションでの効率的なグループ単位の集計

Question

私はしばしば次のようなことをする必要があります

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

同じ効果を達成するための最良の方法は何groupByですか?

Answer 1

中間結果を保持するマップ上に初期コレクションを折りたたむことができます。

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

あなたは collection と言い、私は と書きIterableましたが、あなたの質問では折り目の順序が重要かどうかを考えなければなりません。

効率的なコードが必要な場合は、おそらく Rex の回答のように変更可能なマップを使用します。

Answer 2

ワンライナーとして実際に行うことはできないため、このようなより複雑なものを書く前に、それが必要であることを確認する必要があります(「効率的」を要求したため、パフォーマンスを重視した観点から書かれています):

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

(ユースケースによっては、最後のステップで代わりに不変マップにパックしたい場合があります。) 実際の例を次に示します。

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

ここで、おかしなことに気付くかもしれません。私は Java HashMap を使用しています。これは、Java の HashMap が Scala よりも 2 ～ 3 倍高速であるためです。(Scala HashMap で同等のものを書くことはできますが、実際にはオリジナルよりも速くはなりません。) したがって、この操作は投稿したものより 2 ～ 3 倍高速です。ただし、深刻なメモリ プレッシャが発生していない限り、一時的なコレクションを作成しても、実際には大きな影響はありません。