ScalaCheck 的 Gen.pick 真的是随机的吗？

Question

我在使用 ScalaCheck 时观察到以下意外行为 Gen.pic, which (for me) indicates that its picking is not quite random, even though its documentation 是这样说的：

/** A generator that picks a given number of elements from a list, randomly */

我运行以下三个小程序在设置

后按顺序（在2天的时间里，在不同的时间，这可能很重要）

implicit override val generatorDrivenConfig = PropertyCheckConfig(
  maxSize = 1000, 
  minSize = 1000, 
  minSuccessful = 1000)

获得合适的样本量。

程序#1

val set = Set(1,2,3,4,5,6,7,8,9,10,
      11,12,13,14,15,16,17,18,19,20,
      21,22,23,24,25,26,27,28,29,30,
      31,32,33,34,35,36,37,38,39,40,
      41,42,43,44,45,46,47,48,49,50)

// Thanks to @Jubobs for the solution
// See: 
val g = Gen.pick(3, set).map { _.toList }
forAll (g) { s => println(s) }

在 2 个不同的运行s 生成的 3000 个数字中，我得到了一个惊人的相似，并且非常非运行dom 分布（数字四舍五入，只列出前 5 个，至于所有从这里开始列出）：

Number: 运行#1 中的频率，运行#2 中的频率
15: 33%, 33%
47: 22%, 22%
4: 15%, 16%
19: 10%, 10%
30: 6%, 6%

（免责声明：除了 this way 之外，我找不到如何在此处创建 table）

节目 2

val list: List[Int] = List.range(1, 50)
val g = Gen.pick(3, list)
forAll (g) { s => println(s) }

在使用 List 的情况下，数字似乎在运行ge 的末尾得到 "stuck"（如果两个运行s 则为 3x1000 个数字):

49: 33%, 33%
48: 22%, 22%
47: 14%, 14%
46: 10%, 10%
45: 6%, 6%

有趣的是，频率与程序 1 的情况几乎相同。

备注：我对列表重复了运行s 多达 10 次，并且经历了非常相同的分布，只有 +/- 1% 的差异，只是没有我不想在此 st运行ge "table" 格式中列出所有数字。

节目 3

为了让事情更有趣，我运行第三个小片段，从 List（程序 2）创建 Set（程序 1）：

val set: Set[Int] = List.range(1, 50).toSet
val g = Gen.pick(3, set).map { _.toList }
forAll (g) { s => println(s) }

现在数字与程序 2 相同（List 获胜！），尽管频率（同样，对于 2 运行s 中的 3*1000 个数字）在结束：

49: 33%, 33%
48: 23%, 22%
47: 16%, 15%
46: 9%, 10%
45: 7%, 6%

问题

即使样本量不够（因为它永远不够）告诉 true 运行domness，我还是忍不住质疑 Gen.pick 声称运行domness（就开箱即用而言，我可能需要设置一些种子才能使其工作 "more" 运行domly），因为数得到 "stuck"，频率几乎相同。

查看 Gen.pick's source code 后，第 672 行使用了某个 seed0：

def pick[T](n: Int, l: Iterable[T]): Gen[Seq[T]] = {
    if (n > l.size || n < 0) throw new IllegalArgumentException(s"invalid choice: $n")
    else if (n == 0) Gen.const(Nil)
    else gen { (p, seed0) =>
    // ...

我在其他地方找不到定义（在 Gen.scala source code, or in scala.util.Random 文档中），但我有预感它可能与观察到的行为有关。这是 Gen.pick 的预期行为吗？如果是这样，我怎样才能获得 "more" 运行dom picking?

Answer 1

我认为这与种子无关。它与 Scalacheck 的启发式算法有关。

有一个微妙的错误。考虑它在做什么。它强迫自己在开始时选择值，然后运行domly 覆盖它们之后：

while (it.hasNext) {
  val t = it.next
  count += 1
  if (count <= n) {
    buf += t
  } else {
    val (x, s) = seed.long
    val i = (x & 0x7fffffff).toInt % n
    if (i < n) buf(i) = t
    seed = s
  }
  ...

运行domly 将这些元素分配给 else 块中的结果，这就是它优先考虑尾部值的原因。

因此，pick 是运行从集合中选择值。但是，它牺牲了在值之间进行平均选择并倾向于列表的末尾，因为代码试图延迟遍历列表。

要尝试均匀分布选取的元素，您需要知道集合的长度，但正如我的回答所暗示的，如果不使用可迭代对象两次，这是不可能的。

也许如果你运行 reverse 在你的名单上，或者 shuffle，你会得到更好的选择分布 pick。

因为 Scalacheck 是一个通用的属性测试库，我预测它不能在不牺牲任意大小集合的性能的情况下做这些事情。

更新

但是作为Alexey Romanov points out, this should implement the reservoir sampling算法，它避免了知道长度并且可以在O(n)时间内成为运行。代码中只有一个缺陷。修复只是更正了运行dom 数字生成的行。它应该得到从 1 到列表中访问的第 k 个 (count) 元素的运行dom 编号。

val i = (x & 0x7fffffff).toInt % n

应该是：

val i = (x & 0x7fffffff).toInt % count

我已经向 Scalacheck 提交了 PR：

https://github.com/rickynils/scalacheck/pull/333

Answer 2

尽管@ashawley 的回答已被接受，但我认为它不正确。我认为这实际上是一个错误，它是由 erik-stripe's commit on Sep 1, 2016 引入的，错误实际上在

行中

      val i = (x & 0x7fffffff).toInt % n

本来应该是

      val i = (x & 0x7fffffff).toInt % count

这还是不太正确。

我还希望你的最后一个值的 33% 实际上是 100% 而你没有考虑到你 select 3 个元素的事实所以您所有的统计数据都应乘以 3。因此，对于 3 元素 selection，最后一个元素是 selected 100% 的时间，前一个 - 66.6%等等，比你想象的还要糟糕

再次摘录代码：

else gen { (p, seed0) =>
  val buf = ArrayBuffer.empty[T]
  val it = l.iterator
  var seed = seed0
  var count = 0
  while (it.hasNext) {
    val t = it.next
    count += 1
    if (count <= n) {
      buf += t
    } else {
      val (x, s) = seed.long
      val i = (x & 0x7fffffff).toInt % n
      if (i < n) buf(i) = t
      seed = s
    }
  }
  r(Some(buf), seed)
}

那么这段代码应该做什么以及它实际做了什么？ if (count <= n) 分支用第一个 n 元素填充输出 buf，之后 else 分支总是有效。为了更清楚，我将 while 移动 if 更改为以下代码：

  for (i <- 0 until  n) {
    val t = it.next
    buf += t
  }
  while (it.hasNext) {
    val t = it.next
    val (x, s) = seed.long
    val i = (x & 0x7fffffff).toInt % n
    if (i < n) buf(i) = t
    seed = s
  }

所以现在很明显 else 分支应该同时决定是否应该将当前元素添加到输出 buf 以及它应该替换那里的哪个元素。显然，当前代码总是 select 每个元素，因为 if (i < n) 总是正确的，因为 i 被计算为 something % n。这就是为什么你会看到最后一个元素出现如此巨大的偏差。

显然，计划是使用 Fisher–Yates shuffle 的修改版本，select 只是洗牌的第一个 n 元素，要正确执行此操作，您需要 select [0, count) 范围内的随机数，这可能就是为什么代码是这样写的，即在 while 循环中保留 counter 。

使用 % count 仍然不太正确，因为当 count 不是 2 的幂时，这种简单的方法不会产生均匀分布。更公平地说，像

    val c0 = choose(0, count-1)
    val rt: R[Int] = c0.doApply(p, seed)        
    seed = rt.seed      
    val i = rt.retrieve.get // index to swap current element with. Should be fair random number in range [0, count-1], see Fisher–Yates shuffle
    if (i < n) buf(i) = t

或其他一些方法来创建 i 作为在这样一个范围内的公平均匀分布的随机数应该被使用。

更新（为什么只是% count是错误的）

您可以查看 java.util.Random.nextInt(int) implementation or org.scalacheck.Choose.chLng 的示例，了解应该如何完成。它比 % count 更复杂，这是有充分理由的。为了说明它，请考虑以下示例。假设您的源随机生成器生成均匀随机的 3 位值，即仅在 [0, 7] 范围内，并且您希望获得范围 [0, 2] 内的随机数，只需执行

srcGenerator.nextInt() % 3

现在考虑将范围 [0, 7] 中的值映射到您的范围 [0, 2]：

0, 3, 6 将映射到 0（即映射了 3 个值）
1, 4, 7 将映射到 1（即映射了 3 个值）
2, 5 将映射到 2（即仅映射 2 个值）

因此，如果您只是 % 3，您的分布将是 0 - 3/8、1 - 3/8、2 - 2/8，这显然是不均匀的。这就是为什么我之前引用的那些实现使用某种循环并丢弃源生成器生成的一些值的原因。要求生产统一分布。

ScalaCheck 的 Gen.pick 真的是随机的吗？

Is ScalaCheck's Gen.pick really random?

random

scala

scalacheck

更新