रन-टाइम एल्गोरिदम विशेषज्ञता

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

यह विचार प्रोग्राम अनुवाद के अनुकूलन में आंशिक मूल्यांकन के उपयोग से प्रेरित है। प्रमेय सिद्ध करने वालों में कई मुख्य संक्रियाएँ निम्नलिखित पैटर्न प्रदर्शित करती हैं। मान लीजिए कि हमें कुछ एल्गोरिदम निष्पादित करने की आवश्यकता है ${\mathit {alg}}(A,B)$ ऐसी स्थिति में जहां का मूल्य $A$ के संभावित रूप से कई अलग-अलग मानों के लिए नियत है $B$. इसे कुशलतापूर्वक करने के लिए, हम एक विशेषज्ञता खोजने का प्रयास कर सकते हैं ${\mathit {alg}}$ प्रत्येक निश्चित के लिए $A$, यानी, ऐसा एल्गोरिदम ${\mathit {alg}}_{A}$, वह क्रियान्वित ${\mathit {alg}}_{A}(B)$ क्रियान्वित करने के बराबर है ${\mathit {alg}}(A,B)$.

विशिष्ट एल्गोरिथ्म सामान्य की तुलना में अधिक कुशल हो सकता है, क्योंकि यह निश्चित मूल्य के कुछ विशेष गुणों का फायदा उठा सकता है $A$. आमतौर पर, ${\mathit {alg}}_{A}(B)$ कुछ ऑपरेशनों से बच सकते हैं ${\mathit {alg}}(A,B)$ प्रदर्शन करना होगा, अगर उन्हें इस विशेष पैरामीटर के लिए बेमानी माना जाता है $A$. विशेष रूप से, हम अक्सर कुछ परीक्षणों की पहचान कर सकते हैं जो सही या गलत हैं $A$, अनरोल लूप और रिकर्सन इत्यादि।

आंशिक मूल्यांकन से अंतर

रन-टाइम विशेषज्ञता और आंशिक मूल्यांकन के बीच मुख्य अंतर यह है कि $A$ जिस पर ${\mathit {alg}}$ विशिष्ट हैं, स्थिर रूप से ज्ञात नहीं हैं, इसलिए विशेषज्ञता रन-टाइम पर होती है।

एक महत्वपूर्ण तकनीकी अंतर भी है। कुछ प्रोग्रामिंग भाषा में कोड के रूप में स्पष्ट रूप से दर्शाए गए एल्गोरिदम पर आंशिक मूल्यांकन लागू होता है। रन-टाइम में, हमें किसी ठोस प्रतिनिधित्व की आवश्यकता नहीं होती है ${\mathit {alg}}$. हमें केवल कल्पना करनी है ${\mathit {alg}}$ जब हम विशेषज्ञता प्रक्रिया को प्रोग्राम करते हैं। हम सभी की जरूरत है विशेष संस्करण का एक ठोस प्रतिनिधित्व है ${\mathit {alg}}_{A}$. इसका यह भी अर्थ है कि हम एल्गोरिदम को विशिष्ट बनाने के लिए किसी भी सार्वभौमिक तरीके का उपयोग नहीं कर सकते हैं, जो आमतौर पर आंशिक मूल्यांकन के मामले में होता है। इसके बजाय, हमें प्रत्येक विशेष एल्गोरिथम के लिए एक विशेषज्ञता प्रक्रिया को प्रोग्राम करना होगा ${\mathit {alg}}$. ऐसा करने का एक महत्वपूर्ण लाभ यह है कि हम विशिष्टताओं का फायदा उठाने के लिए कुछ शक्तिशाली तदर्थ तरकीबों का उपयोग कर सकते हैं ${\mathit {alg}}$ और का प्रतिनिधित्व $A$ और $B$, जो किसी भी सार्वभौमिक विशेषज्ञता विधियों की पहुंच से बाहर हैं।

संकलन के साथ विशेषज्ञता

विशेष एल्गोरिथम को एक ऐसे रूप में दर्शाया जाना चाहिए जिसकी व्याख्या की जा सके। कई स्थितियों में, आमतौर पर कब ${\mathit {alg}}_{A}(B)$ कई मूल्यों पर गणना की जानी है $B$ एक पंक्ति में, हम लिख सकते हैं ${\mathit {alg}}_{A}$ एक विशेष अमूर्त मशीन के कोड के रूप में, और हम अक्सर ऐसा कहते हैं $A$ संकलित है। तब कोड को अतिरिक्त रूप से उत्तर-संरक्षण परिवर्तनों द्वारा अनुकूलित किया जा सकता है जो केवल अमूर्त मशीन के निर्देशों के शब्दार्थ पर निर्भर करता है।

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

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

डेटा-और-एल्गोरिदम विशेषज्ञता

ऐसे हालात हैं जब कई उदाहरण हैं $A$ लंबी अवधि के भंडारण और कॉल के लिए अभिप्रेत है ${\mathit {alg}}(A,B)$ भिन्न के साथ होता है $B$ एक अप्रत्याशित क्रम में। उदाहरण के लिए, हमें जाँच करनी पड़ सकती है ${\mathit {alg}}(A_{1},B_{1})$ पहले तो ${\mathit {alg}}(A_{2},B_{2})$, तब ${\mathit {alg}}(A_{1},B_{3})$, और इसी तरह। ऐसी परिस्थितियों में, अत्यधिक स्मृति उपयोग के कारण संकलन के साथ पूर्ण पैमाने पर विशेषज्ञता उपयुक्त नहीं हो सकती है। हालाँकि, हम कभी-कभी एक कॉम्पैक्ट विशेष प्रतिनिधित्व पा सकते हैं $A^{\prime }$ हरएक के लिए $A$, जिसे इसके साथ या इसके बजाय संग्रहीत किया जा सकता है $A$. हम एक प्रकार को भी परिभाषित करते हैं ${\mathit {alg}}^{\prime }$ जो इस प्रतिनिधित्व पर काम करता है और कोई भी कॉल ${\mathit {alg}}(A,B)$ द्वारा प्रतिस्थापित किया जाता है ${\mathit {alg}}^{\prime }(A^{\prime },B)$, उसी कार्य को तेज़ी से करने का इरादा रखता है.

यह भी देखें

• प्स्य्को, पायथन (प्रोग्रामिंग लैंग्वेज) के लिए एक विशेषज्ञ रन-टाइम कंपाइलर
• मल्टी-स्टेज प्रोग्रामिंग

संदर्भ

• A. Voronkov, "The Anatomy of Vampire: Implementing Bottom-Up Procedures with Code Trees", Journal of Automated Reasoning, 15(2), 1995 (original idea)

अग्रिम पठन

• A. Riazanov and A. Voronkov, "Efficient Checking of Term Ordering Constraints", Proc. IJCAR 2004, Lecture Notes in Artificial Intelligence 3097, 2004 (compact but self-contained illustration of the method)
• A. Riazanov and A. Voronkov, Efficient Instance Retrieval with Standard and Relational Path Indexing, Information and Computation, 199(1-2), 2005 (contains another illustration of the method)
• A. Riazanov, "Implementing an Efficient Theorem Prover", PhD thesis, The University of Manchester, 2003 (contains the most comprehensive description of the method and many examples)