2

Scala でa が与えられた場合、少なくとも 1回出現するすべての s のList[Int]を取得したいと考えています。またはを使用してこれを行うことができます。例えば：Set[Int]IntthreshgroupByfoldLeftfilter

val thresh = 3
val myList = List(1,2,3,2,1,4,3,2,1)
myList.foldLeft(Map[Int,Int]()){case(m, i) => m + (i -> (m.getOrElse(i, 0) + 1))}.filter(_._2 >= thresh).keys

を与えSet(1,2)ます。

List[Int]が非常に大きいとします。どのくらいの大きさかはわかりませんが、Ints 周波数のそれぞれについては気にしないので、いずれにせよこれは無駄に思えますthresh。合格したらthresh、もうチェックする必要はありません。 を に追加するだけIntですSet[Int]。

問題は、非常に大きなList[Int],

a) 真の正確な結果が必要な場合 (間違いの余地はありません)

b) 結果が概算である場合、たとえば、いくつかのハッシング トリックまたはブルーム フィルターを使用することによって、どこSet[Int]に誤検知が含まれる可能性があるか、{の頻度Int> thresh} が実際には aBooleanではなくDoublein であるかどうか[0-1]。

4

4 に答える 4

1

を使用しfoldleftて、次のように一致するアイテムを収集できます。

val tuple = (Map[Int,Int](), List[Int]())
myList.foldLeft(tuple) {
  case((m, s), i) => {
    val count = (m.getOrElse(i, 0) + 1) 
    (m + (i -> count), if (count == thresh) i :: s else s)
  }
}

小さなリストで約 40% のパフォーマンス向上を測定できたので、間違いなく向上しています...

List一定の時間がかかる (コメントを参照)を使用して先頭に追加するように編集されました。

于 2015-08-12T20:08:09.420 に答える
1

「より効率的に」とはスペース効率を意味する場合 (極端な場合、リストが無限である場合)、その中のアイテムの頻度を推定するために、Count Min Sketchと呼ばれる確率的データ構造があります。次に、頻度がしきい値を下回るものを破棄できます。

Algebirdライブラリからの Scala 実装があります。

于 2015-08-12T21:44:23.150 に答える
0

を使用して段階的にビルドされ、同時に を反復処理するためのフィルターとして使用される を使用して、foldLeft例を少し 変更できます。ただし、使用しているため、変更可能なマップを使用できず、間に合わせる必要があります。mutable.SetSeqwithFilterwithFilterfoldLeftforeach

import scala.collection.mutable

def getItems[A](in: Seq[A], threshold: Int): Set[A] = {
  val counts: mutable.Map[A, Int] = mutable.Map.empty
  val result: mutable.Set[A] = mutable.Set.empty

  in.withFilter(!result(_)).foreach { x =>
    counts.update(x, counts.getOrElse(x, 0) + 1)

    if (counts(x) >= threshold) {          
      result += x
    }
  }
  result.toSet
}

Seqそのため、最初の実行中に結果セットに既に追加された項目は破棄withFilterされSeqます。map, flatMap, foreachSeq

編集：

Aiveanが正しく指摘したように、私は自分のソリューションを使用しないように変更しましSeq.countたが、これはばかげていました。

Aiveansマイクロベンチを使用すると、彼のアプローチよりもまだわずかに遅いことがわかりますが、著者の最初のアプローチよりも優れています。

Authors solution
377
Ixx solution: 
399
Ixx solution2 (eliminated excessive map writes): 
110
Sascha Kolbergs solution: 
72
Aivean solution: 
54
于 2015-08-12T20:02:03.407 に答える