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

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

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