5

JavaからScalaにいくつかのコード（単純なベイズ推定アルゴリズムですが、それはそれほど重要ではありません）を再実装しています。可能な限り可変性を回避することでコードをクリーンで機能的に保ちながら、可能な限りパフォーマンスの高い方法で実装したいと思います。

Javaコードのスニペットは次のとおりです。

    // initialize
    double lP  = Math.log(prior);
    double lPC = Math.log(1-prior);

    // accumulate probabilities from each annotation object into lP and lPC
    for (Annotation annotation : annotations) {
        float prob = annotation.getProbability();
        if (isValidProbability(prob)) {
            lP  += logProb(prob);
            lPC += logProb(1 - prob);
        }
    }

とても簡単ですよね？そこで、最初の試行でScalafoldLeftメソッドとmapメソッドを使用することにしました。累積する値が2つあるため、アキュムレータはタプルです。

    val initial  = (math.log(prior), math.log(1-prior))
    val probs    = annotations map (_.getProbability)
    val (lP,lPC) = probs.foldLeft(initial) ((r,p) => {
      if(isValidProbability(p)) (r._1 + logProb(p), r._2 + logProb(1-p)) else r
    })

残念ながら、このコードのパフォーマンスはJavaの約5倍遅くなります（単純で不正確なメトリックを使用します。ループ内でコードを10000回呼び出すだけです）。1つの欠陥はかなり明らかです。リストを2回トラバースしています。1つはmapの呼び出しで、もう1つはfoldLeftでです。これが、リストを1回トラバースするバージョンです。

    val (lP,lPC) = annotations.foldLeft(initial) ((r,annotation) => {
      val  p = annotation.getProbability
      if(isValidProbability(p)) (r._1 + logProb(p), r._2 + logProb(1-p)) else r
    })

これの方が良い！Javaコードの約3倍のパフォーマンスを発揮します。私の次の予感は、フォールドの各ステップですべての新しいタプルを作成するのにおそらくいくらかのコストがかかるということでした。そこで、タプルを作成せずに、リストを2回トラバースするバージョンを試すことにしました。

    val lP = annotations.foldLeft(math.log(prior)) ((r,annotation) => {
       val  p = annotation.getProbability
       if(isValidProbability(p)) r + logProb(p) else r
    })
    val lPC = annotations.foldLeft(math.log(1-prior)) ((r,annotation) => {
      val  p = annotation.getProbability
      if(isValidProbability(p)) r + logProb(1-p) else r
    })

これは、以前のバージョンとほぼ同じように機能します（Javaバージョンの3倍遅い）。それほど驚くことではありませんが、私は希望を持っていました。

だから私の質問は、Scalaコードをクリーンに保ち、不必要な可変性を避け、Scalaイディオムに従う一方で、このJavaスニペットをScalaに実装するより速い方法はありますか？最終的にはこのコードを並行環境で使用することを期待しているため、不変性を維持することの価値は、単一スレッドでのパフォーマンスの低下を上回る可能性があります。

4

5 に答える 5

4

まず、ペナルティの一部は、使用しているコレクションのタイプに起因する場合があります。しかし、そのほとんどはおそらくオブジェクトの作成であり、ループを 2 回実行することによって実際に回避することはできません。これは、数値をボックス化する必要があるためです。

代わりに、値を蓄積する可変クラスを作成できます。

class LogOdds(var lp: Double = 0, var lpc: Double = 0) {
  def *=(p: Double) = {
    if (isValidProbability(p)) {
      lp += logProb(p)
      lpc += logProb(1-p)
    }
    this  // Pass self on so we can fold over the operation
  }
  def toTuple = (lp, lpc)
}

これを危険に使用することはできますが、そうする必要はありません。実際、あなたはそれを折りたたむことができます。

annotations.foldLeft(new LogOdds()) { (r,ann) => r *= ann.getProbability } toTuple

このパターンを使用する場合、すべての変更可能な unsafe は折り畳みの中に隠されます。それは決して逃げません。

現在、平行折りはできませんが、断片を結合するための余分な操作を加えた折りのような集約を行うことができます。したがって、メソッドを追加します

def **(lo: LogOdds) = new LogOdds(lp + lo.lp, lpc + lo.lpc)

にLogOddsそしてそれから

annotations.aggregate(new LogOdds())(
  (r,ann) => r *= ann.getProbability,
  (l,r) => l**r
).toTuple

準備は万端です。

（これには数学以外の記号を自由に使用してください。ただし、基本的に確率を乗算しているため、組み込み確率などよりも、何が起こっているかについて直感的なアイデアを与える可能性が高いようです。）

于 2012-02-02T17:36:45.183 に答える
3

コンパイラによって while ループに変換される末尾再帰メソッドを実装できるため、Java バージョンと同じくらい高速になるはずです。または、単にループを使用することもできます。メソッドでローカル変数を使用するだけであれば、それに対する法律はありません (たとえば、Scala コレクションのソース コードでの広範な使用を参照してください)。

def calc(lst: List[Annotation], lP: Double = 0, lPC: Double = 0): (Double, Double) = {
  if (lst.isEmpty) (lP, lPC)
  else {
    val prob = lst.head.getProbability
    if (isValidProbability(prob)) 
      calc(lst.tail, lP + logProb(prob), lPC + logProb(1 - prob))
    else 
      calc(lst.tail, lP, lPC)
  }
}

折りたたみの利点は、並列化できることです。これにより、マルチコア マシンで Java バージョンよりも高速になる可能性があります (他の回答を参照)。

于 2012-02-02T18:10:45.293 に答える
2

まず、パフォーマンスの問題に対処しましょう。whileループを使用する以外に、Javaほど高速に実装する方法はありません。基本的に、JVMはJavaループを最適化する範囲でScalaループを最適化することはできません。その理由は、JVMの人々の間でも懸念されています。なぜなら、それはライブラリの取り組みと並行することにも邪魔になるからです。

さて、Scalaのパフォーマンスに戻ると.view、ステップで新しいコレクションを作成しないようにすることもできますが、ステップは常にパフォーマンスの低下につながるとmap思います。map重要なのは、コレクションをでパラメータ化されたものに変換しているということですDouble。これは、ボックス化およびボックス化解除する必要があります。

ただし、最適化する方法が1つあります。それは、並列化することです。並列コレクションにするように要求.parした場合は、次を使用できます。annotationsfold

val parAnnot = annotations.par
val lP = parAnnot.map(_.getProbability).fold(math.log(prior)) ((r,p) => {
   if(isValidProbability(p)) r + logProb(p) else r
})
val lPC = parAnnot.map(_.getProbability).fold(math.log(1-prior)) ((r,p) => {
  if(isValidProbability(p)) r + logProb(1-p) else r
})

map別の手順を回避するには、Rexが提案するように、aggregateの代わりにを使用します。fold

Futureボーナスポイントについては、両方の計算を並行して実行するために使用できます。ただし、タプルを元に戻して一度に実行すると、パフォーマンスが向上すると思います。何がうまく機能するかを確認するには、このようなものをベンチマークする必要があります。

並列コレクションではfilter、有効なアノテーションを最初に取得することで利益が得られる場合があります。または、おそらく、collect。

val parAnnot = annottions.par.view map (_.getProbability) filter (isValidProbability(_)) force;

また

val parAnnot = annotations.par collect { case annot if isValidProbability(annot.getProbability) => annot.getProbability }

とにかく、ベンチマーク。

于 2012-02-02T17:52:21.170 に答える
2

一種の補足として、次を使用することで、慣用的にリストを 2 回トラバースすることを避けることができますview。

val probs = annotations.view.map(_.getProbability).filter(isValidProbability)

val (lP, lPC) = ((logProb(prior), logProb(1 - prior)) /: probs) {
   case ((pa, ca), p) => (pa + logProb(p), ca + logProb(1 - p))
}

これでおそらく 3 番目のバージョンよりも優れたパフォーマンスが得られるわけではありませんが、私にはよりエレガントに感じられます。

于 2012-02-02T17:51:05.103 に答える
1

現在、ボックス化せずに scala コレクション ライブラリを操作することはできません。したがって、Java のプリミティブs は、たとえそれらを にラップしていなくてもdouble、操作で継続的にボックス化およびボックス化解除されます(これは特殊化されていますが、もちろん、毎回新しいオブジェクトを作成するパフォーマンスのオーバーヘッドを既に支払っています)。 .foldTuple2

于 2012-02-02T17:35:49.600 に答える