haskell - test - quick check near me

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 un buen ajuste para probar eso. Por ejemplo, aquí es una de las propiedades que podría verificar:

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

El problema es que el algoritmo es muy intensivo en computación y la ejecución de 100 pruebas con grandes listas de entrada lleva mucho tiempo.

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

Así que tengo dos preguntas:

• ¿Qué cambios en QuickCheck 2 hacen que sea 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?

Edición: para ser más específico, me gustaría probar mi solución con un tamaño de lista de 0 a 100, que contenga números enteros entre -10000 y 10000.

Answer 1

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

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

Ambas implementaciones utilizaron el parámetro tamaño. En QuickCheck 1, el tamaño de un valor generado es por defecto 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 simplemente sería 100 .

Como la suma de los subconjuntos es NP-completa, probablemente tenga un algoritmo exponencial;) Por supuesto, la diferencia en el tiempo de ejecución entre una lista de longitudes 50 y 100 puede ser enorme. Es comprensible que quieras probar con pequeñas listas. Tiene dos opciones: crear un nuevo tipo de datos (preferiblemente con newtype ) o hacer un generador independiente y usar para forAll . Al utilizar newtype , también puede especificar cómo deben reducirse los valores. Esta es una implementación de ejemplo que utiliza 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)

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

Para usar esta instancia con su propiedad, solo use un SmallIntList como argumento:

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