इन-प्लेस एल्गोरिदम
कंप्यूटर विज्ञान में, इन-प्लेस एल्गोरिथम एक एल्गोरिथम है जो बिना किसी सहायक डेटा संरचना का उपयोग किए इनपुट को रूपांतरित करता है। चूँकि, सहायक चर के लिए थोड़ी मात्रा में अतिरिक्त संग्रहण स्थान की अनुमति है। एल्गोरिथ्म निष्पादित होने पर इनपुट समान्यत: आउटपुट द्वारा ओवरराइट किया जाता है। एक इन-प्लेस एल्गोरिद्म केवल तत्वों के प्रतिस्थापन या अदला-बदली के माध्यम से अपने इनपुट अनुक्रम को अपडेट करता है। एक एल्गोरिदम जो इन-प्लेस नहीं है उसे कभी-कभी स्थान-स्थान या बाहर नहीं कहा जाता है।
इन-प्लेस के थोड़े अलग अर्थ हो सकते हैं। अपने सख्त रूप में, एल्गोरिदम में केवल अतिरिक्त स्थान की एक स्थिर मात्रा हो सकती है, जिसमें फ़ंक्शन कॉल और पॉइंटर्स सहित सब कुछ गिना जा सकता है। चूँकि यह फॉर्म बहुत सीमित है क्योंकि केवल लंबाई n सरणी के लिए एक इंडेक्स रखने के लिए O(log n) बिट्स की आवश्यकता होती है। अधिक समान्य रूप से, इन-प्लेस का अर्थ है कि एल्गोरिदम इनपुट में परिवर्तन करने के लिए अतिरिक्त स्थान का उपयोग नहीं करता है, किंतु इसके संचालन के लिए एक छोटे, चूँकि गैर-स्थिर अतिरिक्त स्थान की आवश्यकता हो सकती है। समान्यत: यह स्थान O(log n) होता है, चूँकि कभी-कभी O(n) में कुछ भी अनुमति दी जाती है। ध्यान दें कि स्थान कोम्लेक्सिटी में उपयोग किए गए स्थान के भाग के रूप में सूचकांक लंबाई की गणना करने या न करने के लिए भी विभिन्न विकल्प होते हैं। अधिकांशतः स्थान कोम्लेक्सिटी उनकी लंबाई को अनदेखा करते हुए, आवश्यक सूचकांकों या संकेतकों की संख्या के संदर्भ में दी जाती है। इस लेख में, हम सूचक लंबाई की गणना करते हुए कुल स्थान कोम्लेक्सिटी (डीएसपीएसीई) का उल्लेख करते हैं। इसलिए, विश्लेषण की तुलना में यहां स्थान आवश्यकताओं में एक अतिरिक्त log n कारक होता है जो सूचकांकों और संकेतकों की लंबाई को अनदेखा करता है।
एक एल्गोरिथम अपने स्थान उपयोग के भाग के रूप में आउटपुट की गणना कर भी सकता है और नहीं भी चूंकि इन-प्लेस एल्गोरिदम समान्यत: आउटपुट के साथ अपने इनपुट को ओवरराइट करते हैं, इसलिए अतिरिक्त स्थान की आवश्यकता नहीं होती है। राइट-ओनली मेमोरी या स्ट्रीम में आउटपुट लिखते समय, एल्गोरिथम के केवल कार्य स्थान पर विचार करना अधिक उपयुक्त हो सकता है। लॉग-स्पेस रिडक्शन जैसे सैद्धांतिक अनुप्रयोगों में, आउटपुट स्पेस को सदैव अनदेखा करना अधिक विशिष्ट है (इन स्थिति में यह अधिक आवश्यक है कि आउटपुट केवल लिखने के लिए हो)।
उदाहरण
n आइटमों की aसरणी को देखते हुए, मान लीजिए कि हम एक ऐसी सरणी चाहते हैं जो समान तत्वों को विपरीत क्रम में रखती है और मूल का निपटान करती है। ऐसा करने का एक सरल विधि यह है कि समान आकार की एक नई सरणी बनाएं, इसे उचित क्रम में aसे प्रतियों से भरें और फिर aको हटा दें।
function reverse(a[0..n - 1])
allocate b[0..n - 1]
for i from 0 to n - 1
b[n − 1 − i] := a[i]
return b
सामान्यतः, a और b को एक साथ उपलब्ध कराने के लिए O(n)
अतिरिक्त स्थान की आवश्यकता होती है। इसके अतिरिक्त, आवंटन और आवंटन समाप्त करना अधिकांशतः धीमा संचालन होता है। चूँकि हमें अब a की आवश्यकता नहीं है, हम इसके अतिरिक्त इस इन-प्लेस एल्गोरिथ्म का उपयोग करके इसे अपने स्वयं के विपरीत के साथ अधिलेखित कर सकते हैं, जिसके लिए सहायक चरiऔरtmpके लिए केवल पूर्णांकों की निरंतर संख्या (2) की आवश्यकता होगी, चाहे सरणी कितनी भी बड़ी क्यों न हो।
function reverse_in_place(a[0..n-1])
for i from 0 to floor((n-2)/2)
tmp := a[i]
a[i] := a[n − 1 − i]
a[n − 1 − i] := tmp
एक अन्य उदाहरण के रूप में, कई सॉर्टिंग एल्गोरिदम सरणियों को क्रमबद्ध क्रम में पुनर्व्यवस्थित करते हैं, जिनमें सम्मिलित हैं: बबल सॉर्ट, कॉम्ब सॉर्ट, चयन सॉर्ट, इंसर्शन सॉर्ट, हीप्सॉर्ट और शेल सॉर्ट इन एल्गोरिदम को केवल कुछ पॉइंटर्स की आवश्यकता होती है, इसलिए उनकी स्थान कोम्लेक्सिटी O(log n) है।[1]
सॉर्ट किए जाने वाले डेटा पर क्विकॉर्ट इन-प्लेस संचालित होता है। चूँकि क्विकसॉर्ट को इसके डिवाइड और कॉन्कर स्ट्रेटेजी में सबऐरे का ट्रैक रखने के लिए O(log n) स्टैक स्पेस पॉइंटर्स की आवश्यकता होती है। परिणाम स्वरुप, क्विकॉर्ट को O(log2 n) अतिरिक्त स्थान की आवश्यकता है। यद्यपि यह गैर-स्थिर स्थान तकनीकी रूप से क्विकॉर्ट को इन-प्लेस श्रेणी से बाहर ले जाता है, क्विकॉर्ट और अन्य एल्गोरिदम को केवल O(log n) अतिरिक्त पॉइंटर्स की आवश्यकता होती है जिन्हें समान्यत: इन-प्लेस एल्गोरिदम माना जाता है।
अधिकांश चयन एल्गोरिदम भी स्थान में हैं, चूँकि कुछ अंतिम, स्थिर-आकार के परिणाम खोजने की प्रक्रिया में इनपुट सरणी को पुनर्व्यवस्थित करते हैं।
कुछ टेक्स्ट हेरफेर एल्गोरिदम जैसे ट्रिम (प्रोग्रामिंग) और रिवर्स को इन-प्लेस किया जा सकता है।
कम्प्यूटेशनल कोम्लेक्सिटी में
कम्प्यूटेशनल कोम्लेक्सिटी सिद्धांत में, इन-प्लेस एल्गोरिदम की सख्त परिभाषा में O(1) स्पेस कोम्लेक्सिटी, वर्ग DSPACE(1) वाले सभी एल्गोरिदम सम्मिलित हैं। यह वर्ग बहुत सीमित है; यह नियमित भाषाओं के समान है।[2] वास्तव में, इसमें ऊपर सूचीबद्ध कोई भी उदाहरण सम्मिलित नहीं है।
एल्गोरिदम को समान्यत: एल में माना जाता है, समस्याओं की श्रेणी में O(log n) अतिरिक्त स्थान की आवश्यकता होती है। यह वर्ग व्यावहारिक परिभाषा के अधिक अनुरूप है, क्योंकि यह आकार n की संख्याओं को सूचक या सूचकांक के रूप में अनुमति देता है। चूँकि , यह विस्तारित परिभाषा अभी भी अपनी पुनरावर्ती कॉल के कारण क्विकॉर्ट को बाहर करती है।
एल के साथ इन-प्लेस एल्गोरिदम की पहचान करने के कुछ रौचक निहितार्थ हैं; उदाहरण के लिए, इसका अर्थ है कि एक अप्रत्यक्ष ग्राफ़ में दो नोड्स के बीच एक पथ उपस्थित है या नहीं यह निर्धारित करने के लिए एक (किंतु कोम्लेक्सिटी ) इन-प्लेस एल्गोरिदम है,[3] एक समस्या जिसके लिए डेप्थ-फर्स्ट सर्च (प्रत्येक नोड के लिए एक विज़िट किया गया बिट) जैसे विशिष्ट एल्गोरिदम का उपयोग करके O(n) अतिरिक्त स्थान की आवश्यकता होती है। यह बदले में समस्याओं के लिए इन-प्लेस एल्गोरिदम उत्पन्न करता है जैसे कि यह निर्धारित करना कि क्या कोई ग्राफ द्विदलीय है या यह परीक्षण करना कि क्या दो ग्राफ़ में जुड़े हुए घटकों की संख्या समान है।
यादृच्छिकता की भूमिका
कई स्थिति में यादृच्छिक एल्गोरिदम का उपयोग करके एल्गोरिदम की स्थान आवश्यकताओं में अधिक कट की जा सकती है। उदाहरण के लिए, यदि कोई यह जानना चाहता है कि क्या 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
