18

我编写了一个算法来解决 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 之间的整数。

4

1 回答 1

26

QuickCheck 2 引入的可能导致效率低下的一件事是该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 参数，所以总是在 range 内[-10000,10000]，所以还有一些改进的空间。该shrink函数只是将可用shrink的 s 用于列表和 Ints。

要将此实例与您的属性一起使用，只需使用 aSmallIntList作为参数：

prop_sumEqualsS (SmallIntList l) s = case subsetSum l s of
                                         ...
于 2012-04-03T11:13:44.910 回答