🚼 👨🏽‍🔬 🦈 लाइन कन्वेयर बेल्ट 🎅🏽 🚵🏽 🧝🏻

पांच साल पहले, मैंने एक प्रोग्राम डिजाइन किया था जो नियंत्रण टीमों के साथ पाठ को संसाधित करता है। प्रसंस्करण चरणों की संख्या बहुत महत्वपूर्ण थी - 6-7 प्रोसेसर खुद के माध्यम से बड़ी मात्रा में डेटा पारित कर सकते हैं, जैसा कि कभी-कभी यूनिक्स पाइपलाइनों में होता है। कार्य को सही ढंग से पूरा करने के लिए, मैंने एक सामान्य विधि विकसित की जो अन्य स्थानों में उपयोगी हो सकती है। इस लेख के पीछे का विचार वास्तव में यूनिक्स पाइपलाइनों के समान है, लेकिन कुछ महत्वपूर्ण अंतर हैं:

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

रैखिक डेटा से, मेरा मतलब उन वस्तुओं के अनुक्रम से होगा जो अगले (यदि कोई हो) को संक्रमण की अनुमति देता है। उदाहरण हैं: एक बाइनरी फ़ाइल, UTF-8 अक्षरों से पाठ, टोकन का एक क्रम, आदेश। एक जटिल कार्यक्रम जो एक अनुवादक के रूप में रैखिक डेटा को संसाधित करता है, आमतौर पर कई परिवर्तन करता है। यहाँ एक उदाहरण है:

किसी फाइल को बाइट्स द्वारा पढ़ना,
UTF-8 में डिकोडिंग,
पूर्वप्रक्रमक
शाब्दिक विश्लेषण
पार्स करने।

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

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

मेरे पास प्रकाशन के योग्य इन एल्गोरिदम का कार्यान्वयन नहीं है, इसलिए मैं खुद को सामान्य विचार और कार्यान्वयन योजना तक सीमित करूंगा। नमूना योजनाएं C ++ में दी गई हैं, वे वर्चुअल और मल्टीपल इनहेरिटेंस, साथ ही टेम्प्लेट का उपयोग करती हैं।

यदि आप विशेष रूप से परेशान किए बिना रैखिक डेटा के प्रसंस्करण को डिज़ाइन करते हैं तो क्या होता है

आइए कनवर्टर सॉफ़्टवेयर इंटरफ़ेस के संभावित कार्यान्वयन को देखें। सरलतम संस्करण में, तीन प्रकार के कन्वर्टर्स संभव हैं:

class Source { … public: T getData(); … }; class Sink { … public: void putData(T); … }; class Universal { … public: void process(); };

चित्रा 1. एक साधारण पाइपलाइन कार्यान्वयन की योजना।

यहाँ इस तरह के एक पाइपलाइन का एक तुच्छ उदाहरण है, "योजक" (यह एसटीडी से संख्या पढ़ता है: दालचीनी, उन्हें जोड़े में डालती है, एसटीडी को प्रिंट करता है: cout, यह एक काम कर रहे C ++ प्रोग्राम है):

 #include <iostream> //   std::cin class IntSource { public: int getData() { int next; std::cin>>next; return next; } bool good() const { return std::cin.good(); } }; //   std::cout class IntSink { public: void putData(int data) { std::cout<<data<<std::endl; } }; //    IntSource      IntSink class IntUniversal { IntSource source; IntSink sink; public: void process() { int i1 = source.getData(); int i2 = source.getData(); if( good() ) sink.putData(i1+i2); } bool good() const { return source.good(); } }; int main() { IntUniversal belt; while( belt.good() ) belt.process(); }

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

पाइप लाइन में पहला तत्व स्रोत है;
अंतिम तत्व सिंक है;
सिंक कनवर्टर सीधे केवल एक और सिंक कनवर्टर से पहले हो सकता है, स्रोत कनवर्टर सीधे केवल किसी अन्य स्रोत कनवर्टर का अनुसरण कर सकता है;
सार्वभौमिक कन्वर्टर को स्रोत और पूर्ववर्ती सिंक का पालन करना चाहिए।

इन नियमों से यह इस प्रकार है कि पाइपलाइन का एकमात्र संभावित कार्यान्वयन यह है: स्रोत ₁ , ..., स्रोत _n , यूनिवर्सल, सिंक ₁ , ..., सिंक _मी । इस तरह की पाइपलाइन के संचालन के दौरान कॉल स्टैक इस तरह दिख सकता है:

स्रोत _k :: getData
...
स्रोत _n :: getData
यूनिवर्सल :: प्रक्रिया,

या

सिंक _l :: putData
...
सिंक ₁ :: डालडाटा
यूनिवर्सल :: प्रक्रिया।

कन्वेयर में सुधार

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

 class UniversalBase { public: virtual void process()=0; }; template<class S> class UniversalSource; template<class T> class UniversalSink; //       template <class S> class UniversalSource : public virtual UniversalBase { UniversalSink<S>* next; protected: void putOnBelt(const S&); }; //       template <class T> class UniversalSink : public virtual UniversalBase { UniversalSource<T>* prev; protected: T getFromBelt(); }; // ,    T     S template <class T, class S> class Universal : public UniversalSink<T>, public UniversalSource<S> { };

चित्रा 2. बेहतर पाइपलाइन कार्यान्वयन की योजना।

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

यहां उसी योजक का एक उदाहरण है, लेकिन नई पाइपलाइन अवधारणा का उपयोग करके लागू किया गया है। अब यह पूर्ण विकसित कार्यक्रम नहीं है, इसमें पाइपलाइन प्रबंधक के कार्यान्वयन का अभाव है।

 #include <iostream> #inlcude <belt.h> //   std::cin class IntSource : public Belt::UniversalSource<int> { public: void process() { int data; if( std::cin>>data ) putOnBelt(data); } }; //   std::cout class IntSink : public Belt::UniversalSink<int> { public: void process() { if(!hasData() ) return; std::cout<<getFromBelt()<<std::endl; } }; //           class IntUniversal : public Belt::Universal<int,int> { public: void process() { int i1 = getFromBelt(); int i2 = getFromBelt(); if(!good() ) return; putOnBelt(i1+i2); } }; int main() { IntSource source; IntUniversal universal; IntSink sink; (source >> universal >> sink).process(); }

फ़ंक्शंस और कक्षाएं यहाँ उपयोग की जाती हैं जिनका पहले उल्लेख नहीं किया गया था:

 bool UniversalSink::hasData(void); bool UniversalSink::good(void); template<class T,class S> class UnboundedBelt : public Universal<T,S> {...}; template<class T> class RightBoundedBelt : public UniversalSink<T> {...}; template<class S> LeftBoundedBelt : public UniversalSource<S> {...}; class Belt : public UniversalBase {...}; template<class T, class R, class S> UnboundedBelt<T,S> operator >> (Universal<T,R>&,Universal<R,S>&); template<class R, class S> LeftBoundedBelt<S> operator >> (UniversalSource<R>&,Universal<R,S>&); template<class T, class R> RightBoundedBelt<T> operator >> (Universal<T,R>&,UniversalSink<R>&); template<class R> Belt operator >> (UniversalSource<R>&,UniversalSink<R>&);

डेटा के अंत को निर्धारित करने की समस्या को निम्नानुसार हल किया जा सकता है: वर्चुअल फ़ंक्शन बूल UniversalSource :: hasData () को परिभाषित किया गया है, जिसका क्रियान्वयन डिफ़ॉल्ट रूप से नियम पर आधारित है - हम मानते हैं कि डेटा समाप्त हो गया अगर प्रक्रिया एक पुनरावृत्ति के रूप में कुछ भी पारित नहीं हुई।

पाइपलाइन प्रबंधक कार्यान्वयन दृष्टिकोण

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

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

इस प्रकार, सरल मामले में कॉल स्टैक फॉर्म लेता है:

...
कन्वेयर प्रबंधक
UniversalSink :: getFromBelt ()
कन्वर्टर _{n ₂} :: प्रक्रिया ()
कन्वेयर प्रबंधक
UniversalSink :: getFromBelt ()
कन्वर्टर _{n ₁} :: प्रक्रिया ()
कन्वेयर प्रबंधक

पाइपलाइन के सामान्य संचालन को सुनिश्चित करने के लिए, जो कि अधिकांश सामान्य अनुप्रयोगों के कामकाज के लिए आवश्यक है, केवल एक ही कार्य करना आवश्यक है:

पाइपलाइन मैनेजर के पास कनवर्टर के प्रोसेस फंक्शन को कॉल करने का अधिकार नहीं है अगर उसी कन्वर्टर का प्रोसेस फंक्शन पहले से कॉल स्टैक पर है। (ए)

इस स्वयंसिद्ध का कार्यान्वयन कार्यान्वयन पर एक महत्वपूर्ण (और केवल) प्रतिबंध लगाता है (हम केवल एकल-थ्रेडेड केस के बारे में बात कर रहे हैं):

पाइपलाइन प्रबंधक के पास कनवर्टर के प्रोसेस फ़ंक्शन को कॉल करने का अधिकार नहीं है यदि कॉल-स्टैक में बाएं-सबसे कनवर्टर की प्रक्रिया फ़ंक्शन है।

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

यहां दो संभावित प्रबंधक कार्यान्वयन हैं:

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

संभव बन्स

लेख पाइपलाइन के कार्यान्वयन का एक सरल आरेख प्रदान करता है। इसके सुधारों को लागू किया जा सकता है:

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

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

निष्कर्ष

मैं इसके लिए माफी माँगता हूँ:

किसी विषय का अध्ययन करना, इस विषय पर साहित्य पढ़ना, शब्दावली या अवधारणा से डरना;
अंग्रेजी भाषा को जानना, पहचानकर्ताओं में अंग्रेजी शब्दों का उपयोग करने की मिसाल से भयभीत;
कोडिंग शैलियों के कई अनुयायियों से अलग मेरा (और एक शक के बिना, अधिक सही);
C ++ या एकाधिक वंशानुक्रम की नफरत;
प्रोग्रामर उपयोग किए गए C ++ कंस्ट्रक्शन से परिचित नहीं हैं।

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

लाइन कन्वेयर बेल्ट

यदि आप विशेष रूप से परेशान किए बिना रैखिक डेटा के प्रसंस्करण को डिज़ाइन करते हैं तो क्या होता है

कन्वेयर में सुधार

पाइपलाइन प्रबंधक कार्यान्वयन दृष्टिकोण

संभव बन्स

निष्कर्ष

More articles: