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

Question

当我使用ScalaCheck的Gen.pic时,我观察到以下意外行为,对我而言,这表明它的选择并不是随机的,即使它的文档是这样说的:

/** 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: http://stackoverflow.com/a/43825913/4169924
val g = Gen.pick(3, set).map { _.toList }
forAll (g) { s => println(s) }

在2个不同的运行中生成的3000个数字中,我得到了一个惊人的相似,非常随机的分布(数字是四舍五入的,只列出前5个,从这里开始的所有列表):

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

(免责声明:我找不到如何以其他方式创建表格)

计划2

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

在使用a的情况下List,数字似乎在范围的末尾"卡住"(两次运行时为3x1000个数字):

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

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

备注:我重复列表运行多达10次,并且经历了相同的分布,差异为+/- 1%,只是不想在这个奇怪的"表格"格式中列出所有数字.

计划3

为了稍微调整一下,我运行了第三个小片段,Set从List(程序2)创建(程序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次运行中的3*1000数字)在结尾时略有不同:

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

题

即使样本量不够(因为它永远不够)来说明真正的随机性,我也不禁质疑Gen.pick声称的随机性(就使用它开箱即用而言,我可能需要设置一些种子让它"更随机"工作,因为数字"卡住",频率几乎相同.

在查看Gen.pick源代码时,在#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源代码中,或在scala.util.Random文档中),但我有预感它可能与观察到的行为有关.这是预期的行为Gen.pick吗？如果是这样,我怎样才能获得"更多"随机选择？

Answer 1

虽然@ashawley的答案已被接受,但我认为这不正确.我认为这实际上是一个错误,它是由erik-stripe在2016年9月1日的提交引入的,而且该错误实际上是在行中

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

它应该是

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

这仍然不太正确.

我还期望你最后一个值的33%实际上是100%并且你没有考虑到你选择3个元素的事实所以你的所有统计数据都应该乘以3.所以对于3元素选择,最后一个元素是选择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)分支填充输出buf与第一n要素,之后始终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以及应该替换哪个元素.显然,当前代码总是选择每个元素,因为在计算时if (i < n)总是如此.这就是为什么你看到最后一个元素如此巨大的倾斜.isomething % n

显然,计划是使用Fisher-Yates shuffle的修改版本,只选择shuffle的第一个n元素并正确地执行它,你需要选择范围[0,count)中的随机数,这可能是为什么编写代码的原因写它的方式即保留counter内while循环.

使用% count仍然不太正确,因为这种简单的方法在不是count2的幂时不会产生均匀的分布.更公平的东西就像

    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)实现或org.scalacheck.Choose.chLng 以获取如何完成它的示例.它比仅仅更复杂,% count并且有充分的理由.为了说明它,请考虑以下示例.让我们假设您的源随机生成器生成均匀随机的3位值,即在[0,7]的范围内,并且您希望获得范围内的ranadom数,[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,这显然是不均匀的.这就是我之前引用的那些实现使用某种循环并丢弃源生成器生成的一些值的原因.它需要生产unifrom分布.