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

साथियों, शुभ संध्या! आपने हमारे द्वारा " C ++ 17 STL। Standard Template Library " पुस्तक के पहले संस्करण को इतनी आसानी से अलग कर लिया और आप दूसरे का विश्लेषण करना जारी रखते हैं, कि हमने आखिरकार यहां वैकल्पिक दृष्टिकोण प्रस्तुत करने का फैसला किया। आज के लेख के लेखक इवान ćukić हैं, जो C ++ में पुस्तक कार्यात्मक प्रोग्रामिंग के मालिक हैं, जिसे मैनिंग पब्लिशिंग हाउस में रिलीज़ के लिए तैयार किया जा रहा है। हम उनके संशयवादी विचारों, कोड और गणनाओं का मूल्यांकन करने की पेशकश करते हैं

प्रस्तावना

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

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

एल्गोरिदम

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

बेशक, यह बिल्कुल सच है कि अगर हम जिस समस्या का सामना कर रहे हैं, उसे हल करने के for एक लूप के लिए लिखने के लिए तैयार हैं, तो हमें सबसे पहले यह सोचने की जरूरत है कि क्या मानक पुस्तकालय के मौजूदा एल्गोरिदम (या बढ़ावा) इसके लिए उपयुक्त हैं, और आँख बंद करके काम नहीं करते।

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

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

एक समस्या उत्पन्न हो सकती है अगर हमें एल्गोरिथ्म को लागू करने से पहले किसी तरह से डेटा तैयार करने की आवश्यकता है।

सेट का अंतर

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

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

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

नतीजतन, हमारे पास दो सेट हैं: एक में आसपास के दृश्य क्षेत्रों से चर होंगे, और दूसरे में लैम्ब्डा अभिव्यक्ति के शरीर में उपयोग किए जाने वाले चर होंगे।

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

और, अगर हमें प्रतिच्छेदन की आवश्यकता है, तो हम std::set_intersection उपयोग कर सकते हैं।

यह एल्गोरिथ्म अपनी सादगी में बहुत सुंदर है। यह दो क्रमबद्ध संग्रहों को स्वीकार करता है और साथ ही साथ उन्हें शुरू से अंत तक चलाता है:

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

प्रत्येक पुनरावृत्ति में, कम से कम एक तत्व (पहले या दूसरे इनपुट संग्रह से) को छोड़ दिया जाता है - इसलिए, एल्गोरिथ्म की जटिलता रैखिक होगी - O(m + n) , जहाँ m पहले संग्रह में तत्वों की संख्या है और n दूसरे संग्रह में तत्वों की संख्या है ।

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

छंटाई

यहाँ समस्या है: क्या होगा अगर संग्रह पूर्व-छाँटे नहीं गए हैं?

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

इस प्रकार, चर नाम से सॉर्ट नहीं किए जाएंगे, और हम सीधे उनके लिए संचालन के लिए std::set_intersection उपयोग नहीं कर पाएंगे। इसी तरह, यदि आप लैम्ब्डा अभिव्यक्ति के शरीर में चर को ट्रैक करते हैं, तो हम सबसे अधिक संभावना है कि उन्हें क्रमबद्ध रूप से नहीं बचा पाएंगे।

चूंकि 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) ।

छोटे क्रमबद्ध करें

क्या बिना छांटना संभव है?

यदि दोनों संग्रह क्रमबद्ध नहीं हैं, तो हमें पहले से प्रत्येक तत्व के लिए दूसरे संग्रह के चारों ओर जाना होगा - यह तय करने के लिए कि क्या इसे परिणाम सेट में शामिल किया जाए। यद्यपि यह दृष्टिकोण वास्तविक परियोजनाओं में काफी आम है, यह पिछले एक से भी बदतर है - इसकी जटिलता O(n * m) ।

एक पंक्ति में सब कुछ छाँटने के बजाय, या कुछ भी नहीं छाँटने के बजाय, ज़ेन को याद रखें और तीसरा पथ चुनें - हम केवल एक संग्रह को सॉर्ट करते हैं।

यदि केवल एक संग्रह को सॉर्ट किया जाता है, तो हम एक-एक करके अनसोल्ड से सभी मानों पर पुनरावृति कर सकते हैं और प्रत्येक मान की जांच कर सकते हैं कि यह सॉर्ट किए गए संग्रह में है या नहीं। ऐसा करने के लिए, एक द्विआधारी खोज लागू करें।

इस मामले में, पहली बार छँटाई के लिए समय की जटिलता O(n log n) और छँटाई और जाँच के लिए O (m log n) । कुल जटिलता O((n + m) log n) ।

यदि हमने दूसरे संग्रह को क्रमबद्ध करने का निर्णय लिया, और पहला नहीं, तो जटिलता O((n + m) log m) ।

अधिकतम दक्षता प्राप्त करने के लिए, हम हमेशा उस संग्रह को सॉर्ट करते हैं जिसमें कम तत्व होते हैं, ताकि हमारे एल्गोरिथ्म की अंतिम जटिलता हो
((m + n) log (min(m, n)) ।

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

 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)); }); } 

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

हैशिंग

अंतिम विकल्प एक छोटे संग्रह से std::unordered_set (एक हैश-आधारित अनियंत्रित सेट कार्यान्वयन) का निर्माण करना है, बजाय इसे सॉर्ट करने के। इस स्थिति में, खोज कार्यों की जटिलता O(1) औसत होगी, लेकिन std::unordered_set का निर्माण करने में समय लगेगा std::unordered_set । भवन की जटिलता 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)); }); } 

हैशिंग दृष्टिकोण पूरी तरह से जीत जाता है जब आपको एक ही पूर्वनिर्धारित छोटे सेट के साथ कई सेटों के चौराहों की गणना करने की आवश्यकता होती है। यही है, हमारे पास सेट A , सेट B₁ , B₂… and है B₂… और हम A ∩ B₁, A ∩ B₂… गणना करना चाहते हैं A ∩ B₁, A ∩ B₂…

इस स्थिति में, आप std::unordered_set निर्माण की जटिलता को अनदेखा कर सकते हैं, और प्रत्येक चौराहे की गणना की जटिलता रैखिक होगी - O(m) , जहाँ m दूसरे संग्रह में तत्वों की संख्या है।

नियंत्रण

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

एक छोटे से संग्रह आउटपरफॉर्म std::unordered_set थोड़ा सा, लेकिन विशेष रूप से नहीं।

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