Steuern, wie Testdaten in QuickCheck generiert werden

Question

Ich schrieb einen Algorithmus, um eine Lösung für das Subset-Summenproblem in Haskell zu finden. Die Signatur lautet

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

QuickCheck scheint eine gute Passform zu sein, um das zu testen. Zum Beispiel ist ich hier eine der Eigenschaften, die ich überprüfen konnte:

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

Das Problem ist, dass der Algorithmus sehr rechenintensiv ist und 100 Tests mit großen Eingangslisten laufen dauert ewig zu laufen.

Ich versuchte mit QuickCheck 1 und es lief schnell, aber die zum Testen verwendeten Datensätze waren sehr klein. Nach dem Wechsel zu QuickCheck 2 scheint es das umgekehrte Problem zu sein. Es gibt a manual für QC, aber es scheint alt zu sein (es gibt keine Datumsinformationen) und ich weiß nicht, wie viel noch für QC2 gilt. A Tutorial ist auf der Haskell Wiki verfügbar, aber es gibt nicht viele Details, nur ein paar Worte über die Instanziierung Arbitrary.

So habe ich zwei Fragen:

• Was 2 in Quick ändert es so viel langsamer als Quick Check werden lassen?
• Wie können Sie die Erstellung von Datensätzen am besten steuern, damit sie für einen bestimmten Test nützlich sind?

Edit: Um genauer zu sein, ich möchte meine Lösung mit einer Liste der Größe von 0 bis 100, testen, ganze Zahlen zwischen -10000 und 10000.

Answer 1

Eine Sache, die Quick Check 2 enthält, eingeführt, dass könnte eine Quelle von Ineffizienz sein, ist die shrink Funktion. Wenn eine Eigenschaft fehlschlägt, wird die Schrumpffunktion aufgerufen, die Kandidaten auf kleineren Testwerten gibt, und sie werden geschrumpft, bis sie keinen kleineren Wert geben können, für den die Eigenschaft fehlschlägt. Aber dies geschieht nur passiert, wenn Eigenschaften fehlschlagen.

Die Änderungen für das willkürliche Beispiel für Listen haben viel zwischen version 1 und version 2 nicht verändert. Der Unterschied ist im Wortlaut, Version 1 verwendet vector, und Version 2 verwendet ein Listenverständnis, aber dann ist vector mit genau solch einem Listenverständnis von sequenziellen Aufrufen zu beliebig implementiert.

Beide Implementierungen verwendeten den Größenparameter. In QuickCheck 1 ist die Größe ein generierter Wert von default div n 2 + 3, wobei n die Nummer des Tests ist. QuickCheck 2 verwendet einen anderen Ansatz, bei dem die maximale Größe und die Anzahl der Tests konfiguriert ist. Die Testgrößen werden in diesem Bereich auf verteilt und wachsen linear in der Anzahl der Tests (siehe computeSize' in quickCheckWithResult). Das heißt, mit der Standardeinstellung von 100 Tests und maximaler Größe wäre die maximale Größe von QuickCheck 1 (div 100 2 + 3) = 53, und mit QuickCheck 2 wäre es einfach 100.

Da die Subsetsumme NP-vollständig ist, haben Sie wahrscheinlich einen Exponentialalgorithmus;) Dann kann der Unterschied in der Laufzeit zwischen einer Liste der Länge 50 und 100 natürlich enorm sein. Verständlicherweise möchten Sie mit kleinen Listen testen. Sie haben zwei Möglichkeiten: Erstellen Sie einen neuen Datentyp (vorzugsweise mit newtype) oder machen Sie einen eigenständigen Generator und verwenden Sie forAll. Mit newtype können Sie auch angeben, wie Werte geschrumpft werden sollen. Dies ist eine beispielhafte Implementierung des newtype Ansatz:

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) 

Diese Arbitrary Instanz macht keine Listen mehr als 50 Elemente. Die Elemente verwenden nicht den Größenparameter, daher befinden sie sich immer in im Bereich [-10000,10000], daher gibt es einige Verbesserungen. Die shrink Funktion verwendet einfach die verfügbaren shrink s für Listen und Int s.

Um diese Instanz mit Ihrer Eigenschaft zu verwenden, um nur ein Argument SmallIntList als verwenden:

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