Kiểm soát cách dữ liệu thử nghiệm được tạo trong QuickCheck

Question

Tôi đã viết một thuật toán để tìm giải pháp cho vấn đề tổng hợp tập hợp con trong Haskell. Chữ ký là

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

QuickCheck có vẻ phù hợp để kiểm tra điều đó. Ví dụ tôi đây là một trong những tài sản mà tôi có thể kiểm tra:

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

Vấn đề là các thuật toán khá tính toán chuyên sâu và chạy 100 xét nghiệm với danh sách đầu vào lớn mất lứa tuổi để chạy.

Tôi đã thử với QuickCheck 1 và nó đã chạy nhanh, nhưng tập dữ liệu được sử dụng để thử nghiệm rất nhỏ. Sau khi chuyển sang QuickCheck 2, nó có vẻ là vấn đề ngược lại. Có a manual đối với QC nhưng có vẻ như cũ (không có thông tin ngày) và tôi không biết số tiền vẫn còn áp dụng cho QC2. A Tutorial có sẵn trên Wiki Haskell nhưng không có nhiều chi tiết, chỉ một vài từ trên instantiating Arbitrary.

Vì vậy, tôi có hai câu hỏi:

• gì thay đổi trong QuickCheck 2 làm cho nó trở nên chậm hơn nhiều so với QuickCheck?
• Cách tốt nhất để kiểm soát việc tạo tập dữ liệu để làm cho chúng hữu ích cho thử nghiệm nhất định là gì?

Edit: Để cụ thể hơn, tôi muốn thử nghiệm giải pháp của tôi với một kích thước danh sách 0-100, có chứa các số nguyên giữa -10.000 và 10000.

Answer 1

Một điều mà QuickCheck 2 giới thiệu mà có thể là nguồn của không hiệu quả là chức năng shrink. Nếu một thuộc tính thất bại, thì chức năng thu nhỏ được gọi là cung cấp cho các ứng cử viên trên các giá trị thử nghiệm nhỏ hơn và chúng được thu hẹp cho đến khi chúng không thể cung cấp giá trị nhỏ hơn cho thuộc tính bị thiếu. Nhưng điều này chỉ có xảy ra khi thuộc tính không thành công.

Thay đổi đối với trường hợp tùy ý cho danh sách không thay đổi nhiều giữa version 1 và version 2. Sự khác biệt trong từ ngữ, phiên bản 1 sử dụng vector và phiên bản 2 sử dụng một danh sách hiểu, nhưng sau đó vector được triển khai với chính xác danh sách như vậy của các cuộc gọi được sắp xếp theo tùy ý.

Cả hai triển khai đều sử dụng thông số kích thước. Trong QuickCheck 1, kích thước của giá trị được tạo là bởi mặc định div n 2 + 3, trong đó n là số của thử nghiệm. QuickCheck 2 sử dụng cách tiếp cận khác, trong đó kích thước tối đa và số lượng kiểm tra được định cấu hình. Kích thước thử nghiệm sẽ được phân phối trong phạm vi đó, tăng tuyến tính trong số lần kiểm tra (xem computeSize' trong quickCheckWithResult). Điều này có nghĩa là, với cài đặt mặc định là 100 thử nghiệm và kích thước tối đa, kích thước tối đa từ QuickCheck 1 sẽ là (div 100 2 + 3) = 53 và với QuickCheck 2 nó chỉ đơn giản là 100.

Khi tổng số phụ là NP-complete, bạn có thể có thuật toán số mũ;) Sau đó, sự khác biệt về thời gian chạy giữa danh sách dài 50 và 100 có thể là rất lớn. Có thể hiểu bạn muốn danh sách nhỏ để kiểm tra. Bạn có hai lựa chọn : tạo loại dữ liệu mới (tốt nhất là với newtype) hoặc tạo trình tạo độc lập và sử dụng forAll. Bằng cách sử dụng newtype, bạn có thể cũng chỉ định cách thu nhỏ các giá trị. Đây là một thực hiện ví dụ sử dụng phương pháp 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 dụ này không làm cho danh sách dài hơn 50 yếu tố. Các yếu tố không sử dụng thông số kích thước, vì vậy chúng luôn ở trong phạm vi [-10000,10000], do đó, có một số phòng để cải thiện. Chức năng shrink chỉ sử dụng các số shrink s có sẵn cho danh sách và Int s.

Để sử dụng trường hợp này với tài sản của bạn, chỉ cần sử dụng một SmallIntList như một cuộc tranh cãi:

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