📻 👩🏽‍🚀 🎭 एल्गोरिदम के अनुभवजन्य विश्लेषण के लिए कुछ सुझाव 👩 🙎🏼 👵🏽

प्रविष्टि

पिछले साल नवंबर में, एक मैगनस लाइ हेटलैंड पुस्तक दिखाई दी, जिसका शीर्षक "पायथन एल्गोरिदम: मैथेरिंग बेसिक अल्गोरिद्म इन द पायथन लैंग्वेज।" लेखक कई वर्षों से प्रोग्रामिंग में लगा हुआ है और अब नॉर्वेजियन विश्वविद्यालयों में से एक पर एल्गोरिदम के सिद्धांत में एक पाठ्यक्रम पढ़ाता है। अपनी पुस्तक में, वह एल्गोरिदम के निर्माण और विश्लेषण के तरीकों के बजाय सरल शब्दों के साथ समझाता है, और वह पायथन प्रोग्रामर के उद्देश्य से कई उदाहरण भी बताता है। लेखक विभिन्न एल्गोरिथम समस्याओं के समाधान के निर्माण और अनुकूलन के लिए एक व्यावहारिक दृष्टिकोण पर केंद्रित है। समीक्षाओं में से एक का कहना है कि इस पुस्तक की तुलना कॉर्मेन के क्लासिक काम के साथ की जा सकती है।

तन्नन और मैं इस पुस्तक का अनुवाद बहुत कम कर रहे हैं, और मैं आपके ध्यान में अध्याय के पहले भाग का अनुवाद करता हूँ, एम्पोरिअल इवैलुएशन ऑफ़ अल्गोरिद्म।

एल्गोरिदम का अनुभवजन्य मूल्यांकन

यह पुस्तक एल्गोरिदम के डिजाइन (और एल्गोरिदम का बारीकी से संबंधित विश्लेषण) का वर्णन करती है। लेकिन विकास में एक और महत्वपूर्ण प्रक्रिया है जो बड़ी वास्तविक जीवन परियोजनाओं को बनाते समय महत्वपूर्ण है; यह एल्गोरिदम का अनुकूलन है। इस पृथक्करण के दृष्टिकोण से, एल्गोरिथ्म के डिजाइन को एल्गोरिथम की कम स्पर्शोन्मुख जटिलता (एक प्रभावी एल्गोरिथम विकसित करके) प्राप्त करने का एक तरीका माना जा सकता है, और इस विषमता में छिपी स्थिरांक की कमी के रूप में अनुकूलन।

हालांकि मैं आपको पायथन डिजाइन एल्गोरिदम पर कुछ सुझाव दे सकता हूं, यह अनुमान लगाना कठिन है कि आप किस चाल और चाल के साथ काम कर रहे हैं या पायथन के अपने उपकरण और संस्करण के लिए आपको सबसे अच्छा प्रदर्शन देंगे। (एसिम्पोटिक्स का उपयोग सिर्फ इसलिए किया जाता है ताकि ऐसी चीजों का सहारा लेने की आवश्यकता न हो)। सामान्य तौर पर, कुछ मामलों में, चाल की आवश्यकता नहीं हो सकती है, क्योंकि आपका कार्यक्रम पहले से ही काफी तेज है। ज्यादातर मामलों में आप जो सबसे आसान काम कर सकते हैं, वह है बस कोशिश करना और देखना। यदि आपके पास कुछ हैक का विचार है, तो बस इसे आज़माएं! अपनी चाल को लागू करें और कुछ परीक्षण चलाएं। क्या कोई सुधार हैं? और अगर यह परिवर्तन आपके कोड को कम पठनीय बनाता है, और प्रदर्शन लाभ छोटा है, तो सोचें - क्या यह इसके लायक है?

यद्यपि तथाकथित प्रयोगात्मक एल्गोरिदम के सैद्धांतिक पहलू (अर्थात, एल्गोरिदम के प्रयोगात्मक मूल्यांकन और उनके कार्यान्वयन) इस पुस्तक के दायरे से परे हैं, मैं आपको कुछ व्यावहारिक सुझाव दूंगा जो बहुत उपयोगी हो सकते हैं।

टिप 1. यदि संभव हो, तो इसके बारे में चिंता न करें।

असममित जटिलता के बारे में चिंता करना बहुत मददगार हो सकता है। कभी-कभी व्यवहार में जटिलता के कारण किसी समस्या का हल इस तरह हो सकता है। हालांकि, एसिम्प्टोटिक्स में लगातार स्थिरांक अक्सर महत्वपूर्ण नहीं होते हैं। आरंभ करने के लिए एल्गोरिथ्म के एक सरल कार्यान्वयन का प्रयास करें, और सुनिश्चित करें कि यह स्थिर रूप से काम करता है। यदि यह काम करता है, तो इसे स्पर्श न करें।

टिप 2. रनटाइम को मापने के लिए समय का उपयोग करें।

टाइमटाइम मॉड्यूल को रनटाइम को मापने के लिए डिज़ाइन किया गया है। यद्यपि आपको वास्तव में विश्वसनीय डेटा प्राप्त करने के लिए बहुत काम करने की आवश्यकता है, व्यावहारिक उद्देश्यों के लिए, टाइमटाइम करेगा। उदाहरण के लिए:

>>> import timeit >>> timeit.timeit("x = 2 + 2") 0.034976959228515625 >>> timeit.timeit("x = sum(range(10))") 0.92387008666992188

टाइमलाइन मॉड्यूल का उपयोग सीधे कमांड लाइन से किया जा सकता है, उदाहरण के लिए:

 $ python -m timeit -s"import mymodule as m" "m.myfunction()"

समय का उपयोग करते समय आपको कुछ सावधान रहना चाहिए: साइड इफेक्ट्स जो कि टाइमिट के पुन: क्रियान्वयन को प्रभावित करेंगे। टाइमटाइम फ़ंक्शन सटीकता बढ़ाने के लिए आपके कोड को कई बार चलाएगा, और यदि अतीत बाद वाले को प्रभावित करना शुरू कर देता है, तो आप एक कठिन स्थिति में होंगे। उदाहरण के लिए, यदि आप mylist.sort () जैसी किसी चीज़ के निष्पादन की गति को मापते हैं, तो सूची केवल पहली बार क्रमबद्ध होगी। शेष हजारों लॉन्च के दौरान, सूची पहले से ही क्रमबद्ध हो जाएगी और यह एक अनुचित रूप से छोटे परिणाम देगा।

इस मॉड्यूल के बारे में अधिक जानकारी और यह कैसे काम करता है यह पायथन मानक पुस्तकालय प्रलेखन में पाया जा सकता है।

टिप 3. अड़चन का पता लगाने के लिए प्रोफाइलर का उपयोग करें।

अक्सर, यह समझने के लिए कि कार्यक्रम के किन हिस्सों में अनुकूलन की आवश्यकता होती है, विभिन्न अनुमान और धारणाएं बनाई जाती हैं। इस तरह की धारणाएं अक्सर गलत होती हैं। अनुमान लगाने के बजाय, प्रोफाइलर का उपयोग करें। पायथन मानक के रूप में कई प्रोफाइल के साथ आता है, लेकिन cProfile की सिफारिश की जाती है। समयसीमा का उपयोग करना जितना आसान है, लेकिन यह प्रोग्राम को चलाते समय किस समय बर्बाद होता है, इस बारे में अधिक विस्तृत जानकारी देता है। यदि आपके प्रोग्राम का मुख्य कार्य मुख्य कहा जाता है, तो आप प्रोफाइलर का उपयोग इस प्रकार कर सकते हैं:

 import cProfile cProfile.run('main()')

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

युक्ति 4. रेखांकन के अनुसार परिणाम दिखाएं।

विज़ुअलाइज़ेशन यह समझने का एक शानदार तरीका हो सकता है कि क्या है। प्रदर्शन अध्ययन के लिए, अक्सर चार्ट का उपयोग किया जाता है (उदाहरण के लिए, डेटा मात्रा और निष्पादन समय के बीच संबंध का आकलन करने के लिए) और बॉक्स-और-मूंछें चार्ट जो कई लॉन्चों पर बिताए समय के वितरण को दर्शाते हैं। उदाहरण आकृति में देखे जा सकते हैं।

पायथन से रेखांकन और आरेख के निर्माण के लिए एक उत्कृष्ट पुस्तकालय matplotlib है (आप इसे http://matplotlib.sf.net पर प्राप्त कर सकते हैं)।

टिप 5. रनटाइम तुलना के आधार पर निष्कर्ष के बारे में सावधान रहें।

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

यदि आप दो से अधिक कार्यान्वयन की तुलना करते हैं तो समस्या और अधिक जटिल हो जाती है। तुलना किए गए संस्करणों की संख्या के वर्ग के अनुपात में तुलना के लिए जोड़े की संख्या बढ़ जाती है, बहुत संभावना बढ़ जाती है कि कम से कम दो संस्करण थोड़ा अलग दिखाई देंगे। (इसे एकाधिक तुलनात्मक समस्या कहा जाता है)। इस समस्या के सांख्यिकीय समाधान हैं, लेकिन सबसे आसान तरीका दो संदिग्ध संस्करणों के साथ प्रयोग को दोहराना है। आपको कई बार ऐसा करने की आवश्यकता हो सकती है। क्या वे अब भी एक जैसे दिखते हैं?

दूसरे, कई बिंदु हैं जिन्हें औसत मूल्यों की तुलना करते समय आपको ध्यान देने की आवश्यकता है। कम से कम, आपको वास्तविक समय के औसत की तुलना करनी चाहिए। आमतौर पर, प्रदर्शन को मापने के दौरान घातीय संख्या प्राप्त करने के लिए, प्रत्येक प्रोग्राम के रनटाइम को कुछ मानक, सरल एल्गोरिथ्म के निष्पादन समय से विभाजित करके सामान्य किया जाता है। वास्तव में, यह उपयोगी हो सकता है, लेकिन कुछ मामलों में माप परिणामों को अर्थहीन बना देगा। इस विषय पर कुछ उपयोगी सुझाव फ्लेमिंग और वालेस में पाए जा सकते हैं, "आंकड़ों के साथ झूठ नहीं कैसे: बेंचमार्क परिणामों को संक्षेप में प्रस्तुत करने का सही तरीका।" आप बैस्ट और वेबर के "औसत की तुलना न करें," या सिट्रोन एट अल के एक नए लेख को भी पढ़ सकते हैं। " हार्मोनिक या ज्यामितीय माध्य: क्या यह वास्तव में मायने रखता है? "

और तीसरा, शायद आपके निष्कर्ष को सामान्यीकृत नहीं किया जा सकता है। इनपुट डेटा के एक अलग सेट पर और अलग हार्डवेयर पर समान माप अलग-अलग परिणाम दे सकते हैं। यदि कोई आपके माप के परिणामों का उपयोग करेगा, तो आपको लगातार दस्तावेज़ प्राप्त करना होगा कि आपने उन्हें कैसे प्राप्त किया।

टिप 6. प्रयोगों के स्पर्शोन्मुख व्यवहार के बारे में निष्कर्ष निकालते समय सावधान रहें।

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

मान लीजिए कि आप मानते हैं कि एल्गोरिथ्म द्विघात जटिलता के साथ काम करता है, लेकिन आप निर्णायक रूप से इसे साबित नहीं कर सकते। क्या आप अपनी धारणा को साबित करने के लिए प्रयोगों का उपयोग कर सकते हैं? जैसा कि पहले ही उल्लेख किया गया है, प्रयोग (और एल्गोरिदम का अनुकूलन) मुख्य रूप से निरंतर गुणांक के साथ सौदा करते हैं, लेकिन एक समाधान है। मुख्य समस्या यह है कि आपकी परिकल्पना वास्तव में प्रयोगात्मक रूप से अपरिवर्तनीय है। यदि आप दावा करते हैं कि एल्गोरिथ्म में जटिलता ओ (n,) है, तो डेटा न तो पुष्टि कर सकता है और न ही इससे इनकार कर सकता है। हालांकि, यदि आप अपनी परिकल्पना को अधिक विशिष्ट बनाते हैं, तो यह परीक्षण योग्य हो जाएगा। उदाहरण के लिए, आप कुछ आंकड़ों के आधार पर यह मान सकते हैं कि कार्यक्रम का समय आपके वातावरण में कभी भी 0.24n² + 0.1n + 0.03 सेकंड से अधिक नहीं होगा। यह एक परीक्षण योग्य (अधिक सटीक, प्रतिवर्तनीय) परिकल्पना है। यदि आपने कई माप किए हैं, लेकिन फिर भी काउंटर-उदाहरण नहीं मिल सकते हैं, तो आपकी परिकल्पना सच हो सकती है। और यह पहले से ही एल्गोरिथ्म के द्विघात जटिलता की परिकल्पना की पुष्टि करता है।

निष्कर्ष

उदाहरण के लिए, अमेज़न पर ही पुस्तक का ऑर्डर दिया जा सकता है।

अनुवाद कतार में अगले अक्षर ग्राफ और पेड़ों के साथ शुरू करने और काम करने पर अध्याय हैं। लेखक पायथन का उपयोग करके इन डेटा संरचनाओं के साथ प्रभावी ढंग से काम करने के व्यावहारिक पहलुओं का वर्णन करता है।

एल्गोरिदम के अनुभवजन्य विश्लेषण के लिए कुछ सुझाव