使用算法生成器进行基于属性的测试：“查找给定序列中未出现的最小正整数”

Question

我在堆栈溢出上偶然发现了这个挑战，同时学习了使用 ScalaCheck 在 scala 中进行基于属性的测试。

求给定序列中不出现的最小正整数

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

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 的（因为您确实标记了最新）Scalacheck 集成和 Sca 最新匹配器，例如

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设置为尝试< code > for all 100次，嵌套属性检查将检查值10k次。因为< code>smallestNI几乎总是小于试验次数(因为< code>listOf很少生成长列表)，所以穷举检查实际上会比嵌套属性检查更快。

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