एल्गोरिथम जटिलता के लिए एक स्वचालित परीक्षण कैसे लिखें?

प्रारंभ में, कार्य व्यावहारिक विचारों से अधिक शैक्षिक हित से बाहर हुआ। जब मुझे मॉक ऑब्जेक्ट्स के बारे में पता चला, तो मुझे आश्चर्य हुआ कि क्या ऐसी कोई स्थिति है जिसके लिए आप एक मॉक ऑब्जेक्ट का उपयोग करके टेस्ट लिख सकते हैं, लेकिन राज्य परीक्षणों के साथ नहीं। वस्तुतः पहला विचार जो मन में आया वह एल्गोरिदम की कम्प्यूटेशनल जटिलता के बारे में था। क्या एक स्वचालित परीक्षण को यह सत्यापित करना संभव है कि एक विशिष्ट स्थिति में एक निश्चित जटिलता के एल्गोरिथ्म का उपयोग किया जाता है?



समाधान का विचार बहुत सरल है: मान लीजिए कि कुछ एल्गोरिथ्म इनपुट डेटा सेट को संसाधित करता है। फिर इसकी एल्गोरिथम जटिलता इस सेट पर किए गए संचालन की संख्या और संरचना से निर्धारित होती है। यदि आप मॉक ऑब्जेक्ट को इनपुट में सबमिट करते हैं, जो आपके तरीके की प्रत्येक कॉल को गिना जाएगा, तो एल्गोरिथ्म पूरा होने के बाद, हम उस सटीक संख्या और प्रकार की गणना करने में सक्षम होंगे जो इसके संचालन के लिए आवश्यक थे। यह केवल मुखर बयान दर्ज करने के लिए बनी हुई है।

सीमा: इस विधि के लिए, स्थैतिक या गतिशील बहुरूपता का उपयोग करना आवश्यक है ताकि मॉक-ऑब्जेक्ट के लिए प्रतिस्थापन किया जा सके।

आइए प्रदर्शित करें कि यह C ++ के उदाहरण के साथ कैसे काम करता है।

मॉक ऑब्जेक्ट के साथ शुरू करते हैं। सी ++ में डेटा संरचनाओं के साथ काम करते समय, यह आवश्यक है कि तुलना संचालन <और ==, साथ ही असाइनमेंट ऑपरेटर और कॉपी ऑपरेटर को ऑब्जेक्ट के लिए परिभाषित किया जाए। पहले दो ऑपरेशन ऑब्जेक्ट को पढ़ रहे हैं, और अंतिम दो लिख रहे हैं। हम एक ऐसा वर्ग लिखेंगे जो पढ़ने और लिखने के कार्यों को अलग-अलग करेगा।

class Mock { public: Mock(): someValue(0){} Mock(int value): someValue(value) {} Mock(Mock const& other) { ++Mock::writeCounter; //    ++Mock::readCounter; //    this->someValue = other.someValue; } Mock& operator=(Mock const& other) { ++Mock::writeCounter; //    ++Mock::readCounter; //    this->someValue = other.someValue; return *this; } static int HasBeenRead() { return readCounter; } static int HasBeenWritten() { return writeCounter; } static void Clear() { readCounter = 0; writeCounter = 0; } private: int someValue; static int readCounter; //   static int writeCounter; //   friend bool operator==(Mock const& m1, Mock const & m2); friend bool operator<(Mock const& m1, Mock const & m2); }; int Mock::readCounter = 0; int Mock::writeCounter = 0; bool operator==(Mock const& m1, Mock const & m2) { Mock::readCounter += 2; //    return m1.someValue == m2.someValue; } bool operator<(Mock const& m1, Mock const & m2) { Mock::readCounter +=2; //    return m1.someValue < m2.someValue; } 

आइए C ++ STL लाइब्रेरी के एल्गोरिदम और डेटा संरचनाओं पर हमारे विचार, हमारे विचार का परीक्षण करें।

सूची में शर्त की जटिलता हे (कांस्ट) है।

 list<Mock> list; for(int i = 999; i >= 0; --i) list.insert(list.begin(), Mock(i)); cout << "Insert to list: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

कंसोल आउटपुट:

 Insert to list: read 1000 write 1000 

सबसे खराब स्थिति में, एक रैखिक सरणी में खोज जटिलता O (n) है।

 find(list.begin(), list.end(), Mock(999)); cout << "Find in list: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

कंसोल आउटपुट:

 Find in list: read 3000 write 1000 

एक संतुलित बाइनरी ट्री में n तत्वों को सम्मिलित करने से O (n * log_2 (n)) ऑर्डर की जटिलता होती है। मुझे नहीं पता कि इसके लिए C ++ मानक में कोई आवश्यकता है या नहीं, लेकिन Microsoft STL लाइब्रेरी में, बाइनरी संतुलित पेड़ के आधार पर नक्शा लागू किया जाता है।
आइए गिनती:

 map<Mock,int> map; for(int i = 0; i < 1024; ++i) map[Mock(i)] = i; cout << "Insert to map 1024 items: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

कंसोल आउटपुट:

 Insert to map 1024 items: read 65704 write 2048 

इस निष्कर्ष से क्या कहा जा सकता है: सबसे पहले, प्रत्येक वस्तु पर दो लिखने के संचालन होते हैं! यह राज्य पृथक्करण के बिना बड़ी वस्तुओं के लिए महंगा हो सकता है। दूसरे, निश्चित रूप से, प्रति ऑब्जेक्ट लगभग 60 रीड ऑपरेशंस काफी अनुमानित हैं - log_2 (1024) = 10, लेकिन आप पैमाने को महसूस करना शुरू करते हैं और समझते हैं कि हैश टेबल अच्छे क्यों हैं।

क्या यह व्यवहार में उपयोगी हो सकता है?

ईमानदारी से, मेरे अभ्यास में केवल तीन मामले थे जब यह वास्तव में काम में आया था, और फिर, उनमें से दो को ही परीक्षण के लिए समस्या का पता लगाने की अधिक आवश्यकता थी।

1. लगभग आठ साल पहले, मुझे क्यूटी 4.0 पर एक एप्लिकेशन को डिबग करना था। समस्या यह थी: जब आप एक निश्चित प्रपत्र खोलते हैं, तो संपूर्ण अनुप्रयोग बहुत धीमा होने लगा। जैसे ही आप फॉर्म को बंद करते हैं, एप्लिकेशन ठीक काम करता है। लेख में वर्णित तकनीक ने मुझे यह पता लगाने की अनुमति दी कि क्यूटी 4.0 में सभी नियंत्रण जो प्राप्त कर सकते हैं और घटनाओं को संसाधित कर सकते हैं वे एक रैखिक सूची में हैं। जब कोई घटना होती है, तो वह पूरी सूची से गुजरती है। बेशक, यदि कुछ नियंत्रण यह निर्णय लेते हैं कि इसने संदेश को संसाधित कर दिया है, तो संदेश श्रृंखला के साथ आगे स्थानांतरित नहीं होता है। लेकिन, यदि कोई ऐसा व्यक्ति नहीं है जो संदेश को संसाधित करना चाहता है, तो यह पूरी श्रृंखला से गुजरता है। उदाहरण के लिए, एक अनुप्रयोग पर माउस कर्सर की घटना। तो, जिस रूप में ब्रेक का नेतृत्व किया गया, उसमें 400 से अधिक नियंत्रण शामिल थे! बाह्य रूप से, प्रपत्र 20 स्तंभों और 20 पंक्तियों की तालिका जैसा था, लेकिन यह केवल बाह्य रूप से है! अलग-अलग नियंत्रणों का उपयोग करके तालिका का अनुकरण किया गया था।
2. लगभग 5 साल पहले, एक नए ग्राहक ने हमें उसी शिकायत के बारे में बताया, लेकिन यह एप्लिकेशन C # के तहत पहले से ही DevExpress लाइब्रेरी में था। दुर्भाग्य से, मैं विवरणों को भूल गया - लेकिन समस्या यह थी कि पुस्तकालय के अंदर एक घटक था जिसमें ओ (एन ^ 4) के बजाय ओ (एन ^ 4) के आदेश की जटिलता थी।
3. वर्तमान में हम जिन परियोजनाओं पर काम कर रहे हैं, उनमें से एक का सर्वर हिस्सा अभिनेताओं के मॉडल पर बनाया गया है। प्रणाली काफी जटिल हो गई है, इसलिए, आने वाले संदेशों को संसाधित करने की प्रभावशीलता को नियंत्रित करने के लिए, परीक्षणों का उपयोग किया जाता है जो मूल संदेश को एक विशेष के साथ प्रतिस्थापित करते हैं जो संदेश क्षेत्रों तक पहुंच को गिनता है।