जब आपको एसटीएल से एल्गोरिदम का उपयोग करने की आवश्यकता नहीं है

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

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

एल्गोरिदम

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

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

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

सेट का अंतर

कल्पना करें कि हम C ++ प्रोग्रामर्स के लिए एक टूल लिखने की कोशिश कर रहे हैं, जो सभी लैंबडास को सभी डिफॉल्ट वैरिएबल्स ([=] और [और]] के कैप्चर के साथ कोड में पाएंगे और लैंबडास को कैप्चर किए गए वैरिएबल की विशिष्ट सूची के साथ परिवर्तित करने के लिए टिप्स प्रदर्शित करेंगे। कुछ इस तरह:

std::partition(begin(elements), end(elements), [=] (auto element) { //^~~ -     ,   [threshold] return element > threshold; }); 

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

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

• यदि पहले संग्रह में वर्तमान आइटम दूसरे में वर्तमान आइटम के समान है - इसे परिणाम में जोड़ें और इन संग्रह में अगले आइटम पर आगे बढ़ें
• यदि पहले संग्रह में वर्तमान आइटम दूसरे संग्रह में वर्तमान आइटम से कम है, तो पहले संग्रह में अगले आइटम पर जाएं
• यदि पहले संग्रह में वर्तमान आइटम दूसरे संग्रह में वर्तमान आइटम से बड़ा है, तो दूसरे संग्रह में अगले आइटम पर जाएं

एल्गोरिथ्म के प्रत्येक चरण के साथ, हम पहले, दूसरे या दोनों संग्रहों के साथ आगे बढ़ते हैं, जिसका अर्थ है कि इस एल्गोरिथ्म की जटिलता रैखिक होगी - O (m + n), जहां n और m संग्रह के आकार हैं।

सरल और प्रभावी। लेकिन यह केवल अब तक के इनपुट संग्रहों को क्रमबद्ध किया गया है।

छंटाई

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

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

इस मामले में छंटनी उनके दायरे के अनुसार चर को संग्रहीत करने के लिए स्टैक का उपयोग करने के पूरे विचार को मार देगी, लेकिन फिर भी यह संभव है:

 template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_1(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { std::sort(first1, last1); std::sort(first2, last2); return std::set_intersection(first1, last1, first2, last2, dest); } 

परिणामी एल्गोरिथ्म की जटिलता क्या है? O (n log n + m log m + n + m) की तरह कुछ क्वैसिलिनियर जटिलता है।

कम छँटाई

क्या हम छंटाई का उपयोग नहीं कर सकते हैं? हम कर सकते हैं, क्यों नहीं। हम पहले संग्रह से दूसरे, रैखिक खोज में प्रत्येक तत्व की खोज करेंगे। हमें जटिलता ओ (n * m) मिलती है। और मैंने वास्तविक परियोजनाओं में इस दृष्टिकोण को काफी बार देखा।

"सब कुछ सॉर्ट करें" और "कुछ भी सॉर्ट न करें" विकल्पों के बजाय, हम ज़ेन को खोजने और तीसरे तरीके से जाने की कोशिश कर सकते हैं - केवल एक संग्रह को सॉर्ट करें। यदि संग्रह में से एक को सॉर्ट किया जाता है, लेकिन दूसरा नहीं करता है, तो हम एक बार में अनसोल्ड संग्रह एक के तत्वों पर पुनरावृति कर सकते हैं और सॉर्ट किए गए बाइनरी खोज में खोज सकते हैं।

इस एल्गोरिथ्म की जटिलता पहले संग्रह को छांटने के लिए ओ (एन लॉग एन) और खोज और जाँच के लिए ओ (एम लॉग एन) होगी। कुल में, हम जटिलता ओ ((एन + एम) लॉग एन) प्राप्त करते हैं।

यदि हम किसी अन्य संग्रह को क्रमबद्ध करने का निर्णय लेते हैं, तो हमें जटिलता O ((n + m) log m) मिलती है। जैसा कि आप समझते हैं, अंतिम जटिलता ओ ((एम + एन) लॉग (मिनट (एम, एन)) प्राप्त करने के लिए यहां एक छोटे संग्रह को क्रमबद्ध करना तर्कसंगत होगा।

कार्यान्वयन इस तरह दिखेगा:

 template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_2(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_2(first2, last2, first1, last1, dest); return; } std::sort(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return std::binary_search(first1, last1, FWD(value)); }); } 

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

हैशिंग

और इस लेख में चर्चा किए गए अंतिम विकल्प को छांटने के बजाय एक छोटे संग्रह के लिए हैशिंग का उपयोग करना होगा। यह हमें इसमें O (1) की खोज करने का अवसर देगा, हालाँकि हैश का निर्माण, निश्चित रूप से, O (n) से O (n * n) में कुछ समय लगेगा, जो एक समस्या बन सकती है):

 template <typename InputIt1, typename InputIt2, typename OutputIt> void unordered_intersection_3(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_3(first2, last2, first1, last1, dest); return; } std::unordered_set<int> test_set(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return test_set.count(FWD(value)); }); } 

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

प्रदर्शन परीक्षण

अभ्यास के साथ सिद्धांत की पुष्टि करने के लिए हमेशा उपयोगी होता है (विशेषकर बाद के मामलों में, जब यह स्पष्ट नहीं है कि हैशिंग की प्रारंभिक लागत खोज प्रदर्शन में लाभ के साथ भुगतान करेगी)।

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