क्विक चेक

Question

में परीक्षण डेटा कैसे उत्पन्न होता है, इस पर नियंत्रण करते हुए मैंने हास्केल में सबसेट योग समस्या का हल ढूंढने के लिए एक एल्गोरिदम लिखा था। हस्ताक्षर

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

क्विक चेक परीक्षण करने के लिए एक अच्छा फिट प्रतीत होता है।

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

समस्या यह है कि एल्गोरिथ्म काफी कंप्यूटेशनल रूप से संवेदनशील और बड़ा इनपुट सूचियों के साथ 100 परीक्षण चल रहा है चलाने के लिए उम्र ले जाता है: उदाहरण के लिए मैं यहाँ गुण है कि मैं जांच कर सकता है में से एक है।

मैंने क्विक चेक 1 के साथ प्रयास किया और यह जल्दी से चला गया, लेकिन परीक्षण के लिए उपयोग किए गए डेटा सेट बहुत छोटे थे। क्विक चेक 2 पर जाने के बाद यह विपरीत समस्या प्रतीत होता है। क्यूसी के लिए a manual है लेकिन यह पुराना प्रतीत होता है (कोई तारीख जानकारी नहीं है) और मुझे नहीं पता कि क्यूसी 2 पर अभी भी कितना लागू होता है। A Tutorial हास्केल विकी पर उपलब्ध है लेकिन Arbitrary को तत्काल करने पर कुछ ही विवरण नहीं हैं।

• क्या QuickCheck 2 में परिवर्तन करने के लिए यह इतना QuickCheck की तुलना में धीमी हो जाते हैं:

  तो मैं दो प्रश्न हैं?

• किसी दिए गए परीक्षण के लिए उन्हें उपयोगी बनाने के लिए डेटा सेट निर्माण को नियंत्रित करने का सबसे अच्छा तरीका क्या है?

संपादित करें: अधिक विशिष्ट होना करने के लिए, मैं -10,000 और 10000

Answer 1

एक बात QuickCheck 2 पेश किया है कि उस के बीच पूर्णांकों युक्त, 0 से 100 के सूची के आकार के साथ अपने समाधान का परीक्षण करना चाहते हैं अक्षमता का स्रोत हो सकता है shrink फ़ंक्शन। यदि कोई संपत्ति विफल हो जाती है, तो संकीर्ण फ़ंक्शन को कॉल किया जाता है जो उम्मीदवारों को छोटे परीक्षण मूल्यों पर देता है, और वे तब तक संकुचित होते हैं जब तक वे छोटे मान नहीं दे सकते जिसके लिए संपत्ति विफल हो जाती है। लेकिन यह केवल होता है जब गुण विफल होते हैं।

सूचियों के लिए मनमाने ढंग से उदाहरण के लिए परिवर्तन ज्यादा version 1 और version 2 के बीच नहीं बदला है। अंतर शब्द में है, संस्करण 1 vector का उपयोग करता है, और संस्करण 2 एक सूची समझ का उपयोग करता है, लेकिन फिर vector को मनमाने ढंग से अनुक्रमित कॉल की बिल्कुल ऐसी सूची समझ के साथ कार्यान्वित किया जाता है।

दोनों कार्यान्वयन आकार पैरामीटर का उपयोग करते थे। क्विक चेक 1 में, का आकार डिफ़ॉल्ट div n 2 + 3 है, जहां n परीक्षण की संख्या है। क्विक चेक 2 अन्य दृष्टिकोण का उपयोग करता है, जहां अधिकतम आकार और परीक्षणों की संख्या कॉन्फ़िगर की गई है। परीक्षण आकार उस श्रेणी में वितरित किए जाएंगे, परीक्षणों की संख्या में रैखिक रूप से बढ़ रहे हैं (quickCheckWithResult में देखें)। इसका मतलब है, 100 परीक्षणों और अधिकतम आकार की डिफ़ॉल्ट सेटिंग के साथ, क्विक चेक 1 से अधिकतम आकार (div 100 2 + 3) = 53 होगा, और क्विक चेक 2 के साथ यह 100 होगा।निश्चित रूप से भारी हो लंबाई 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 दृष्टिकोण का उपयोग कर रहा है। तत्व आकार पैरामीटर का उपयोग नहीं करते हैं, इसलिए वे हमेशा श्रेणी [-10000,10000] पर हैं, इसलिए सुधार के लिए कुछ जगह है। shrink फ़ंक्शन आसानी से सूचियों के लिए उपलब्ध shrink एस और Int एस का उपयोग करता है।

अपनी संपत्ति के साथ इस उदाहरण का उपयोग करने के लिए, बस एक SmallIntList के रूप में एक तर्क का उपयोग करें:

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

आपके प्रश्नों