如何使用 ScalaCheck 生成两个相同大小的集合

Question

我正在尝试为匹配算法开发基于属性的测试，我需要生成两个相同大小的输入集以输入算法。我目前的解决方案尝试如下。

case class Man(id: Long, quality: Long, ordering: Ordering[Woman])
case class Woman(id: Long, quality: Long, ordering: Ordering[Man])

val man: Gen[Man] = {
  for {
    id <- Gen.posNum[Long]
    quality <- Gen.posNum[Long]
  } yield Man(id, quality, Man.womanByQuality)
}

val woman: Gen[Woman] = {
  for {
    id <- Gen.posNum[Long]
    quality <- Gen.posNum[Long]
  } yield Woman(id, quality, Woman.manByQuality)
}  

def setOfN[T](n: Int, g: Gen[T]): Gen[Set[T]] = {
  Gen.containerOfN[Set, T](n, g)
}

def unMatched: Gen[(Set[Man], Set[Woman])] = Gen.sized {
  n => setOfN(n, man).flatMap(ms => setOfN(ms.size, woman).map(ws => (ms, ws)))
}

这会根据需要生成输入集的元组，但不能保证它们的大小相同。当我运行测试使用...

property("all men and women are matched") = forAll(unMatched) {
  case (ms, ws) =>
    println((ms.size, ws.size))
    val matches = DeferredAcceptance.weaklyStableMatching(ms, ws)
    (matches.size == ms.size) && (matches.size == ws.size)
}

控制台会打印类似...

(0,0)
(1,1)
(2,2)
(3,2)
(1,2)
(0,2)
(0,1)
(0,0)
! marriage-market.all men and women are matched: Exception raised on proper
  ty evaluation.
> ARG_0: (Set(),Set(Woman(1,1,scala.math.Ordering$$anon@3d8314f0)))
> ARG_0_ORIGINAL: (Set(Man(3,1,scala.math.Ordering$$anon@2bea5ab4), Man(
  2,1,scala.math.Ordering$$anon@2bea5ab4), Man(2,3,scala.math.Ordering$$
  anon@2bea5ab4)),Set(Woman(1,1,scala.math.Ordering$$anon@3d8314f0), 
  Woman(3,2,scala.math.Ordering$$anon@3d8314f0)))
> Exception: java.lang.IllegalArgumentException: requirement failed
scala.Predef$.require(Predef.scala:264)
org.economicsl.matching.DeferredAcceptance$.weaklyStableMatching(DeferredAc
  ceptance.scala:97)
org.economicsl.matching.MarriageMarketSpecification$.$anonfun$new(Marriag
  eMarketSpecification.scala:54)
org.economicsl.matching.MarriageMarketSpecification$.$anonfun$new$adapted
  (MarriageMarketSpecification.scala:51)
org.scalacheck.Prop$.$anonfun$forAllShrink(Prop.scala:761)
Found 1 failing properties.

Process finished with exit code 1

测试失败，因为我要求两个输入集的大小必须相等。我的意图是生成器应该提供有效的输入数据。

想法？

Answer 1

我偶然发现了以下解决方案。

def unMatched: Gen[(Set[Man], Set[Woman])] = Gen.sized {
  n => setOfN(n, man).flatMap(ms => setOfN(ms.size, woman).map(ws => (ms, ws))).suchThat { case (ms, ws) => ms.size == ws.size }
}

但我认为没有必要使用 suchThat 组合器。问题似乎是 size 参数被视为容器大小的上限（而不是等式约束）。

根据@FlorianK

的评论更新

我发现问题出在我对 Man 和 Woman 生成器的规范上。这些生成器不是生成器不同的值。我没有使用正数 Long 来表示唯一的 id，而是改用 Java UUID。正确的生成器是

val man: Gen[Man] = {
  for {
    id <- Gen.uuid
    quality <- Gen.posNum[Long]
  } yield Man(id, quality, Man.womanByQuality)
}

val woman: Gen[Woman] = {
  for {
    id <- Gen.uuid
    quality <- Gen.posNum[Long]
  } yield Woman(id, quality, Woman.manByQuality)
}

我不太清楚为什么原来的发电机没有按预期工作。他们当然有可能生成非唯一实例，但我认为这应该是非常罕见的（我猜我错了！）。

Answer 2

我使用以下代码成功生成了一对 List[Int] 大小相等的代码：

val pairOfListGen = Gen.sized { size => for {
    x <- Gen.containerOfN[List, Int](size, Gen.choose(0,50000))
    y <- Gen.containerOfN[List, Int](size, Gen.choose(0,50000))
  } yield (x,y)
}

Man.womanByQuality 未在您的代码示例中定义，因此我无法使用您的生成器对其进行测试，但我希望这对您有用。

Answer 3

问题：构造一个类型为Gen[(Set[T],Set[U])]的生成器，使得对于生成的每一对集合，该对中的每个集合都具有相同的大小。

下面的函数

import org.scalacheck.Gen
def genSameSizeSets[T,U](gt: Gen[T], gu: Gen[U]): Gen[(Set[T],Set[U])] = {
  for { n      <- Gen.posNum[Long] // or .oneOf(1 to MAX_SET_SIZE)
        tset   <- Gen.containerOfN[Set,T](n, gt)
        uset   <- Gen.containerOfN[Set,U](n, gu)
        minsize = Math.min(tset.size, uset.size)
  } yield (tset.take(minsize), uset.take(minsize))
}

构建所需的生成器。

这个生成器的一个关键点是它完全避免了丢弃候选人。

containerOfN 本身不能保证结果 Set 的大小，因为这需要 gt 和 gu 生成 n 连续的不同值。

另一种实现方式是在为了理解

if tset.size == uset.size

这可能是第一次尝试。它不是一个强大的生成器，因为它有很高的丢弃率并且 ScalaCheck 在通过之前就放弃了。

在这种情况下，有一个简单的出路。不是丢弃不匹配的候选者，而是将较大的候选者强制为与较小的（仍然是非空的）相同的大小。由于设置值是任意的，因此丢弃哪些并不重要。这个逻辑是用 Math.min 和 take.

实现的

这似乎是良好生成器设计的重要原则：“避免像瘟疫一样丢弃”。

这是一个完整的工作示例：

import org.scalacheck.Properties
import org.scalacheck.Gen
import org.scalacheck.Arbitrary
import org.scalacheck.Prop.{forAll,collect}

object WhosebugExample extends Properties("same size sets") {

  def genSameSizeSets[T,U](gt: Gen[T], gu: Gen[U]): Gen[(Set[T],Set[U])] = {
    for { n <- Gen.posNum[Int]
          ts <- Gen.containerOfN[Set,T](n, gt)
          us <- Gen.containerOfN[Set,U](n, gu)
          if us.size == ts.size
          minsize = Math.min(ts.size, us.size)
    } yield (ts.take(minsize), us.take(minsize))
  }

  val g = genSameSizeSets(Arbitrary.arbitrary[Int], Arbitrary.arbitrary[Char])

  property("same size")  = forAll(g) { case (intSet, charSet) =>
    collect(intSet.size, charSet.size) { intSet.size == charSet.size }
  }


}

使用此输出

+ same size sets.same size: OK, passed 100 tests.
> Collected test data: 
8% (11,11)
7% (2,2)
7% (17,17)
6% (16,16)
<snip>
1% (44,44)
1% (27,27)
1% (26,26)
1% (56,56)

Answer 4

刚回答了crpyt的相关问题

def pairOfLists[T1, T2](t1g: Gen[T1], t2g: Gen[T2]): Gen[List[(T1, T2)]] = for {
  t1s <- Gen.listOf(t1g)
  t2s <- Gen.listOfN(t1s.size * 3, t2g).suchThat(_.size >= t1s.size)
} yield t1s.zip(t2s.take(t1s.size))

注意 suchThat 会丢弃 t2s 个太小的候选项，这会导致生成器更快失败； t1s.size * 3 试图通过增加 t2s 候选人的可能性来减轻这种情况，该候选人比必要的更大，然后用 t2s.take(t1s.size)

缩短

如何使用 ScalaCheck 生成两个相同大小的集合

How to generate two sets of the same size using ScalaCheck

scala

scalacheck