इन-प्लेस एल्गोरिदम
कंप्यूटर विज्ञान में, इन-प्लेस एल्गोरिथम एक एल्गोरिथम है जो बिना किसी सहायक डेटा संरचना का उपयोग किए इनपुट को रूपांतरित करता है। चूँकि, सहायक चर के लिए थोड़ी मात्रा में अतिरिक्त संग्रहण स्थान की अनुमति है। एल्गोरिथ्म निष्पादित होने पर इनपुट समान्यत: आउटपुट द्वारा ओवरराइट किया जाता है। एक इन-प्लेस एल्गोरिद्म केवल तत्वों के प्रतिस्थापन या अदला-बदली के माध्यम से अपने इनपुट अनुक्रम को अपडेट करता है। एक एल्गोरिदम जो इन-प्लेस नहीं है उसे कभी-कभी जगह-जगह या बाहर नहीं कहा जाता है।
इन-प्लेस के थोड़े अलग अर्थ हो सकते हैं। अपने सख्त रूप में, एल्गोरिदम में केवल अतिरिक्त स्थान की एक स्थिर मात्रा हो सकती है, जिसमें फ़ंक्शन कॉल और पॉइंटर्स सहित सब कुछ गिना जा सकता है। चूँकि , यह फॉर्म बहुत सीमित है क्योंकि केवल लंबाई n सरणी के लिए एक इंडेक्स रखने के लिए O(log n) बिट्स की आवश्यकता होती है। अधिक मोटे तौर पर, इन-प्लेस का मतलब है कि एल्गोरिदम इनपुट में हेरफेर करने के लिए अतिरिक्त स्थान का उपयोग नहीं करता है, लेकिन इसके संचालन के लिए एक छोटे, हालांकि गैर-स्थिर अतिरिक्त स्थान की आवश्यकता हो सकती है। समान्यत:, यह स्थान O(log n) होता है, हालांकि कभी-कभी O(n) में कुछ भी अनुमति दी जाती है। ध्यान दें कि अंतरिक्ष जटिलता में उपयोग किए गए स्थान के हिस्से के रूप में सूचकांक लंबाई की गणना करने या न करने के लिए भी विभिन्न विकल्प होते हैं। अक्सर, अंतरिक्ष जटिलता उनकी लंबाई को नजरअंदाज करते हुए, आवश्यक सूचकांकों या संकेतकों की संख्या के संदर्भ में दी जाती है। इस लेख में, हम सूचक लंबाई की गणना करते हुए कुल अंतरिक्ष जटिलता (डीएसपीएसीई) का उल्लेख करते हैं। इसलिए, विश्लेषण की तुलना में यहां स्थान आवश्यकताओं में एक अतिरिक्त लॉग एन कारक होता है जो सूचकांकों और संकेतकों की लंबाई को नजरअंदाज करता है।
एक एल्गोरिथम अपने स्थान उपयोग के भाग के रूप में आउटपुट की गणना कर भी सकता है और नहीं भी। चूंकि इन-प्लेस एल्गोरिदम समान्यत: आउटपुट के साथ अपने इनपुट को ओवरराइट करते हैं, इसलिए अतिरिक्त स्थान की आवश्यकता नहीं होती है। राइट-ओनली मेमोरी या स्ट्रीम में आउटपुट लिखते समय, एल्गोरिथम के केवल कार्य स्थान पर विचार करना अधिक उपयुक्त हो सकता है। लॉग-स्पेस रिडक्शन जैसे सैद्धांतिक अनुप्रयोगों में, आउटपुट स्पेस को हमेशा अनदेखा करना अधिक विशिष्ट है (इन मामलों में यह अधिक आवश्यक है कि आउटपुट केवल लिखने के लिए हो)।
उदाहरण
एक सरणी डेटा संरचना को देखते हुए a का n आइटम, मान लीजिए कि हम एक ऐसी सरणी चाहते हैं जो समान तत्वों को उलटे क्रम में रखती है और मूल का निपटान करती है। ऐसा करने का एक सरल तरीका समान आकार की एक नई सरणी बनाना है, इसे प्रतियों से भरें a उचित क्रम में और फिर हटा दें a.
फ़ंक्शन रिवर्स ([0..n - 1]) आवंटन बी [0..एन - 1] मैं 0 से n - 1 के लिए b[n − 1 − i] := a[i] वापसी ख
दुर्भाग्य से, इसकी आवश्यकता है O(n) सरणी रखने के लिए अतिरिक्त स्थान a और b एक साथ उपलब्ध है। साथ ही, मेमोरी प्रबंधन # आवंटन और डीललोकेशन अक्सर धीमे संचालन होते हैं। चूंकि हमें अब जरूरत नहीं है a, हम इसके बजाय इस इन-प्लेस एल्गोरिथम का उपयोग करके इसे अपने स्वयं के उत्क्रमण के साथ अधिलेखित कर सकते हैं, जिसे सहायक चर के लिए पूर्णांकों की निरंतर संख्या (2) की आवश्यकता होगी i और tmp, सरणी कितनी भी बड़ी क्यों न हो।
फ़ंक्शन रिवर्स_इन_प्लेस (एक [0..n-1]) मैं के लिए 0 से मंजिल तक ((n-2)/2) टीएमपी: = एक [मैं] a[i][:= a[n − 1 − i] एक [एन − 1 − i]�:= tmp
एक अन्य उदाहरण के रूप में, कई सॉर्टिंग एल्गोरिदम एरेज़ को इन-प्लेस सॉर्ट किए गए क्रम में पुनर्व्यवस्थित करते हैं, जिसमें शामिल हैं: बबल सॉर्ट, कॉम्ब सॉर्ट, सिलेक्शन सॉर्ट, इंसर्शन सॉर्ट, हीप्सोर्ट और शेल सॉर्ट। इन एल्गोरिदम को केवल कुछ पॉइंटर्स की आवश्यकता होती है, इसलिए उनकी अंतरिक्ष जटिलता होती है O(log n).[1] क्विकॉर्ट सॉर्ट किए जाने वाले डेटा पर इन-प्लेस संचालित होता है। चूँकि , क्विकसॉर्ट की आवश्यकता होती है O(log n) विभाजित करें और जीतें एल्गोरिथम रणनीति में उपसरणियों का ट्रैक रखने के लिए स्टैक स्पेस पॉइंटर्स। नतीजतन, क्विकॉर्ट की जरूरत है O(log2 n) अतिरिक्त स्थान। यद्यपि यह गैर-निरंतर स्थान तकनीकी रूप से इन-प्लेस श्रेणी, क्विकसॉर्ट और अन्य एल्गोरिदम से क्विकसॉर्ट लेता है, केवल आवश्यकता होती है O(log n) अतिरिक्त पॉइंटर्स को समान्यत: इन-प्लेस एल्गोरिदम माना जाता है।
अधिकांश चयन एल्गोरिदम भी जगह में हैं, हालांकि कुछ अंतिम, स्थिर-आकार के परिणाम खोजने की प्रक्रिया में इनपुट सरणी को पुनर्व्यवस्थित करते हैं।
कुछ टेक्स्ट हेरफेर एल्गोरिदम जैसे ट्रिम (प्रोग्रामिंग) और रिवर्स को इन-प्लेस किया जा सकता है।
कम्प्यूटेशनल जटिलता में
कम्प्यूटेशनल जटिलता सिद्धांत में, इन-प्लेस एल्गोरिदम की सख्त परिभाषा में सभी एल्गोरिदम शामिल हैं O(1) अंतरिक्ष जटिलता, वर्ग नियतात्मक स्थान (1)। यह वर्ग बहुत सीमित है; यह नियमित भाषाओं के बराबर है।[2] वास्तव में, इसमें ऊपर सूचीबद्ध किसी भी उदाहरण को शामिल नहीं किया गया है।
हम समान्यत: एल (जटिलता) में एल्गोरिदम पर विचार करते हैं, समस्याओं की श्रेणी की आवश्यकता होती है O(log n) अतिरिक्त स्थान, जगह में होना। यह वर्ग व्यावहारिक परिभाषा के अनुरूप अधिक है, क्योंकि यह आकार की संख्या की अनुमति देता है n संकेत या सूचक के रूप में। यह विस्तारित परिभाषा अभी भी क्विकसॉर्ट को बाहर करती है, चूँकि , इसकी पुनरावर्ती कॉल के कारण।
एल के साथ इन-प्लेस एल्गोरिदम की पहचान करने के कुछ दिलचस्प निहितार्थ हैं; उदाहरण के लिए, इसका मतलब है कि एक अप्रत्यक्ष ग्राफ में दो नोड्स के बीच पथ मौजूद है या नहीं, यह निर्धारित करने के लिए एक (बल्कि जटिल) इन-प्लेस एल्गोरिदम है,[3] एक समस्या जिसकी आवश्यकता है O(n) गहराई-प्रथम खोज (प्रत्येक नोड के लिए विज़िट किया गया बिट) जैसे विशिष्ट एल्गोरिदम का उपयोग करके अतिरिक्त स्थान। यह बदले में समस्याओं के लिए इन-प्लेस एल्गोरिदम उत्पन्न करता है जैसे कि यह निर्धारित करना कि क्या कोई ग्राफ द्विदलीय ग्राफ है या परीक्षण करता है कि क्या दो ग्राफों में समान संख्या में जुड़े घटक (ग्राफ सिद्धांत) हैं। अधिक जानकारी के लिए SL (जटिलता) देखें।
यादृच्छिकता की भूमिका
कई मामलों में, एक यादृच्छिक एल्गोरिथ्म का उपयोग करके एक एल्गोरिथ्म की स्थान आवश्यकताओं में भारी कटौती की जा सकती है। उदाहरण के लिए, मान लें कि हम यह जानना चाहते हैं कि क्या ग्राफ में दो शीर्ष हैं n कोने ग्राफ़ के समान कनेक्टेड घटक (ग्राफ़ सिद्धांत) में हैं। इसे निर्धारित करने के लिए कोई ज्ञात सरल, निर्धारक, इन-प्लेस एल्गोरिथम नहीं है, लेकिन अगर हम बस एक शीर्ष पर शुरू करते हैं और लगभग एक यादृच्छिक चलना करते हैं 20n3 चरण, संभावना है कि हम दूसरे शीर्ष पर ठोकर खाएंगे बशर्ते कि यह एक ही घटक में बहुत अधिक हो। इसी तरह, प्रारंभिक परीक्षण के लिए सरल यादृच्छिक इन-प्लेस एल्गोरिदम हैं जैसे कि मिलर-राबिन प्राइमलिटी टेस्ट, और पोलार्ड के आरओ एल्गोरिदम जैसे सरल इन-प्लेस यादृच्छिक फैक्टरिंग एल्गोरिदम भी हैं। इस घटना की अधिक चर्चा के लिए आरएल (जटिलता) और बीपीएल (जटिलता) देखें।
कार्यात्मक प्रोग्रामिंग में
कार्यात्मक प्रोग्रामिंग भाषाएं अक्सर डेटा को अधिलेखित करने वाले स्पष्ट इन-प्लेस एल्गोरिदम को हतोत्साहित करती हैं या समर्थन नहीं करती हैं, क्योंकि यह एक प्रकार का साइड इफेक्ट (कंप्यूटर विज्ञान) है; इसके बजाय, वे केवल नए डेटा के निर्माण की अनुमति देते हैं। हालांकि, अच्छे कार्यात्मक भाषा संकलक अक्सर पहचान लेंगे जब एक मौजूदा के समान एक वस्तु बनाई जाती है और फिर पुराने को फेंक दिया जाता है, और हुड के नीचे एक साधारण उत्परिवर्तन में इसे अनुकूलित करेगा।
ध्यान दें कि सैद्धांतिक रूप से इन-प्लेस एल्गोरिदम का सावधानीपूर्वक निर्माण करना संभव है जो डेटा को संशोधित नहीं करता है (जब तक कि डेटा का उपयोग नहीं किया जा रहा हो), लेकिन यह व्यवहार में शायद ही कभी किया जाता है। विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं देखें।
यह भी देखें
- सॉर्टिंग एल्गोरिथ्म#एल्गोरिदम की तुलना|इन-प्लेस और नॉट-इन-प्लेस सॉर्टिंग एल्गोरिदम की तालिका
संदर्भ
- ↑ The bit space requirement of a pointer is O(log n), but pointer size can be considered a constant in most sorting applications.
- ↑ Maciej Liśkiewicz and Rüdiger Reischuk. The Complexity World below Logarithmic Space. Structure in Complexity Theory Conference, pp. 64-78. 1994. Online: p. 3, Theorem 2.
- ↑ Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, MR 2445014, S2CID 207168478, ECCC TR04-094
