scala - 如何从 Scala 的集合中选择一个随机值

Question

我需要一种方法来从集合中统一选择一个随机值。

这是我目前的实现。

implicit class TraversableOnceOps[A, Repr](val elements: TraversableOnce[A]) extends AnyVal {
  def pickRandomly : A = elements.toSeq(Random.nextInt(elements.size))
}

但是这段代码实例化了一个新的集合，所以在内存方面并不理想。

有什么办法可以改善？

[更新] 让它与 Iterator 一起工作

  implicit class TraversableOnceOps[A, Repr](val elements: TraversableOnce[A]) extends AnyVal {
    def pickRandomly : A = {
      val seq = elements.toSeq
      seq(Random.nextInt(seq.size))
    }
  }

Answer 1

乍一看，如果不先计算元素就无法做到这一点，但您可以!

遍历序列 f 并以概率 1/i 取每个元素 fi:

def choose[A](it: Iterator[A], r: util.Random): A =
  it.zip(Iterator.iterate(1)(_ + 1)).reduceLeft((x, y) =>
    if (r.nextInt(y._2) == 0) y else x
  )._1

统一性的快速演示:

scala> ((1 to 1000000)
     | .map(_ => choose("abcdef".iterator, r))
     | .groupBy(identity).values.map(_.length))
res45: Iterable[Int] = List(166971, 166126, 166987, 166257, 166698, 166961)

Here's关于我不久前写的数学的讨论，虽然我担心它有点不必要的冗长。它还概括为选择任何固定数量的元素而不是一个。