Ответ 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
...