如何从Scala列表或数组中随机抽样？

Question

我希望从Scala列表或数组（不是RDD）中随机抽样，样本大小可以比列表或数组的长度长得多，我该如何以 高效 的方式实现？因为样本大小可能非常大，并且需要在不同的列表/数组上进行大量抽样。

我知道对于Spark RDD，我们可以使用takeSample()来实现，是否有与Scala列表/数组等价的方法呢？

非常感谢。

- Carter

---

随机数生成器是有状态的，因此列表没有这样的函数是没有意义的。您必须自己实现一个（而且它将是一个线性时间操作）。对于数组，您可以从“Random”对象中获取一个随机整数，如下所示：'Random.nextInt(myArray.length)'，然后索引到数组中。 - Felix

啊，算了。我读得太快了 xD - Felix

Answer 1

一个容易理解的版本看起来像这样：

import scala.util.Random

Random.shuffle(list).take(n)
Random.shuffle(array.toList).take(n)

// Seeded version
val r = new Random(seed)
r.shuffle(...)

- Marius Soutier

---

样本大小可以比列表或数组的长度更长。 - Felix

我知道take函数的工作原理，但你不觉得他是不是也意味着在这种情况下它应该给出一个比序列更大的样本？ - Felix

顺便问一下，你为什么要转换成列表？难道列表上的洗牌复杂度不是很高吗（我不知道具体实现）？ - Felix

啊，时间是线性的。那就没问题了:https://github.com/scala/scala/blob/v2.11.7/src/library/scala/util/Random.scala#L107-L122 - Felix

谢谢大家。是的，我需要有放回抽样，而且样本大小始终比数组/列表的长度要大得多，例如，我可能需要从长度为50的列表中抽取10,000个样本。 - Carter

Answer 2

对于数组：

import scala.util.Random
import scala.reflect.ClassTag

def takeSample[T:ClassTag](a:Array[T],n:Int,seed:Long) = {
  val rnd = new Random(seed)
  Array.fill(n)(a(rnd.nextInt(a.size)))
}

根据已给的种子生成一个随机数生成器（rnd）。接着，用从0到数组大小之间的随机数填充该数组。

最后一步是将每个随机值应用于输入数组的索引运算符。在REPL中使用它可能如下所示：

scala> val myArray = Array(1,3,5,7,8,9,10)
myArray: Array[Int] = Array(1, 3, 5, 7, 8, 9, 10)

scala> takeSample(myArray,20,System.currentTimeMillis)
res0: scala.collection.mutable.ArraySeq[Int] = ArraySeq(7, 8, 7, 3, 8, 3, 9, 1, 7, 10, 7, 10,
1, 1, 3, 1, 7, 1, 3, 7)

对于列表，我会将其转换为数组然后使用相同的函数。我怀疑你无论如何都不可能得到更高效的列表。

需要注意的是，使用列表的相同功能将花费 O(n^2) 的时间，而首先将列表转换为数组将花费 O(n) 的时间

- Felix

---

你的 takeSample 方法不必要地创建了包含索引的数组，然后进行映射。你应该考虑像这样做：Array.fill(n)(a(rng.nextInt(a.size)))。 - Jason Scott Lenderman

是的，那个无法编译。它无法找到所需的清单文件。你可能可以添加显式参数，这样它就能工作了。 - Felix

当我运行上面的代码时，我得到了以下结果。我做错了什么？ scala> takeSample(myArray,20,System.currentTimeMillis) res0: Array[() => Int] = Array(<function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>) - Max

请再试一次。我将其从 () => a(rnd.nextInt(a.size)) 更改为 a(rnd.nextInt(a.size))，并添加了 T 的类标签，以便数组的构建可以正常工作。现在请尝试 :) 对于不便我感到抱歉。 - Felix

Answer 3

如果你想进行无重复抽样，可以将其与随机数进行压缩，排序（时间复杂度为O(n*log(n)），丢弃随机数，然后进行抽样。请保留HTML标签。

import scala.util.Random
val l = Seq("a", "b", "c", "d", "e")
val ran = l.map(x => (Random.nextFloat(), x))
  .sortBy(_._1)
  .map(_._2)
  .take(3)

- KevinKatz

Answer 4

使用经典递归。

import scala.util.Random

def takeSample[T](a: List[T], n: Int): List[T] = {
    n match {
      case n: Int if n <= 0 => List.empty[T]
      case n: Int => a(Random.nextInt(a.size)) :: takeSample(a, n - 1)
    }
}

- Thomas Pocreau

---

尝试一下这个：takeSample(List(1,2,3),10000)，但是它会因为不是尾递归而崩溃。 - Felix

Answer 5

使用for推导式，对于给定的数组xs，如下所示，

for (i <- 1 to sampleSize; r = (Math.random * xs.size).toInt) yield a(r)

注意这里的随机生成器产生的值在单位间隔内，它们被缩放以覆盖数组的大小范围，并转换为Int以便在数组上进行索引。

请注意，对于纯函数式随机生成器，例如考虑Functional Programming in Scala中的 State Monad 方法，讨论见此处。

还要考虑NICTA，另一个纯函数式随机值生成器，其用法例如此处所示。

- elm

---

Math.random不是一种糟糕的实践吗？这几乎就是静态全局状态。 - Felix

在我看来，本地状态和全局状态之间存在巨大的差异。一个是糟糕的，另一个则更加可怕。 - Felix

Answer 6

虽然没有测试性能，但以下代码是一种简单而优雅的抽样方法，我相信它可以帮助那些只想获取抽样代码的人。根据您最终样本的大小来更改“range”。如果伪随机性不够满足您的需求，可以在内部列表中使用take(1)并增加范围。

Random.shuffle((1 to 100).toList.flatMap(x => (Random.shuffle(yourList))))

- ruhsuzbaykus

Answer 7

package your.pkg

import your.pkg.SeqHelpers.SampleOps

import scala.collection.generic.CanBuildFrom
import scala.collection.mutable
import scala.language.{higherKinds, implicitConversions}
import scala.util.Random

trait SeqHelpers {

  implicit def withSampleOps[E, CC[_] <: Seq[_]](cc: CC[E]): SampleOps[E, CC] = SampleOps(cc)
}

object SeqHelpers extends SeqHelpers {

  case class SampleOps[E, CC[_] <: Seq[_]](cc: CC[_]) {

    private def recurse(n: Int, builder: mutable.Builder[E, CC[E]]): CC[E] = n match {
      case 0 => builder.result
      case _ =>
        val element = cc(Random.nextInt(cc.size)).asInstanceOf[E]
        recurse(n - 1, builder += element)
    }

    def sample(n: Int)(implicit cbf: CanBuildFrom[CC[_], E, CC[E]]): CC[E] = {
      require(n >= 0, "Cannot take less than 0 samples")
      recurse(n, cbf.apply)
    }
  }
}

要实现这个功能：

• 将SeqHelpers混入到Scalatest规范中
• 包含import your.pkg.SeqHelpers._

然后以下内容应该可以正常工作：

Seq(1 to 100: _*) sample 10 foreach { println }

欢迎进行编辑以删除强制转换。

如果有一种方法可以在不预先知道具体类型的情况下创建集合的空实例作为累加器，请留言评论。尽管如此，建议使用构建器更为高效。

- Darren Bishop