控制在QuickCheck中生成测试数据的方式

Question

我写了一个算法来找到Haskell中子集求和问题的解决方案.签名是

subsetSum :: (Ord a, Num a) => [a] -> a -> Maybe [a]

QuickCheck似乎非常适合测试它.例如,我在这里是我可以检查的属性之一:

prop_sumEqualsS l s = case subsetSum l s of
                        Just solution -> (sum solution) == s
                        Nothing       -> True

问题是该算法计算量很大,运行100个大输入列表的测试需要很长时间才能运行.

我尝试使用QuickCheck 1并且确实运行得很快,但用于测试的数据集非常小.转移到QuickCheck 2后,似乎是相反的问题.有QC 手册,但它似乎很旧(没有日期信息),我不知道QC2还有多少适用.Haskell Wiki上提供了一个教程,但没有太多细节,只有几个关于实例化的文字Arbitrary.

所以我有两个问题:

• QuickCheck 2中的哪些变化使它变得比QuickCheck慢得多？
• 控制数据集创建的最佳方法是什么,使它们对给定的测试有用？

编辑:更具体地说,我想测试我的解决方案,列表大小从0到100,包含-10000到10000之间的整数.

Answer 1

QuickCheck 2引入的一个可能是效率低下的原因是shrink功能.如果属性失败,则调用shrink函数,该函数为候选者提供较小的测试值,并且它们会缩小,直到它们无法给出属性失败的较小值.但这只发生在属性失败时.

在版本1 和版本2之间,列表的任意实例的更改没有太大变化.不同之处在于措辞,版本1使用vector,版本2使用列表理解,但随后vector实现了对任意序列调用的精确列表理解.

两种实现都使用size参数.在QuickCheck 1中,默认情况下生成的值的大小div n 2 + 3,其中n是测试的编号.QuickCheck 2使用另一种方法,其中配置了最大大小和测试数量.测试尺寸将分布在该范围内,在试验(见数目线性生长computeSize'中quickCheckWithResult).这意味着,默认设置为100次测试和最大尺寸,QuickCheck 1的最大尺寸将是(div 100 2 + 3) = 53,而QuickCheck 2就是这样100.

由于子集和是NP完全的,你可能有一个指数算法;)那么长度50和100的列表之间的运行时间差异当然是巨大的.可以理解的是,您希望使用小型列表进行测试.您有两种选择:创建新数据类型(最好使用newtype)或制作独立的生成器并使用forAll.通过使用,newtype您还可以指定如何缩小值.这是使用该newtype方法的示例实现:

newtype SmallIntList = SmallIntList [Int] deriving (Eq,Show)

instance Arbitrary SmallIntList where
  arbitrary = sized $ \s -> do
                 n <- choose (0,s `min` 50)
                 xs <- vectorOf n (choose (-10000,10000))
                 return (SmallIntList xs)
  shrink (SmallIntList xs) = map SmallIntList (shrink xs)

此Arbitrary实例不会使列表长于50个元素.元素不使用size参数,因此它们始终在范围内[-10000,10000],因此存在一些改进空间.该shrink函数只使用shrink列表和 Ints 的可用s.

要将此实例与您的属性一起使用,只需使用a SmallIntList作为参数:

prop_sumEqualsS (SmallIntList l) s = case subsetSum l s of
                                         ...