控制如何在QuickCheck中生成测试数据 [英] Controlling how test data is generated in QuickCheck

问题描述

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

  subsetSum ::（Ord a，Num a）=> [a]  - > a  - >也许[a] 
  

QuickCheck似乎很适合测试它。例如，我在这里是我可以检查的一个属性：

  prop_sumEqualsS ls = case subsetSum ls of 
 Just解决方案 - > （求和解）== s 
 Nothing  - >真正的
  

问题在于算法计算密集，运行100次大输入列表测试需要很长时间跑步。

我尝试过使用QuickCheck 1，它运行得很快，但用于测试的数据集非常小。在转到QuickCheck 2之后，它似乎是相反的问题。质量控制有手册，但似乎很旧（没有日期信息）我不知道QC2还有多少适用。 教程可在Haskell Wiki上找到，但没有太多细节，只需简单介绍一下实例化任意。

所以我有两个问题：

• QuickCheck 2中的哪些更改使其变得比QuickCheck慢很多？


• 控制数据集创建以使其对指定测试有用的最佳方法是什么？
>

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

解决方案

QuickCheck 2引入的一件事可能是
低效率的来源是 shrink 函数。如果一个属性失败，那么
就会调用这个缩小函数，这个函数可以为候选人提供更小的
测试值，并且它们会缩小，直到它们不能给出属性失败的
更小的值。但是，只有
才会出现属性失败。

列表任意实例的更改在 ：//hackage.haskell.org/packages/archive/QuickCheck/1.2.0.1/doc/html/src/Test-QuickCheck.html#Arbitraryrel =noreferrer> version 1
和版本2 。
区别在于措词，版本1使用 vector ，版本2使用
a list comprehension，但是 vector 正好实现了这样一个列表理解
的任意序列调用。

两个实现都使用size参数。在QuickCheck 1中，
a生成值的大小是
default div n 2 + 3 ，其中 n 是测试的编号。
QuickCheck 2使用另一种方法，其中配置了最大大小
和测试次数。测试大小将在该范围内分布
，并在测试数量上呈线性增长（请参阅 quickCheckWithResult computeSize' $ C>）。
这意味着，默认设置为100次测试和最大大小，QuickCheck 1的最大大小
将为（div 100 2 + 3）= 53 ，并使用QuickCheck 2
，它仅仅是 100 。

子集和是NP完全的，你可能有一个指数算法;）
然后在长度为50到100 $ b的列表之间的运行时间差$ b当然可以是巨大的。可以理解你想要小列表来测试。您有两个
选择：创建一个新的数据类型（最好使用 newtype ）或使
a独立生成器，并使用 forAll 。通过使用 newtype ，您可以
指定如何缩小值。这是一个使用 newtype 方法的示例实现：

  newtype SmallIntList = SmallIntList [Int]派生（Eq，Show）
 
实例任意SmallIntList其中
任意=大小$ \s  - > 
n < - 选择（0，s`min` 50）
 xs < -  vectorOf n（选择（-10000,10000））
返回（SmallIntList xs）
缩小（SmallIntList xs）= map SmallIntList（缩小xs）
  

任意实例不会使列表超过50个元素。
元素不使用size参数，所以它们总是在
范围内 [ - 10000,10000] ，所以有一些空间改进。
shrink 函数简单地使用列表中的可用 shrink s和
Int s。

要在您的属性中使用此实例，只需使用 SmallIntList as
一个参数：

$ p $ prop_sumEqualsS（SmallIntList l）s = case子集
。 ..


I wrote an algorithm to find a solution to the subset sum problem in Haskell. The signature is

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

QuickCheck seems to be a good fit to test that. For example I here is one of the properties that I could check:

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

The problem is that the algorithm is quite computationally intensive and running 100 tests with big input lists takes ages to run.

I tried with QuickCheck 1 and it did run quickly, but the data sets used for testing were very small. After moving to QuickCheck 2 it seems to be the opposite problem. There is a manual for QC but it seems to be old (there is no date information) and I don't know how much still applies to QC2. A Tutorial is available on the Haskell Wiki but there is not much details, just a few words on instantiating Arbitrary.

So I have two questions:

• What changes in QuickCheck 2 make it become so much slower than QuickCheck?
• What is the best way to control data sets creation to make them useful for a given test?

Edit: To be more specific, I would like to test my solution with a list size from 0 to 100, containing integers between -10000 and 10000.

解决方案

One thing that QuickCheck 2 introduced that could be a source of inefficiency is the shrink function. If a property fails, then the shrink function is called which gives candidates on smaller test values, and they are shrunk until they cannot give a smaller value for which the property fails. But this only happens when properties fail.

The changes for the arbitrary instance for lists has not changed much between version 1 and version 2. The difference is in wording, version 1 uses vector, and version 2 uses a list comprehension, but then vector is implemented with exactly such a list comprehension of sequenced calls to arbitrary.

Both implementations used the size parameter. In QuickCheck 1, the size of a generated value is by default div n 2 + 3, where n is the number of the test. QuickCheck 2 uses another approach, where the maximum size and the number of tests is configured. The test sizes will be distributed in that range, growing linearly in the number of tests (see computeSize' in quickCheckWithResult). This means, with the default setting of 100 tests and maximum size, the maximum size from QuickCheck 1 would be (div 100 2 + 3) = 53, and with QuickCheck 2 it would simply be 100.

As subset sum is NP-complete you probably have an exponential algorithm ;) Then the difference in running time between a list of length 50 and 100 can of course be enormous. Understandably you want small lists to test with. You have two choices: make a new data type (preferably with newtype) or make a stand-alone generator and use forAll. By using newtype you can also specify how values should be shrunk. This is an example implementation using the newtype approach:

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)

This Arbitrary instance does not make lists longer than 50 elements. The elements do not use the size parameter, so they are always in the range [-10000,10000], so there is some room for improvement. The shrink function simply uses the available shrinks for lists and Ints.

To use this instance with your property, just use a SmallIntList as an argument:

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

这篇关于控制如何在QuickCheck中生成测试数据的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！