18

Haskellの部分和問題の解を見つけるためのアルゴリズムを書きました。署名は

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

QuickCheckはそれをテストするのに適しているようです。たとえば、私はここで私がチェックできるプロパティの1つです：

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

問題は、アルゴリズムが非常に計算集約的であり、大きな入力リストを使用して100個のテストを実行すると、実行に時間がかかることです。

QuickCheck 1を試してみたところ、すぐに実行されましたが、テストに使用されたデータセットは非常に小さかったです。QuickCheck 2に移行した後は、逆の問題のようです。QCのマニュアルはありますが、古くなっているようで（日付情報がありません）、QC2にどれだけ当てはまるのかわかりません。チュートリアルはHaskellWikiで入手できますが、詳細はあまりなく、インスタンス化に関するいくつかの単語がありますArbitrary。

だから私は2つの質問があります：

  • QuickCheck 2のどのような変更により、QuickCheckよりも大幅に遅くなりますか？
  • データセットの作成を制御して、特定のテストに役立つようにするための最良の方法は何ですか？

編集：より具体的には、-10000から10000までの整数を含む、0から100までのリストサイズでソリューションをテストしたいと思います。

4

1 に答える 1

26

QuickCheck 2が導入した非効率性の原因の1つは、shrink機能です。プロパティが失敗した場合、縮小関数が呼び出され、より小さなテスト値の候補が提供され、プロパティが失敗したより小さな値を提供できなくなるまで縮小されます。ただし、これはプロパティが失敗した場合にのみ発生します。

リストの任意のインスタンスの変更は、バージョン1 とバージョン2の間であまり変更されていません。違いは言い回しにあり、バージョン1はを使用しvector、バージョン2はリスト内包を使用しますが、その後、vector任意のシーケンス呼び出しのまさにそのようなリスト内包で実装されます。

どちらの実装もサイズパラメータを使用しました。QuickCheck 1では、生成される値のサイズはデフォルトdiv n 2 + 3でです。ここnで、はテストの番号です。QuickCheck 2は、テストの最大サイズと数を構成する別のアプローチを使用します。テストサイズはその範囲に分散され、テストの数が直線的に増加します（を参照computeSize'）quickCheckWithResult。つまり、デフォルト設定の100テストと最大サイズでは、QuickCheck 1からの最大サイズはになり(div 100 2 + 3) = 53、QuickCheck2では単純にになります100。

サブセット和はNP完全であるため、おそらく指数アルゴリズムがあります;）その場合、長さ50と100のリスト間の実行時間の違いはもちろん非常に大きくなる可能性があります。当然のことながら、小さなリストでテストする必要があります。2つの選択肢があります。新しいデータ型を作成する（できればを使用して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要素より長いリストを作成しません。要素はサイズパラメータを使用しないため、常に範囲内[-10000,10000]にあるため、改善の余地があります。このshrink関数は、shrinkリストと Intsに使用可能なsを使用するだけです。

このインスタンスをプロパティで使用するSmallIntListには、引数としてaを使用します。

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