Controlar cómo se generan los datos de prueba en QuickCheck

Question

Escribí un algoritmo para encontrar una solución al problema de la suma de subconjuntos en Haskell. La firma es

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

QuickCheck parece ser una buena opción para probar eso. Por ejemplo, aquí I es una de las propiedades que pude comprobar:

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

El problema es que el algoritmo es muy computacionalmente intensivas y en funcionamiento 100 pruebas con grandes listas de entrada lleva años para correr.

Intenté con QuickCheck 1 y se ejecutó rápidamente, pero los conjuntos de datos utilizados para las pruebas fueron muy pequeños. Después de pasar a QuickCheck 2, parece ser el problema opuesto. Hay un a manual para QC, pero parece ser antiguo (no hay información de fecha) y no sé cuánto se aplica todavía a QC2. A Tutorial está disponible en Haskell Wiki pero no hay muchos detalles, solo unas pocas palabras sobre la instanciación de Arbitrary.

así que tengo dos preguntas:

• ¿Qué cambios en QuickCheck 2 que sea convertido en mucho más lento que QuickCheck?
• ¿Cuál es la mejor manera de controlar la creación de conjuntos de datos para que sean útiles para una prueba determinada?

Editar: Para ser más específicos, me gustaría probar mi solución con un tamaño de la lista de 0 a 100, que contiene números enteros entre -10000 y 10000.

Answer 1

Una cosa que QuickCheck 2 introdujo que podría ser una fuente de ineficiencia es la función shrink. Si una propiedad falla, entonces se llama a la función de contracción que otorga a los candidatos en valores de prueba más pequeños, y se reducen hasta que no pueden dar un valor menor por el cual falla la propiedad. Pero esto solo ocurre cuando las propiedades fallan.

Los cambios para la instancia arbitraria para las listas no ha cambiado mucho entre version 1 y version 2. La diferencia está en la redacción, la versión 1 usa vector, y la versión 2 usa una comprensión de la lista, pero luego vector se implementa con exactamente una comprensión de lista de llamadas secuenciadas a arbitrarias.

Ambas implementaciones usaron el parámetro de tamaño. En QuickCheck 1, el tamaño de es un valor generado por predeterminado div n 2 + 3, donde n es el número de la prueba. QuickCheck 2 utiliza otro enfoque, donde se configura el tamaño máximo y el número de pruebas. Los tamaños de prueba se distribuirán en ese rango, creciendo linealmente en el número de pruebas (consulte computeSize' en quickCheckWithResult). Esto significa que con la configuración predeterminada de 100 pruebas y tamaño máximo, el tamaño máximo de QuickCheck 1 sería (div 100 2 + 3) = 53, y con QuickCheck 2 sería simplemente 100.

Como la suma de subconjuntos es NP-completo es probable que tenga un algoritmo exponencial;) Entonces la diferencia en el tiempo de funcionamiento entre una lista de longitud 50 y 100 desde luego puede ser enorme. Es comprensible que desee listas pequeñas para probar. Tiene dos opciones de : cree un nuevo tipo de datos (preferiblemente con newtype) o haga de un generador autónomo y use forAll. Al usar newtype, puede también especificar cómo se deben reducir los valores. Este es un ejemplo de implementación utilizando el enfoque 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) 

este Arbitrary ejemplo, no hace que las listas de más de 50 elementos. Los elementos no usan el parámetro de tamaño, por lo que siempre están en en el rango [-10000,10000], por lo que hay margen de mejora. La función shrink simplemente usa los shrink disponibles para las listas y Int s.

Para utilizar esta instancia con su propiedad, sólo tiene que utilizar un SmallIntList como un argumento:

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