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

अब आप उनके हाथों में DotNext 2018 Piter सम्मेलन की एक रिपोर्ट रख रहे हैं, जो आधुनिक अनुकूलन तकनीकों के बारे में बात करती है। .NET का इससे क्या लेना-देना है? यह एक ऐसे व्यक्ति की एक मौलिक रिपोर्ट है जो अपने पूरे जीवन का अनुकूलन कर रहा है। यदि प्रदर्शन आपके लिए महत्वपूर्ण है, तो आपको इसे देखने (या इस लेख को पढ़ने) की आवश्यकता है। बिल्ली के लिए आपका स्वागत है!

बेंचमार्किंग की कला

मैं आपके साथ बेंचमार्किंग से संबंधित कई विषयों पर चर्चा करना चाहूंगा। आरंभ करने के लिए, आइए कुछ बुनियादी बातों को दोहराएं। Amdahl का नियम कंप्यूटर विज्ञान के क्लासिक्स का हिस्सा है, यह मुख्य रूप से समानांतर कंप्यूटिंग में उपयोग किया जाता है, लेकिन किसी भी जटिल प्रणाली में काम करता है। यदि हम एक निश्चित प्रणाली के काम में सुधार करना चाहते हैं, तो हमें शुरू करने की आवश्यकता है जहां इस प्रणाली की मुख्य समस्याएं केंद्रित हैं। कानून स्वयं स्पष्ट है: यदि कोई घटक सिस्टम का 20% है, तो सिस्टम प्रदर्शन में अधिकतम सुधार जो केवल इस घटक के संचालन को अनुकूलित करके प्राप्त किया जा सकता है वह 20% है। बहुत बार मुझे लोगों से मिलना पड़ता है (निश्चित रूप से, हमारे पाठक उनसे संबंधित नहीं हैं) जो कमांड लाइन पार्सिंग को अनुकूलित करने जैसी चीजें करते हैं। ये ऑपरेशन आपके कार्यक्रम के पहले 10 माइक्रोसेकंड लेते हैं, और लोग अपनी एल्गोरिथ्म जटिलता का विश्लेषण करते हैं और अगर समय-समय पर चतुराई से डरते हैं।

जैसा कि आप शायद जानते हैं, अनुकूलन शुरू करने से पहले, आवेदन को प्रोफाइल करना और उसमें हॉट स्पॉट का चयन करना आवश्यक है। यहाँ यह लद्दा के कानून के बारे में कहा जाना चाहिए (यह वास्तविक उपनाम नहीं है, और अम्दल, पीछे की ओर पढ़ें)। आपको उस घटक पर अपने प्रयासों को केंद्रित करने की आवश्यकता है जो समय के सबसे बड़े निवेश की ओर ले जाता है। इसे आवेदन के बाहर ले जाना होगा, आवश्यक कार्य करना होगा, वापस लौटना होगा और फिर से परीक्षण करना होगा। आपको ऐसा करने की आवश्यकता का कारण यह है क्योंकि बहुत बार 20% प्रदर्शन सुधार दस 2% सुधार का परिणाम है। और एक बड़ी प्रणाली के ढांचे में, इस तरह के एक छोटे से सुधार को मापना असंभव है। इसके लिए, घटक का परीक्षण सूट में परीक्षण किया जाना चाहिए। सिस्टम के मुख्य घटकों में से एक के प्रदर्शन में 20% सुधार का अर्थ सिस्टम के लिए समग्र रूप से 5% सुधार हो सकता है, और कुछ क्षेत्रों के लिए यह एक उत्कृष्ट परिणाम है। यह मत भूलो कि अनुकूलन में कई वैश्विक प्रभाव हो सकते हैं, इसलिए चयनात्मक बेंचमार्किंग के परिणामों के आधार पर, आपको सिस्टम के संचालन के बारे में निष्कर्ष निकालने में बहुत सावधानी बरतनी चाहिए।

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

उदाहरण के लिए, सिस्टम को मूल स्थिति में पूरी तरह से वापस करने के लिए, फ़ाइलों के मामले में, उन्हें एक अलग डिस्क पर खोलने की आवश्यकता होती है, जो परीक्षण के अंत के बाद, हटाने की आवश्यकता होती है (जैसा कि मैं समझता हूं, यह विंडोज के तहत किया जा सकता है)। ऑपरेशन आसान नहीं है, लेकिन ज्यादातर मामलों में आवश्यक है।

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



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

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

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

एक अन्य सामान्य नियम यह है कि कंप्यूटर चीजों को उबाऊ होना पसंद करते हैं। क्या आपको दो वैक्टर, एक-एक बिलियन तत्वों द्वारा एक-दूसरे को गुणा करने की आवश्यकता है? यह कंप्यूटर के लिए एक आदर्श कार्य है, इस तरह के कार्यों के लिए इसमें सभी उपकरण विशेष रूप से तेज हैं। इस डेटा का विश्लेषण करने के लिए, एक नियमित अभिव्यक्ति बनाने के लिए उनके आधार पर - मैं ऐसा नहीं करना चाहता। कंप्यूटर, शाखाओं, निर्भरता, अप्रत्यक्ष कॉल जैसी चीजों को संक्षेप में पसंद नहीं करते हैं - उन्हें स्मार्ट कोड पसंद नहीं है, वे उबाऊ कोड पसंद करते हैं। कंप्यूटर अप्रत्यक्ष रिकॉर्डिंग को पसंद नहीं करते हैं - एक जटिल समस्या जो लोहे में शामिल लोग लंबे समय से संघर्ष कर रहे हैं और हल नहीं कर सकते हैं।

एक और नियम यह है कि आपको कम से कम शक्तिशाली संचालन को प्राथमिकता देनी चाहिए, दूसरे शब्दों में, गुणन के अतिरिक्त और गुणन के लिए गुणन को प्राथमिकता दें। फिर, गणित यहाँ उपयोगी है।

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

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

शाखाओं को अंकगणित से बदलें

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

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

static void min4(double[] p) { int n = p.Length; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < n / 4; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } } 

ऊपर मूल कोड है। वैसे, मैं गर्व से रिपोर्ट कर सकता हूं कि मैंने इन उदाहरणों का C # में अनुवाद किया, और वे सफलतापूर्वक संकलित हैं। कोड अपने आप में काफी सरल है: `m को सूचकांक में स्थित दो मानों में से सबसे छोटे का सूचकांक सौंपा गया है` i और `j, और फिर एक समान असाइनमेंट को दो और बार दोहराया जाता है, अन्य दो सूचकांकों पर निर्भर करता है। अंत में, अनुक्रमणिका `m पर मान को अनुक्रमणिका में मान के साथ सरणी में उलट दिया जाता है। जैसा कि आप देख सकते हैं, हम चार आगमनात्मक चर का उपयोग करके सरणी को बायपास करते हैं।

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

आइए उस कोड को बेहतर बनाने की कोशिश करें जो हमें अभी मिला है।

 static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < q; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } } 

पहले अनुकूलन के रूप में, हम संचालन की अत्यधिक पुनरावृत्ति से बचने की कोशिश करेंगे, इसके लिए हम लूप से कई डिवीजन ऑपरेशन निकालते हैं - `एन को 2 और 4 से विभाजित करना और 3 *` एन द्वारा विभाजित करना 4. लेकिन इस अनुकूलन के बाद, हमें पता चलता है कि गणना के लिए नहीं थे हमें मुख्य समस्या: कोड तेजी से नहीं बनेगा, हालांकि यह अधिक कॉम्पैक्ट होगा। सर्वोत्तम मामले में, हम एक आधा प्रतिशत सुधार प्राप्त करेंगे।

 static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = q, k = 2 * q, l = 3 * q; for (; i < q; ++i, ++j, ++k, ++l) { int m0 = p[i] <= p[j] ? i : j; int m1 = p[k] <= p[l] ? k : l; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } } 

दूसरा बदलाव जो हम कोड में करेंगे, वह निर्भरता कम करना है। एल्गोरिथ्म के पिछले संस्करण में, `m to` k या` l असाइन करना ऊपर दिए गए `m लाइन 'को दिए गए मान पर निर्भर करता है। `मी निर्भरता की संख्या को कम करने के लिए, हम अलग से` m0 और `m1 की गणना करते हैं, और फिर उनकी तुलना करते हैं। जब मैंने इस अनुकूलन का प्रदर्शन किया, तो मैं एल्गोरिथ्म की गति में एक महत्वपूर्ण सुधार की उम्मीद कर रहा था, लेकिन अंत में यह शून्य हो गया। लेकिन, मेरी राय में, निर्भरता की संख्या को न्यूनतम रखना महत्वपूर्ण है, यही कारण है कि मैंने कोड को बचा लिया।

 static void min4(double[] p) { int q = p.Length / 4; for (int i = 0; i < q; ++i) { int m0 = p[i] <= p[i + q] ? i : i + q; int m1 = p[i + 2 * q] <= p[i + 3 * q] ? i + 2 * q : i + 3 * q; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } } 

आइए अब हम चार से एक तक आगमनात्मक चर की संख्या को कम करने की कोशिश करते हैं, और हम शेष तीन अंकगणितीय रूप से गणना करेंगे, क्योंकि वे एक दूसरे के साथ निरंतर संबंध में हैं। यह काफी सरल है: `k के बजाय, हमारे पास अन्य दो चर -` i + 2 * q और `i + 3 * q के बजाय` i + q होगा। मुझे इस अनुकूलन के लिए भी उच्च उम्मीदें थीं, लेकिन, पिछले एक की तरह, इसने समय में कोई परिणाम नहीं दिया। यह फिर से माप के महत्व को साबित करता है: उनके बिना मैं दावा कर सकता था कि मैंने एल्गोरिथ्म के संचालन में काफी सुधार किया था, और मेरे पास बहुत महत्वपूर्ण तर्क होंगे।

 static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2: ++i) { int m0 = p[i - q] < p[i] ? i - q : i; int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q; Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } } 

चौथे प्रयास के रूप में, हम 3 से गुणा से छुटकारा पाने के लिए चक्र का पुनर्गठन करते हैं। यह हमें 3% का सुधार देगा। परिणाम अभी भी प्रभावशाली नहीं है। इसके बाद, टर्नरी ऑपरेटरों से छुटकारा पाने की कोशिश करें।

 // Returns: value if flag is true, 0 otherwise static int optional(bool flag, int value) { return -Convert.ToInt32(flag) & value; } 

ऐसा करने के लिए, मैं आपको एक नए फ़ंक्शन से परिचित कराना चाहता हूं - `स्थिर इंट वैकल्पिक (बूल फ्लैग, इंट वैल्यू)। यह इनपुट बूलियन मान को Int32 में परिवर्तित करता है, -1 से गुणा करता है और इसे दूसरे इनपुट मान के साथ बिटवाइज और ऑपरेटर के पास भेजता है। यदि इनपुट ध्वज गलत था, तो int32 में यह 0 होगा, और आउटपुट पर सभी रूपांतरणों के बाद भी हमें 0. मिलेगा। यदि इनपुट ध्वज सही था, तो int32 में यह 1 होगा, जब -1 से गुणा किया जाता है, तो हम FFFFFITF प्राप्त करते हैं, जो कि बिट के बाद "और" किसी भी संख्या के साथ यह दूसरा नंबर देगा। कृपया ध्यान दें कि यदि कहीं भी स्टेटमेंट नहीं है, तो कोड बिना ब्रांचिंग के है, यह कंप्यूटर के लिए उबाऊ है (हालांकि यह हमारे लिए जटिल लगता है)।

 static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2; ++i) { int m0 = i - optional(p[i - q] <= p[i], q); int m1 = i + q + optional(p[i + q2] < p[i + q], q); Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } } 

हम इस वैकल्पिक फ़ंक्शन के साथ टर्नरी ऑपरेटरों की जगह लेंगे, हम इसे गणना के अंदर एकीकृत करेंगे। हम इसे दो बार लागू करते हैं, और तीसरे मामले में, प्रश्न चिह्न छोड़ देते हैं। इस प्रकार, इस चक्र में चार जांचों के बजाय, मेरे पास केवल एक ही होगा।



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

 static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = 0; i < q; ++i) { int m = i + optional(p[i + q] < p[i], q); m += optional(p[i + q2] < p[m], q); m += optional(p[i + q2 + q] < p[m], q); Swap(ref p[i], ref p[m]); } } 

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

 // Returns: v1 if flag is true, v2 otherwise static int ifelse(bool flag, int v1, int v2) { return (-Convert.ToInt32(flag) & v1) | ((Convert.ToInt32(flag) - 1) & v2); } 

एक अन्य विशेषता जो मैं आपको बताना चाहूंगा, वह है I बिना शाखाओं वाली इफेल, जो अब आप स्क्रीन पर देखते हैं। सच है, मैं इसके साथ हमारे उदाहरण में प्रदर्शन में सुधार नहीं कर सका। यदि 0 को ध्वज के रूप में पारित किया जाता है, तो पहली पंक्ति 0 होगी; दूसरे में, हम इंट 1 में 0 से 1 घटाते हैं और एफएफएफएफएफएफएफ प्राप्त करते हैं, जिसके बाद यह मान बिटवाइज "एंड" के साथ-साथ फ़ंक्शन तर्क `v2 'में पारित हो जाता है, जो बदलाव के बिना हमें यह तर्क देगा; अंत में, पहली और दूसरी लाइनें बिटवाइज़ "OR" को पास कर दी जाती हैं, जो फिर से हमें `v2 'देगी। यदि ध्वज 1 है, तो पहली पंक्ति `v1 के बराबर होगी; दूसरे में, हम 1 को 1 से घटाते हैं और 0 प्राप्त करते हैं, जिसके परिणामस्वरूप पूरी रेखा 0 होगी, और बिटवाइज़ '0' में `0 'और` v1 देंगे।

मुझे उम्मीद है कि इस तरह के एक `ifelse बिना ब्रांचिंग फंक्शन वाले लोगों में दिलचस्पी होगी जो बैकएंड में शामिल हैं - फिलहाल, किसी कारण से आधुनिक कंपाइलर इस दृष्टिकोण का उपयोग नहीं करते हैं। इन कार्यों के साथ, आप एल्गोरिदम को पुनर्गठित कर सकते हैं ताकि संकलक उन्हें आपके लिए समझें, क्योंकि आप अपने संकलक की तुलना में अधिक चालाक और रचनात्मक हैं।

बड़ा सेट चौराहा

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

 int Intersect(double[] a1, double[] a2, double[] t) { if (a1.Length == 0 || a2.Length == 0) return 0; int i1 = 0, i2 = 0, i = 0; for (;;) if (a1[i1] < a2[i2]) { if (++i1 == a1.Length) break; } else if (a2[i2] < a1[i1]) { if (++i2 == a2.Length) break; } else { t[i++] = a1[i1]; if (++i1 == a1.Length || ++i2 == a2.Length) break: } return i; } 

इस एल्गोरिथ्म के मूल कार्यान्वयन पर एक नज़र डालें। यदि दोनों इनपुट सेट खाली हैं, तो, जाहिर है, हम 0. वापस आते हैं। हम एक अनंत लूप शुरू करते हैं, जिसमें, यदि कोई मैच होता है, तो हम 1 से परिणाम बढ़ाते हैं और जांचते हैं कि क्या चक्र पूरा होना चाहिए। एक अनंत लूप के बजाय, कोई भी कथन के लिए उपयोग कर सकता है और इसमें लूप को समाप्त करने के लिए शर्त निर्दिष्ट कर सकता है। लेकिन इसका मतलब होगा कि अतिरिक्त काम। कार्यान्वयन में जो आप स्लाइड पर देखते हैं, पहली शाखा में हमारे पास `if (a1 [i1] <a2 [i2]) है, जिसके बाद` 1 से `1 में वृद्धि होती है, और हम केवल` i1 की जाँच कर सकते हैं। इसी तरह, दूसरी शाखा में हमें केवल `i2 'की जाँच करनी है। दोनों मानों को केवल तीसरी शाखा में जांचना आवश्यक है। यदि यह जांच चक्र की शुरुआत में होती, तो हम अतिरिक्त काम करते।

आइए इस कार्यान्वयन को बेहतर बनाने का प्रयास करें। फिलहाल, इसकी एल्गोरिदम जटिलता दो इनपुट तर्कों के आधार पर रैखिक है। मशीन लर्निंग में, अक्सर एक सेट के अंतर को खोजना पड़ता है जो आकार या आंकड़ों में एक दूसरे से बहुत अलग होते हैं। उदाहरण के लिए, आपके पास एक लंबा इनपुट वेक्टर और एक छोटी विशेषता वेक्टर है, जिसके खिलाफ आप जाँच कर रहे हैं। हमारे कोड में, `a1 में एक लाख रिकॉर्ड और` a2 में एक हजार हो सकते हैं। इस मामले में, हम इस एल्गोरिथ्म को पूरा करने के लिए एक लाख चरणों से गुजरने के लिए तैयार नहीं हैं। यहां सबसे बड़ा भार कोड की निम्नलिखित पंक्ति पर होगा: `if (++ i1 == a1.length) ब्रेक। इससे पहले, एक तुलना होती है, और फिर इस पंक्ति में मूल्य का एक वृद्धि होती है; यह, संक्षेप में, एक रैखिक खोज है। हम एक लघु के तत्वों की तलाश में एक लंबे वेक्टर पर पुनरावृति करते हैं। सबसे खराब स्थिति में, हम ऐसी कई खोजों को अंजाम देंगे, जो धीरे-धीरे वेक्टर के साथ आगे बढ़ेंगी।

आइए इस एल्गोरिथम को बेहतर बनाने का प्रयास करें। ठीक है, अगर रैखिक खोज नहीं है, तो बाइनरी बेहतर है, है ना? बाइनरी का उपयोग करते हैं। इसका लाभ यह है कि यह छोटे तत्वों में से सबसे बड़ा सूचकांक देता है।

 int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, a1[i1]); if (m == a2.Length) continue; --m; if (!(a2[m] < a1[i1])) t[i++] = a1[i1]; } return i; } 

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

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

 int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i2 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, i2, a2.Length, a1[i1]); if (m == i2) continue; if (!(a2[m - 1] < a1[i1])) t[i++] = a1[i1]; i2 = m + 1; } return i; } 

यहाँ इस दृष्टिकोण का कार्यान्वयन है। आप देखते हैं कि हम `i2 'से शुरू होने वाले और' a2.length 'के साथ समाप्त होने वाले मूल सरणी के एक भाग के लिए हर बार एक बाइनरी खोज करते हैं। जैसे-जैसे प्रत्येक खोज के साथ `i2 बढ़ता जाएगा, खोज क्षेत्र कम होता जाएगा।

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

 int GBsearch(double[] a, int i, int j, double v) { for (int step = 1;; step *= 2) { if (i >= j) break; if (a[i] > v) break; if (i + step >= j) return Bsearch(a, i + 1, J, v); if (a[i + step] > v) return Bsearch(a, i + 1, i + step, v); i += step + 1; } return i; } 

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

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

आंद्रेई अलेक्जेंड्रेस्कु डोटनेक्स्ट 2018 मास्को में नहीं आएंगे, लेकिन जेफरी रिक्टर, ग्रेग यंग, ​​पावेल योसिफोविच और अन्य वहां होंगे। बोलने वालों के नाम और रिपोर्ट के विषय यहां और टिकट यहां मिल सकते हैं । अब सम्मिलित हों!