Управление созданием тестовых данных в QuickCheck - PullRequest
Новая
       16

Управление созданием тестовых данных в QuickCheck

17 голосов
/ 02 апреля 2012

Я написал алгоритм, чтобы найти решение проблемы суммы подмножеств в Haskell.Подпись 

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

QuickCheck, кажется, подходит для проверки этого.Например, вот одно из свойств, которое я мог проверить: 

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

Проблема заключается в том, что алгоритм является достаточно сложным в вычислительном отношении, и запуск 100 тестов с большими входными списками занимает много времени.

Я пытался с QuickCheck 1, и он работал быстро, но наборы данных, используемые для тестирования, были очень маленькими.После перехода на QuickCheck 2 кажется, что проблема противоположна.Существует руководство для QC, но оно кажется старым (информация о дате отсутствует), и я не знаю, сколько еще применимо к QC2. Учебное пособие доступно на вики-сайте Haskell, но подробностей немного, всего несколько слов о создании экземпляра Arbitrary.

Итак, у меня два вопроса:

  • Какие изменения в QuickCheck 2 делают его намного медленнее, чем QuickCheck?
  • Каков наилучший способ управления созданием наборов данных, чтобы сделать их полезными для данного теста?

Редактировать: Если быть более точным, я хотел бы протестировать свое решение с размером списка от 0 до 100, содержащим целые числа от -10000 до 10000.

1 Ответ

25 голосов
/ 03 апреля 2012

Одна вещь, представленная QuickCheck 2, которая может стать источником неэффективности, - это функция 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, а с QuickCheck 2 он будет просто 100.

Так как сумма подмножеств является NP-полной, у вас, вероятно, есть экспоненциальный алгоритм;) Тогда разница во времени выполнения между списком длиной 50 и 100, конечно, может быть огромной.Понятно, что вы хотите, чтобы небольшие списки для тестирования.У вас есть два варианта: создать новый тип данных (желательно с 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 s для списков и Int s.

Чтобы использовать этот экземпляр с вашим свойством, просто используйте SmallIntList в качестве аргумента: 

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