QuickCheck에서 테스트 데이터 생성 방법 제어

Question

하스켈에서 부분 집합 합계 문제에 대한 해결책을 찾기위한 알고리즘을 작성했습니다. 서명은

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에는 a manual이 있지만 오래되었으므로 (날짜 정보가 없음) QC2에 얼마나 많이 적용되는지 모릅니다. A Tutorial은 하스켈 위키에서 사용 가능하지만 자세한 내용은 많지 않습니다. Arbitrary을 인스턴스화하는 데 대한 몇 마디. QuickCheck 2에 어떤 변화

• 가 너무 느린 QuickCheck보다가 되십시오 :

  그래서 나는이 개 질문이?

• 주어진 테스트에 유용하도록 데이터 세트 생성을 제어하는 ​​가장 좋은 방법은 무엇입니까?

편집 : 내가 QuickCheck 2 것을 도입하는 것이 -10000 10000

Answer 1

한 가지 사이의 정수를 포함, 0 ~ 100의 목록 크기 내 솔루션을 테스트 할 것, 구체적으로는 비효율의 출처가 될 수있는 것은 shrink 함수입니다. 속성이 실패하면 작은 값으로 후보를 제공하는 shrink 함수가 호출되며 속성이 실패한 값보다 작은 값 을 줄 수 없을 때까지 축소됩니다. 그러나이 경우에만 속성은 속성이 실패 할 때 발생합니다.

목록의 임의 인스턴스에 대한 변경 사항은 version 1 과 version 2 사이에 많이 변경되지 않았습니다. 차이점은 버전 1은 vector을 사용하고 버전 2는 을 목록 내 용으로 사용하지만 vector은 정확히 임의의 순차 호출 과 같은 목록 이해로 구현됩니다.

두 구현은 모두 size 매개 변수를 사용했습니다. 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 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 개 요소보다는 목록을 더 이상하지 않습니다 :이 newtype 방법을 사용하여 구현 한 예이다. 요소는 size 매개 변수를 사용하지 않으므로 항상 범위에 있고 [-10000,10000] 범위이므로 개선 할 여지가 있습니다. shrink 함수는 목록에 사용 가능한 shrink을 사용하고 Int을 사용하기 만합니다.

그냥 SmallIntList 로 인수를 사용하여 속성이 인스턴스를 사용하려면

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