割り付けやvarsを避けながら、scalaのリストを効率的に折りたたむ

Question

リストにはたくさんの項目がありますが、どれくらいの項目が「完全」であるかを調べるにはコンテンツを分析する必要があります。私はパーティションで始まったが、その後、私は戻って二つのリストを必要としなかったことに気づいたので、私は倍に切り替え：

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 はになる可能性がありますが、折りたたまれたすべてのアイテムに新しいタプルが割り当てられることを理解しているので、これは疑わしいです）。

当分の間、私はGCが修正されていますが、VARSを紹介

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

としてこれを書き換えました。

GCを悪用せずに、varsを使用せずにこれを行う方法があるのだろうか？

編集：私は受け取った回答に

ハードコール。 var実装はより機能的ですが同等でなければならないtail-recursive最適化バージョンよりも大きなリスト（40％など）ではかなり高速です。

dhgからの最初の答えは、tail-recursiveのパフォーマンスと同じレベルにあるように見えます。これは、サイズパスが超効率的であることを意味しています...実際、最適化すると、私のハードウェア上の再帰的なもの。

Answer 1

あなたは既に回答を受け付けていますが、その解決策がリストを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) 
    } 

先ほどInt S（プリミティブ）の代わりに、タプル（参照型）である2つのアキュムレータを使用する以外これは、効果的にだけカスタマイズfoldあります。また、varsのwhileループと同様に効率的でなければなりません。実際、バイトコードは同一でなければなりません。

Answer 2

あなたのアキュムレータを再使用することができます場合は特に、そのように、変更可能なアキュムレータパターンを使用するように、わずかに整然とです：

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を非表示にすることができますしたい場合は、そうでなければ、まだヴァルスのパターンよりもはるかに自己完結型です。

Answer 3

あなたはそうのような違いを使用して、それを計算することができます：

def counts(groupRows: List[Row]) = { 
    val complete = groupRows.foldLeft(0){ (pair, row) => 
    if(row.time == 0) pair + 1 else pair 
    } 
    (complete, groupRows.length - complete) 
} 

Answer 4

クリーンな2パス・ソリューションがちょうどビルトインcount方法を使用することが考えられます：

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

をしかし、あなたができますイテレーターで

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

を使用すると、1回のパスでそれを行いますこれは、新しい返されたイテレータがバックグラウンドでリンクされ、 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) 

Answer 5

多分それは私だけだが、私は、彼らならば、様々な専門的な折り目（.size、.exists、.SUM、.product）を使用して好みますご利用いただけます。私はそれが一般的な折り畳みの強力な力よりもはっきりしていてエラーを起こしにくいことがわかります。

val complete = groupRows.view.filter(_.time==0).size 
(complete, groupRows.length - complete) 

Answer 6

OK、上記の答えに触発されたが、実際のみに望むことは一度リスト上を通過し、GCを避けるため、私が直接APIのサポートの欠如の顔に、私は私にこれを追加することを決めました中央図書館コード：

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

と、私が欲しいものを得る：最適化されたGC自分のアプリケーションのコードで次に

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のない表現を書くことができます（私は、暗黙的にインポートした場合） - 友好的なルーチンのtha私がヴァルスでプログラムの残りの部分を汚染するのを防ぎます。リスト上の複数のパスがすべてのケースでブール関数を使用して数字

でより明白だったように、長いリストを使用し

• ：

  しかし、私はその後、ルイージのベンチマークを見て、それを更新します私たちは、物事を比較しているように、かなり

http://pastebin.com/2XmrnrrB

VARの実装でも、かなり速く間違いですLuigiのルーチンは同一でなければならないが（最適化された末尾再帰で期待されるように）驚くべきことに、dhgのデュアルパスオリジナルは、テール再帰的なものと同じくらい速い（コンパイラの最適化があれば少し速い）。私はなぜなのか理解していない。

Answer 7

これはどうですか。輸入税なし。

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." 
}