Controllo del modo in cui i dati del test vengono generati in QuickCheck

Question

Ho scritto un algoritmo per trovare una soluzione al problema della somma dei sottoinsiemi in Haskell. La firma è

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

QuickCheck sembra essere una buona misura per testare questo. Per esempio ho qui è una delle proprietà che ho potuto verificare:

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

Il problema è che l'algoritmo è abbastanza computazionalmente intensive e l'esecuzione di 100 test con grandi liste di input prende le età per l'esecuzione.

Ho provato con QuickCheck 1 ed è stato eseguito rapidamente, ma i set di dati utilizzati per il test erano molto piccoli. Dopo essersi trasferito su QuickCheck 2 sembra essere il problema opposto. C'è il a manual per il controllo qualità ma sembra essere vecchio (non ci sono informazioni sulla data) e non so quanto ancora si applichi a QC2. A Tutorial è disponibile su Haskell Wiki ma non ci sono molti dettagli, solo poche parole sulla creazione di istanze Arbitrary.

Così ho due domande:

• Cosa cambia in QuickCheck 2 farlo diventare così molto più lento di QuickCheck?
• Qual è il modo migliore per controllare la creazione di insiemi di dati per renderli utili per un determinato test?

Edit: Per essere più precisi, vorrei provare la mia soluzione con una dimensione lista da 0 a 100, contenente interi tra -10000 e 10000.

Answer 1

Una cosa che QuickCheck 2 introdotto che potrebbe essere una fonte di inefficienza è la funzione shrink. Se una proprietà non riesce, viene chiamata la funzione di compattazione che assegna i candidati ai valori di prova più piccoli e vengono ridotti fino a quando non è possibile fornire un valore inferiore a per il quale la proprietà ha esito negativo. Ma questo solo si verifica quando le proprietà falliscono.

I cambiamenti per l'istanza arbitrario per le liste non è cambiato molto tra version 1 e version 2. La differenza è nel testo, la versione 1 utilizza vector, e la versione 2 utilizza una comprensione di lista, ma poi vector è implementato esattamente con tale comprensione di lista di chiamate in sequenza su arbitrarie.

Entrambe le implementazioni hanno utilizzato il parametro dimensione. In QuickCheck 1, la dimensione di un valore generato è di predefinita div n 2 + 3, dove n è il numero del test. QuickCheck 2 utilizza un altro approccio, in cui è configurata la dimensione massima e il numero di test. Le dimensioni del test verranno distribuite in tale intervallo, crescendo linearmente nel numero di test (vedere computeSize' in quickCheckWithResult). Ciò significa che, con l'impostazione predefinita di 100 test e la dimensione massima, la dimensione massima da QuickCheck 1 sarebbe (div 100 2 + 3) = 53 e con QuickCheck 2 sarebbe semplicemente 100.

Poiché la somma di sottoinsieme è NP-completo, probabilmente si dispone di un algoritmo esponenziale;) Quindi la differenza nel tempo di esecuzione tra un elenco di lunghezza 50 e 100 può essere enorme. Comprensibilmente si vogliono testare le piccole liste. Hai due scelte : fare un nuovo tipo di dati (preferibilmente con newtype) o fare un generatore autonomo e utilizzare forAll. Utilizzando newtype è possibile specificare anche come i valori devono essere rimpicciolite. Questo è un esempio di implementazione utilizzando l'approccio 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) 

questo Arbitrary esempio non rende liste più di 50 elementi. Gli elementi non utilizzano il parametro di dimensione, in modo che siano sempre in gamma [-10000,10000], per cui v'è un certo margine di miglioramento. La funzione shrink utilizza semplicemente le disponibili shrink s per le liste e Int s.

Per utilizzare questa istanza con la vostra proprietà, basta usare un SmallIntList come argomento:

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