属性 基于算法生成器的测试："Find the smallest positive integer that does not occur in a given sequence"

Question

我在学习使用 ScalaCheck 在 scala 中进行基于 属性 的测试时偶然发现了这个关于 Whosebug 的挑战。

我想尝试为这个问题编写一个基于生成器驱动的 属性 测试来检查我的程序的有效性，但似乎无法想到如何编写相关的测试用例.我知道我可以为这个用例编写一个基于 table 驱动的 属性 测试，但这限制了我可以用来测试这个算法的属性数量。

import scala.annotation.tailrec

object Solution extends App {
  def solution(a: Array[Int]): Int = {
    val posNums = a.toSet.filter(_ > 0)

    @tailrec
    def checkForSmallestNum(ls: Set[Int], nextMin: Int): Int = {
      if (ls.contains(nextMin)) checkForSmallestNum(ls, nextMin + 1)
      else nextMin
    }

    checkForSmallestNum(posNums, 1)
  }
}

Answer 1

使用 Scalatest（因为你做了标签 scalatest）Scalacheck 集成和 Scalatest 匹配器，比如

forAll(Gen.listOf(Gen.posNum[Int]) -> "ints") { ints =>
  val asSet = ints.toSet
  val smallestNI = Solution.solution(ints.toArray)
  asSet shouldNot contain(smallestNI)

  // verify that adding non-positive ints doesn't change the result
  forAll(
    Gen.frequency(
      1 -> Gen.const(0),
      10 -> Gen.negNum[Int]
    ) -> "nonPos"
  ) { nonPos =>
    // Adding a non-positive integer to the input shouldn't affect the result
    Solution.solution((nonPos :: ints).toArray) shouldBe smallestNI
  }

  // More of a property-based approach
  if (smallestNI > 1) {
    forAll(Gen.oneOf(1 until smallestNI) -> "x") { x =>
      asSet should contain(x)
    }
  } else succeed  // vacuous

  // Alternatively, but perhaps in a less property-based way
  (1 until smallestNI).foreach { x =>
    asSet should contain(x)
  }
}

请注意，如果 scalatest 设置为尝试 forAlls 100 次，嵌套的 属性 检查将检查值 10k 次。由于 smallestNI 几乎总是少于试验次数（因为 listOf 很少生成长列表），详尽检查实际上比嵌套 属性 检查快。

总的来说，如果某个东西是某个谓词适用的最小正整数，这就等于说对于所有小于该谓词不适用的东西的正整数。