4

リストにたくさんのアイテムがあり、コンテンツを分析して、それらのいくつが「完了」しているかを調べる必要があります。パーティションから始めましたが、リストを 2 つ戻す必要がないことに気付き、フォールドに切り替えました。

val counts = groupRows.foldLeft( (0,0) )( (pair, row) => 
     if(row.time == 0) (pair._1+1,pair._2) 
     else (pair._1, pair._2+1)
   )

しかし、私は多くの並列ユーザーのために通過する行がたくさんあり、それが多くのGCアクティビティを引き起こしています(私の側の仮定... GCは他のものからのものである可能性がありますが、私はそれを理解しているのでこれを疑っています)折りたたまれたすべてのアイテムに新しいタプルを割り当てます)。

とりあえず、以下のように書き直しました

var complete = 0
var incomplete = 0
list.foreach(row => if(row.time != 0) complete += 1 else incomplete += 1)

これは GC を修正しますが、変数を導入します。

GCを悪用せずにvarを使用せずにこれを行う方法があるかどうか疑問に思っていましたか?

編集：

私が受け取った答えを強く求めます。var 実装は、より機能的であるが同等であるはずの末尾再帰最適化バージョンよりも、大きなリストでかなり高速 (40% など) のようです。

dhg からの最初の回答は、末尾再帰のパフォーマンスと同等のようです。これは、サイズ パスが非常に効率的であることを意味します。実際、最適化すると、末尾再帰よりもわずかに速く実行されます。私のハードウェア。

4

7 に答える 7

11

最もクリーンな 2 パス ソリューションは、おそらく組み込みのcountメソッドを使用することです。

val complete = groupRows.count(_.time == 0)
val counts = (complete, groupRows.size - complete)

partitionただし、イテレータで使用すると、1 つのパスで実行できます。

val (complete, incomplete) = groupRows.iterator.partition(_.time == 0)
val counts = (complete.size, incomplete.size)

これが機能するのは、新しく返された反復子が舞台裏でリンクされておりnext、一方を呼び出すと、一致する要素が見つかるまで元の反復子が前方に移動しますが、他方の反復子の一致しない要素は記憶されていないためです。再計算する必要があります。

ワンパス ソリューションの例:

scala> val groupRows = List(Row(0), Row(1), Row(1), Row(0), Row(0)).view.map{x => println(x); x}
scala> val (complete, incomplete) = groupRows.iterator.partition(_.time == 0)
Row(0)
Row(1)
complete: Iterator[Row] = non-empty iterator
incomplete: Iterator[Row] = non-empty iterator
scala> val counts = (complete.size, incomplete.size)
Row(1)
Row(0)
Row(0)
counts: (Int, Int) = (3,2)
于 2012-12-18T22:44:34.257 に答える
3

すでに回答を受け入れているようですが、その解決策がリストを2回トラバースすることを正しく述べています。それを効率的に行う方法は、再帰を使用することです。

def counts(xs: List[...], complete: Int = 0, incomplete: Int = 0): (Int,Int) = 
  xs match {
    case Nil => (complete, incomplete)
    case row :: tail => 
      if (row.time == 0) counts(tail, complete + 1, incomplete)
      else               counts(tail, complete, incomplete + 1)
  }

タプル (参照型) の代わりにfold単なる s (プリミティブ) である 2 つのアキュムレータを使用することを除いて、これは事実上単なるカスタマイズされた です。Intまた、vars を使用した while ループと同じくらい効率的である必要があります。実際、バイトコードは同一である必要があります。

于 2012-12-19T02:15:46.953 に答える
2

上記の回答に触発されましたが、実際にはリストを 1 回だけ渡し、GC を回避したいので、直接の API サポートがないことに直面して、これを中央ライブラリ コードに追加することにしました。

class RichList[T](private val theList: List[T]) {
  def partitionCount(f: T => Boolean): (Int, Int) = {
    var matched = 0
    var unmatched = 0
    theList.foreach(r => { if (f(r)) matched += 1 else unmatched += 1 })
    (matched, unmatched)
  }
}

object RichList {
  implicit def apply[T](list: List[T]): RichList[T] = new RichList(list)
}

次に、アプリケーション コードで (暗黙をインポートした場合)、var-free 式を記述できます。

val (complete, incomplete) = groupRows.partitionCount(_.time != 0)

そして、私が望むものを手に入れましょう。プログラムの残りの部分を vars で汚染するのを防ぐ、最適化された GC フレンドリーなルーチンです。

ただし、ルイージのベンチマークを見て、次のように更新しました。

  • リスト上の複数のパスが数字でより明確になるように、より長いリストを使用します
  • すべてのケースでブール関数を使用して、公平に比較​​できるようにします

http://pastebin.com/2XmrnrrB

Luigi のルーチンは (最適化された末尾再帰で予想されるように) 同じはずですが、var の実装は間違いなくかなり高速です。驚いたことに、dhg のデュアルパスのオリジナルは、末尾再帰のものと同じくらい高速です (コンパイラの最適化がオンの場合はわずかに高速です)。私はなぜなのか理解していない。

于 2012-12-19T01:03:55.143 に答える
2

多分それは私だけですが、利用可能な場合は、さまざまな特殊な折り畳み (.size、.exists、.sum、.product) を使用することを好みます。一般的な折り畳みの強力なパワーよりも明確で、エラーが発生しにくいと思います。

val complete = groupRows.view.filter(_.time==0).size
(complete, groupRows.length - complete)
于 2012-12-18T22:46:54.120 に答える
2

これはどう？輸入税なし。

import scala.collection.generic.CanBuildFrom
import scala.collection.Traversable
import scala.collection.mutable.Builder

case class Count(n: Int, total: Int) {
  def not = total - n
}
object Count {
  implicit def cbf[A]: CanBuildFrom[Traversable[A], Boolean, Count] = new CanBuildFrom[Traversable[A], Boolean, Count] {
    def apply(): Builder[Boolean, Count] = new Counter
    def apply(from: Traversable[A]): Builder[Boolean, Count] = apply()
  }
}
class Counter extends Builder[Boolean, Count] {
  var n = 0
  var ttl = 0
  override def +=(b: Boolean) = { if (b) n += 1; ttl += 1; this }
  override def clear() { n = 0 ; ttl = 0 }
  override def result = Count(n, ttl)
}

object Counting extends App {
  val vs = List(4, 17, 12, 21, 9, 24, 11)
  val res: Count = vs map (_ % 2 == 0)
  Console println s"${vs} have ${res.n} evens out of ${res.total}; ${res.not} were odd."
  val res2: Count = vs collect { case i if i % 2 == 0 => i > 10 }
  Console println s"${vs} have ${res2.n} evens over 10 out of ${res2.total}; ${res2.not} were smaller."
}
于 2012-12-19T03:35:02.203 に答える
0

特にアキュムレータを再利用できる場合は、可変アキュムレータ パターンを使用する方が少しきれいです。

case class Accum(var complete = 0, var incomplete = 0) {
  def inc(compl: Boolean): this.type = {
    if (compl) complete += 1 else incomplete += 1
    this
  }
}
val counts = groupRows.foldLeft( Accum() ){ (a, row) => a.inc( row.time == 0 ) }

本当にしたい場合は、変数をプライベートとして非表示にすることができます。そうでない場合でも、vars を使用したパターンよりもはるかに自己完結型です。

于 2012-12-18T22:15:14.387 に答える
0

次のように差を使用して計算できます。

def counts(groupRows: List[Row]) = {
  val complete = groupRows.foldLeft(0){ (pair, row) => 
    if(row.time == 0) pair + 1 else pair
  }
  (complete, groupRows.length - complete)
}
于 2012-12-18T22:21:19.467 に答える