Как сгенерировать два набора одинакового размера с помощью 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$10@3d8314f0)))
> ARG_0_ORIGINAL: (Set(Man(3,1,scala.math.Ordering$$anon$10@2bea5ab4), Man(
  2,1,scala.math.Ordering$$anon$10@2bea5ab4), Man(2,3,scala.math.Ordering$$
  anon$10@2bea5ab4)),Set(Woman(1,1,scala.math.Ordering$$anon$10@3d8314f0), 
  Woman(3,2,scala.math.Ordering$$anon$10@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$2(Marriag
  eMarketSpecification.scala:54)
org.economicsl.matching.MarriageMarketSpecification$.$anonfun$new$2$adapted
  (MarriageMarketSpecification.scala:51)
org.scalacheck.Prop$.$anonfun$forAllShrink$2(Prop.scala:761)
Found 1 failing properties.

Process finished with exit code 1

Тест не пройден, потому что я включил требование, чтобы два входных набора были одинакового размера. Мое намерение состоит в том, чтобы генератор предоставил действительные входные данные.

Мысли

Answer 1

Мне удалось сгенерировать пары 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 2

Задача : Создайте генератор типа 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 для понимания

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 StackOverflowExample 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 3

Я наткнулся на следующее решение.

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)
}

Я не совсем уверен, почему оригинальные генераторы не работали, как ожидалось. Они, конечно, могли генерировать неуникальные экземпляры, но я подумал, что это должно было быть чрезвычайно редко (наверное, я ошибался!).