Подтвердить что ты не робот

Контроль того, как тестовые данные генерируются в QuickCheck

Я написал алгоритм для поиска решения проблемы суммирования подмножества в 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 Wiki, но деталей нет немного, всего несколько слов о создании экземпляра Arbitrary.

У меня есть два вопроса:

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

Одна вещь, которую представила QuickCheck 2, может быть источником неэффективность - это функция shrink. Если свойство терпит неудачу, тогда вызывается функция усадки, которая дает кандидатам меньшие тестовые значения, и они сокращаются до тех пор, пока они не смогут дать меньшее значение, для которого свойство терпит неудачу. Но это только происходит, когда свойства терпят неудачу.

Изменения для произвольного экземпляра для списков не изменились между версия 1 и версия 2. Разница заключается в формулировке, в версии 1 используется vector, а в версии 2 используется понимание списка, но тогда vector реализуется с точно таким пониманием списка последовательных вызовов произвольных.

В обеих реализациях использовался параметр размера. В QuickCheck 1 размер сгенерированное значение default div n 2 + 3, где n - номер теста. QuickCheck 2 использует другой подход, где максимальный размер и настроено количество тестов. Размеры теста будут распределены в этом диапазоне, линейно растет по количеству тестов (см. computeSize' в quickCheckWithResult). Это означает, что с установкой по умолчанию 100 тестов и максимальным размером максимальный размер из QuickCheck 1 будет (div 100 2 + 3) = 53, а с QuickCheck 2 это было бы просто 100.

Поскольку сумма подмножества NP-complete, вы, вероятно, имеете экспоненциальный алгоритм;) Тогда разница в времени выполнения между списком длины 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 для списков и Int с.

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

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