इन-प्लेस एल्गोरिदम: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Redirect|In-place|execute in place file systems|Execute in place}}कंप्यूटर विज्ञान में, इन-प्लेस एल्गोरिथम एक एल्गोरिथम है जो बिना किसी सहायक डेटा संरचना का उपयोग किए इनपुट को रूपांतरित करता है। हालाँकि, सहायक चर के लिए थोड़ी मात्रा में अतिरिक्त संग्रहण स्थान की अनुमति है। एल्गोरिथ्म निष्पादित होने पर इनपुट आमतौर पर आउटपुट द्वारा ओवरराइट किया जाता है। एक इन-प्लेस एल्गोरिद्म केवल तत्वों के प्रतिस्थापन या अदला-बदली के माध्यम से अपने इनपुट अनुक्रम को अपडेट करता है। एक एल्गोरिदम जो इन-प्लेस नहीं है उसे कभी-कभी जगह-जगह या बाहर नहीं कहा जाता है।
{{Redirect|स्पेस में|फ़ाइल सिस्टम को यथास्थान निष्पादित करें|यथास्थान निष्पादित करें}}


इन-प्लेस के थोड़े अलग अर्थ हो सकते हैं। अपने सख्त रूप में, एल्गोरिदम में केवल एक अंतरिक्ष जटिलता हो सकती है, जिसमें सबरूटीन कॉल और पॉइंटर (कंप्यूटर प्रोग्रामिंग) सहित सब कुछ शामिल है। हालाँकि, यह फॉर्म बहुत सीमित है क्योंकि केवल एक लंबाई के लिए एक इंडेक्स है {{math|''n''}} सरणी की आवश्यकता है {{math|''O''(log ''n'')}} बिट्स। अधिक मोटे तौर पर, इन-प्लेस का अर्थ है कि एल्गोरिथ्म इनपुट में हेरफेर करने के लिए अतिरिक्त स्थान का उपयोग नहीं करता है, लेकिन इसके संचालन के लिए एक छोटे से गैर-स्थिर अतिरिक्त स्थान की आवश्यकता हो सकती है। आमतौर पर, यह स्थान है {{math|''O''(log ''n'')}}, हालांकि कभी-कभी कुछ भी {{math|''O''(''n'')}} की अनुमति है। ध्यान दें कि अंतरिक्ष की जटिलता में उपयोग किए गए स्थान के हिस्से के रूप में सूचकांक लंबाई की गणना करने या न करने के लिए अलग-अलग विकल्प हैं। अक्सर, अंतरिक्ष की जटिलता को उनकी लंबाई की अनदेखी करते हुए आवश्यक सूचकांकों या पॉइंटर्स की संख्या के संदर्भ में दिया जाता है। इस लेख में, हम कुल अंतरिक्ष जटिलता (नियतात्मक स्थान) का उल्लेख करते हैं, सूचक लंबाई की गणना करते हैं। इसलिए, यहां अंतरिक्ष की आवश्यकताएं अतिरिक्त हैं {{math|log ''n''}} कारक एक विश्लेषण की तुलना में जो सूचकांकों और पॉइंटर्स की लंबाई को अनदेखा करता है।
कंप्यूटर विज्ञान में, इन-प्लेस एल्गोरिथम एक एल्गोरिथम है जो बिना किसी सहायक डेटा संरचना का उपयोग किए इनपुट को रूपांतरित करता है। चूँकि, सहायक चर के लिए थोड़ी मात्रा में अतिरिक्त संग्रहण स्थान की अनुमति है। एल्गोरिथ्म निष्पादित होने पर इनपुट समान्यत: आउटपुट द्वारा ओवरराइट किया जाता है। एक इन-प्लेस एल्गोरिद्म केवल तत्वों के प्रतिस्थापन या अदला-बदली के माध्यम से अपने इनपुट अनुक्रम को अपडेट करता है। एक एल्गोरिदम जो इन-प्लेस नहीं है उसे कभी-कभी स्थान-स्थान या बाहर नहीं कहा जाता है।


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


== उदाहरण ==
== उदाहरण ==


एक सरणी डेटा संरचना को देखते हुए {{code|a}} का {{math|''n''}} आइटम, मान लीजिए कि हम एक ऐसी सरणी चाहते हैं जो समान तत्वों को उलटे क्रम में रखती है और मूल का निपटान करती है। ऐसा करने का एक सरल तरीका समान आकार की एक नई सरणी बनाना है, इसे प्रतियों से भरें {{code|a}} उचित क्रम में और फिर हटा दें {{code|a}}.
n आइटमों की {{code|a}}सरणी को देखते हुए, मान लीजिए कि हम एक ऐसी सरणी चाहते हैं जो समान तत्वों को विपरीत क्रम में रखती है और मूल का निपटान करती है। ऐसा करने का एक सरल विधि यह है कि समान आकार की एक नई सरणी बनाएं, इसे उचित क्रम में {{code|a}}से प्रतियों से भरें और फिर {{code|a}}को हटा दें।


  फ़ंक्शन रिवर्स ([0..n - 1])
'''function''' reverse(a[0..n - 1])
  आवंटन बी [0..एन - 1]
      allocate b[0..n - 1]
  मैं 0 से n - 1 के लिए
      '''for''' i '''from''' 0 '''to''' n - 1
  b[n − 1 − i] := a[i]
          b[n − 1 − i] := a[i]
  वापसी ख
      '''return''' b


दुर्भाग्य से, इसकी आवश्यकता है {{math|''O''(''n'')}} सरणी रखने के लिए अतिरिक्त स्थान {{code|a}} और {{code|b}} एक साथ उपलब्ध है। साथ ही, मेमोरी प्रबंधन # आवंटन और डीललोकेशन अक्सर धीमे संचालन होते हैं। चूंकि हमें अब जरूरत नहीं है {{code|a}}, हम इसके बजाय इस इन-प्लेस एल्गोरिथम का उपयोग करके इसे अपने स्वयं के उत्क्रमण के साथ अधिलेखित कर सकते हैं, जिसे सहायक चर के लिए पूर्णांकों की निरंतर संख्या (2) की आवश्यकता होगी {{code|i}} और {{code|tmp}}, सरणी कितनी भी बड़ी क्यों न हो।
सामान्यतः, {{code|a}} और {{code|b}} को एक साथ उपलब्ध कराने के लिए {{math|''O''(''n'')                                                                                      
                                                                                                                                                           
                                                                                                          }} अतिरिक्त स्थान की आवश्यकता होती है। इसके अतिरिक्त, आवंटन और आवंटन समाप्त करना अधिकांशतः धीमा संचालन होता है। चूँकि हमें अब a की आवश्यकता नहीं है, हम इसके अतिरिक्त इस इन-प्लेस एल्गोरिथ्म का उपयोग करके इसे अपने स्वयं के विपरीत के साथ अधिलेखित कर सकते हैं, जिसके लिए सहायक चर{{code|i}} और {{code|tmp}}के लिए केवल पूर्णांकों की निरंतर संख्या (2) की आवश्यकता होगी, चाहे सरणी कितनी भी बड़ी क्यों न हो।


  फ़ंक्शन रिवर्स_इन_प्लेस (एक [0..n-1])
'''function''' reverse_in_place(a[0..n-1])
  मैं के लिए 0 से मंजिल तक ((n-2)/2)
      '''for''' i '''from''' 0 '''to''' floor((n-2)/2)
  टीएमपी: = एक [मैं]
          tmp := a[i]
  a[i][:= a[n − 1 − i]
          a[i] := a[n − 1 − i]
  एक [एन − 1 − i]:= tmp
          a[n − 1 − i] := tmp


एक अन्य उदाहरण के रूप में, कई सॉर्टिंग एल्गोरिदम एरेज़ को इन-प्लेस सॉर्ट किए गए क्रम में पुनर्व्यवस्थित करते हैं, जिसमें शामिल हैं: बबल सॉर्ट, कॉम्ब सॉर्ट, सिलेक्शन सॉर्ट, इंसर्शन सॉर्ट, हीप्सोर्ट और शेल सॉर्ट। इन एल्गोरिदम को केवल कुछ पॉइंटर्स की आवश्यकता होती है, इसलिए उनकी अंतरिक्ष जटिलता होती है {{math|''O''(log ''n'')}}.<ref>The bit space requirement of a pointer is {{math|''O''(log ''n'')}}, but pointer size can be considered a constant in most sorting applications.</ref>
एक अन्य उदाहरण के रूप में, कई सॉर्टिंग एल्गोरिदम सरणियों को क्रमबद्ध क्रम में पुनर्व्यवस्थित करते हैं, जिनमें सम्मिलित हैं: बबल सॉर्ट, कॉम्ब सॉर्ट, चयन सॉर्ट, इंसर्शन सॉर्ट, हीप्सॉर्ट और शेल सॉर्ट इन एल्गोरिदम को केवल कुछ पॉइंटर्स की आवश्यकता होती है, इसलिए उनकी स्थान कोम्लेक्सिटी {{math|''O''(log ''n'')}} है।<ref>The bit space requirement of a pointer is {{math|''O''(log ''n'')}}, but pointer size can be considered a constant in most sorting applications.</ref>
क्विकॉर्ट सॉर्ट किए जाने वाले डेटा पर इन-प्लेस संचालित होता है। हालाँकि, क्विकसॉर्ट की आवश्यकता होती है {{math|''O''(log ''n'')}} विभाजित करें और जीतें एल्गोरिथम रणनीति में उपसरणियों का ट्रैक रखने के लिए स्टैक स्पेस पॉइंटर्स। नतीजतन, क्विकॉर्ट की जरूरत है {{math|''O''(log{{sup|2}} ''n'')}} अतिरिक्त स्थान। यद्यपि यह गैर-निरंतर स्थान तकनीकी रूप से इन-प्लेस श्रेणी, क्विकसॉर्ट और अन्य एल्गोरिदम से क्विकसॉर्ट लेता है, केवल आवश्यकता होती है {{math|''O''(log ''n'')}} अतिरिक्त पॉइंटर्स को आमतौर पर इन-प्लेस एल्गोरिदम माना जाता है।


अधिकांश चयन एल्गोरिदम भी जगह में हैं, हालांकि कुछ अंतिम, स्थिर-आकार के परिणाम खोजने की प्रक्रिया में इनपुट सरणी को पुनर्व्यवस्थित करते हैं।
सॉर्ट किए जाने वाले डेटा पर क्विकॉर्ट इन-प्लेस संचालित होता है। चूँकि क्विकसॉर्ट को इसके डिवाइड और कॉन्कर स्ट्रेटेजी में सबऐरे का ट्रैक रखने के लिए {{math|''O''(log ''n'')}} स्टैक स्पेस पॉइंटर्स की आवश्यकता होती है। परिणाम स्वरुप, क्विकॉर्ट को {{math|''O''(log{{sup|2}} ''n'')}} अतिरिक्त स्थान की आवश्यकता है। यद्यपि यह गैर-स्थिर स्थान तकनीकी रूप से क्विकॉर्ट को इन-प्लेस श्रेणी से बाहर ले जाता है, क्विकॉर्ट और अन्य एल्गोरिदम को केवल {{math|''O''(log ''n'')}} अतिरिक्त पॉइंटर्स की आवश्यकता होती है जिन्हें समान्यत: इन-प्लेस एल्गोरिदम माना जाता है।
 
अधिकांश चयन एल्गोरिदम भी स्थान में हैं, चूँकि कुछ अंतिम, स्थिर-आकार के परिणाम खोजने की प्रक्रिया में इनपुट सरणी को पुनर्व्यवस्थित करते हैं।


कुछ टेक्स्ट हेरफेर एल्गोरिदम जैसे ट्रिम (प्रोग्रामिंग) और रिवर्स को इन-प्लेस किया जा सकता है।
कुछ टेक्स्ट हेरफेर एल्गोरिदम जैसे ट्रिम (प्रोग्रामिंग) और रिवर्स को इन-प्लेस किया जा सकता है।


== कम्प्यूटेशनल जटिलता में ==
== कम्प्यूटेशनल कोम्लेक्सिटी में ==


कम्प्यूटेशनल जटिलता सिद्धांत में, इन-प्लेस एल्गोरिदम की सख्त परिभाषा में सभी एल्गोरिदम शामिल हैं {{math|''O''(1)}} अंतरिक्ष जटिलता, वर्ग नियतात्मक स्थान (1)यह वर्ग बहुत सीमित है; यह नियमित भाषाओं के बराबर है।<ref>Maciej Liśkiewicz and Rüdiger Reischuk. [http://citeseer.ist.psu.edu/34203.html The Complexity World below Logarithmic Space]. ''Structure in Complexity Theory Conference'', pp. 64-78. 1994. Online: p. 3, Theorem 2.</ref> वास्तव में, इसमें ऊपर सूचीबद्ध किसी भी उदाहरण को शामिल नहीं किया गया है।
कम्प्यूटेशनल कोम्लेक्सिटी सिद्धांत में, इन-प्लेस एल्गोरिदम की सख्त परिभाषा में {{math|''O''(1)}} स्पेस कोम्लेक्सिटी, वर्ग '''DSPACE'''(1) वाले सभी एल्गोरिदम सम्मिलित हैं। यह वर्ग बहुत सीमित है; यह नियमित भाषाओं के समान है।<ref>Maciej Liśkiewicz and Rüdiger Reischuk. [http://citeseer.ist.psu.edu/34203.html The Complexity World below Logarithmic Space]. ''Structure in Complexity Theory Conference'', pp. 64-78. 1994. Online: p. 3, Theorem 2.</ref> वास्तव में, इसमें ऊपर सूचीबद्ध कोई भी उदाहरण सम्मिलित नहीं है।


हम आमतौर पर एल (जटिलता) में एल्गोरिदम पर विचार करते हैं, समस्याओं की श्रेणी की आवश्यकता होती है {{math|''O''(log ''n'')}} अतिरिक्त स्थान, जगह में होना। यह वर्ग व्यावहारिक परिभाषा के अनुरूप अधिक है, क्योंकि यह आकार की संख्या की अनुमति देता है {{math|''n''}} संकेत या सूचक के रूप में। यह विस्तारित परिभाषा अभी भी क्विकसॉर्ट को बाहर करती है, हालाँकि, इसकी पुनरावर्ती कॉल के कारण।
एल्गोरिदम को समान्यत: एल में माना जाता है, समस्याओं की श्रेणी में {{math|''O''(log ''n'')}} अतिरिक्त स्थान की आवश्यकता होती है। यह वर्ग व्यावहारिक परिभाषा के अधिक अनुरूप है, क्योंकि यह आकार n की संख्याओं को सूचक या सूचकांक के रूप में अनुमति देता है। चूँकि , यह विस्तारित परिभाषा अभी भी अपनी पुनरावर्ती कॉल के कारण क्विकॉर्ट को बाहर करती है।


एल के साथ इन-प्लेस एल्गोरिदम की पहचान करने के कुछ दिलचस्प निहितार्थ हैं; उदाहरण के लिए, इसका मतलब है कि एक अप्रत्यक्ष ग्राफ में दो नोड्स के बीच पथ मौजूद है या नहीं, यह निर्धारित करने के लिए एक (बल्कि जटिल) इन-प्लेस एल्गोरिदम है,<ref>{{citation
एल के साथ इन-प्लेस एल्गोरिदम की पहचान करने के कुछ रौचक निहितार्थ हैं; उदाहरण के लिए, इसका अर्थ है कि एक अप्रत्यक्ष ग्राफ़ में दो नोड्स के बीच एक पथ उपस्थित है या नहीं यह निर्धारित करने के लिए एक (किंतु  कोम्लेक्सिटी ) इन-प्लेस एल्गोरिदम है,<ref>{{citation
  | last = Reingold | first = Omer | author-link = Omer Reingold
  | last = Reingold | first = Omer | author-link = Omer Reingold
  | doi = 10.1145/1391289.1391291
  | doi = 10.1145/1391289.1391291
Line 46: Line 51:
  | title = Undirected connectivity in log-space
  | title = Undirected connectivity in log-space
  | volume = 55
  | volume = 55
  | year = 2008| s2cid = 207168478 }}</ref> एक समस्या जिसकी आवश्यकता है {{math|''O''(''n'')}} गहराई-प्रथम खोज (प्रत्येक नोड के लिए विज़िट किया गया बिट) जैसे विशिष्ट एल्गोरिदम का उपयोग करके अतिरिक्त स्थान। यह बदले में समस्याओं के लिए इन-प्लेस एल्गोरिदम उत्पन्न करता है जैसे कि यह निर्धारित करना कि क्या कोई ग्राफ द्विदलीय ग्राफ है या परीक्षण करता है कि क्या दो ग्राफों में समान संख्या में जुड़े घटक (ग्राफ सिद्धांत) हैं। अधिक जानकारी के लिए SL (जटिलता) देखें।
  | year = 2008| s2cid = 207168478 }}</ref> एक समस्या जिसके लिए डेप्थ-फर्स्ट सर्च (प्रत्येक नोड के लिए एक विज़िट किया गया बिट) जैसे विशिष्ट एल्गोरिदम का उपयोग करके {{math|''O''(''n'')}} अतिरिक्त स्थान की आवश्यकता होती है। यह बदले में समस्याओं के लिए इन-प्लेस एल्गोरिदम उत्पन्न करता है जैसे कि यह निर्धारित करना कि क्या कोई ग्राफ द्विदलीय है या यह परीक्षण करना कि क्या दो ग्राफ़ में जुड़े हुए घटकों की संख्या समान है।


== यादृच्छिकता की भूमिका ==
== यादृच्छिकता की भूमिका ==


कई मामलों में, एक यादृच्छिक एल्गोरिथ्म का उपयोग करके एक एल्गोरिथ्म की स्थान आवश्यकताओं में भारी कटौती की जा सकती है। उदाहरण के लिए, मान लें कि हम यह जानना चाहते हैं कि क्या ग्राफ में दो शीर्ष हैं {{math|''n''}} कोने ग्राफ़ के समान कनेक्टेड घटक (ग्राफ़ सिद्धांत) में हैं। इसे निर्धारित करने के लिए कोई ज्ञात सरल, निर्धारक, इन-प्लेस एल्गोरिथम नहीं है, लेकिन अगर हम बस एक शीर्ष पर शुरू करते हैं और लगभग एक यादृच्छिक चलना करते हैं {{math|20''n''{{sup|3}}}} चरण, संभावना है कि हम दूसरे शीर्ष पर ठोकर खाएंगे बशर्ते कि यह एक ही घटक में बहुत अधिक हो। इसी तरह, प्रारंभिक परीक्षण के लिए सरल यादृच्छिक इन-प्लेस एल्गोरिदम हैं जैसे कि मिलर-राबिन प्राइमलिटी टेस्ट, और पोलार्ड के आरओ एल्गोरिदम जैसे सरल इन-प्लेस यादृच्छिक फैक्टरिंग एल्गोरिदम भी हैं। इस घटना की अधिक चर्चा के लिए आरएल (जटिलता) और बीपीएल (जटिलता) देखें।
कई स्थिति में यादृच्छिक एल्गोरिदम का उपयोग करके एल्गोरिदम की स्थान आवश्यकताओं में अधिक कट की जा सकती है। उदाहरण के लिए, यदि कोई यह जानना चाहता है कि क्या n शीर्षों वाले ग्राफ़ में दो शीर्ष ग्राफ़ के एक ही जुड़े हुए घटक में हैं, तो इसे निर्धारित करने के लिए कोई ज्ञात सरल, नियतात्मक, इन-प्लेस एल्गोरिदम नहीं है। चूँकि , अगर हम बस एक शीर्ष से प्रारंभ करते हैं और लगभग {{math|20''n''{{sup|3}}}} कदमों की रैंडमाइज्ड सैर करते हैं तो संभावना है कि हम दूसरे शीर्ष पर ठोकर खाएँगे, परन्तु कि वह एक ही घटक में होते है । इसी तरह, प्राइमलिटी परीक्षण के लिए मिलर-राबिन प्राइमलिटी टेस्ट जैसे सरल रैंडमाइज्ड इन-प्लेस एल्गोरिदम हैं, और पोलार्ड के आरएचओ एल्गोरिदम जैसे सरल इन-प्लेस रैंडमाइज्ड फैक्टरिंग एल्गोरिदम भी हैं।


== कार्यात्मक प्रोग्रामिंग में ==
== कार्यात्मक प्रोग्रामिंग में ==


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


ध्यान दें कि सैद्धांतिक रूप से इन-प्लेस एल्गोरिदम का सावधानीपूर्वक निर्माण करना संभव है जो डेटा को संशोधित नहीं करता है (जब तक कि डेटा का उपयोग नहीं किया जा रहा हो), लेकिन यह व्यवहार में शायद ही कभी किया जाता है। विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं देखें।
ध्यान दें कि सैद्धांतिक रूप से इन-प्लेस एल्गोरिदम का सावधानीपूर्वक निर्माण करना संभव है जो डेटा को संशोधित नहीं करता है (जब तक कि डेटा का उपयोग नहीं किया जा रहा हो), किंतु यह व्यवहार में संभवतः ही कभी किया जाता है। विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं देखें।


== यह भी देखें ==
== यह भी देखें ==
* सॉर्टिंग एल्गोरिथ्म#एल्गोरिदम की तुलना|इन-प्लेस और नॉट-इन-प्लेस सॉर्टिंग एल्गोरिदम की तालिका
* इन-प्लेस और नॉट-इन-प्लेस सॉर्टिंग एल्गोरिदम की तालिका


== संदर्भ ==
== संदर्भ ==
<references/>
<references/>


{{DEFAULTSORT:In-Place Algorithm}}[[Category:एल्गोरिदम]]
{{DEFAULTSORT:In-Place Algorithm}}
 


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page|In-Place Algorithm]]
[[Category:Created On 05/01/2023]]
[[Category:Created On 05/01/2023|In-Place Algorithm]]
[[Category:Machine Translated Page|In-Place Algorithm]]
[[Category:Missing redirects|In-Place Algorithm]]
[[Category:Templates Vigyan Ready|In-Place Algorithm]]
[[Category:एल्गोरिदम|In-Place Algorithm]]

Latest revision as of 10:15, 28 July 2023

कंप्यूटर विज्ञान में, इन-प्लेस एल्गोरिथम एक एल्गोरिथम है जो बिना किसी सहायक डेटा संरचना का उपयोग किए इनपुट को रूपांतरित करता है। चूँकि, सहायक चर के लिए थोड़ी मात्रा में अतिरिक्त संग्रहण स्थान की अनुमति है। एल्गोरिथ्म निष्पादित होने पर इनपुट समान्यत: आउटपुट द्वारा ओवरराइट किया जाता है। एक इन-प्लेस एल्गोरिद्म केवल तत्वों के प्रतिस्थापन या अदला-बदली के माध्यम से अपने इनपुट अनुक्रम को अपडेट करता है। एक एल्गोरिदम जो इन-प्लेस नहीं है उसे कभी-कभी स्थान-स्थान या बाहर नहीं कहा जाता है।

इन-प्लेस के थोड़े अलग अर्थ हो सकते हैं। अपने सख्त रूप में, एल्गोरिदम में केवल अतिरिक्त स्थान की एक स्थिर मात्रा हो सकती है, जिसमें फ़ंक्शन कॉल और पॉइंटर्स सहित सब कुछ गिना जा सकता है। चूँकि यह फॉर्म बहुत सीमित है क्योंकि केवल लंबाई 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 कदमों की रैंडमाइज्ड सैर करते हैं तो संभावना है कि हम दूसरे शीर्ष पर ठोकर खाएँगे, परन्तु कि वह एक ही घटक में होते है । इसी तरह, प्राइमलिटी परीक्षण के लिए मिलर-राबिन प्राइमलिटी टेस्ट जैसे सरल रैंडमाइज्ड इन-प्लेस एल्गोरिदम हैं, और पोलार्ड के आरएचओ एल्गोरिदम जैसे सरल इन-प्लेस रैंडमाइज्ड फैक्टरिंग एल्गोरिदम भी हैं।

कार्यात्मक प्रोग्रामिंग में

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

ध्यान दें कि सैद्धांतिक रूप से इन-प्लेस एल्गोरिदम का सावधानीपूर्वक निर्माण करना संभव है जो डेटा को संशोधित नहीं करता है (जब तक कि डेटा का उपयोग नहीं किया जा रहा हो), किंतु यह व्यवहार में संभवतः ही कभी किया जाता है। विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं देखें।

यह भी देखें

  • इन-प्लेस और नॉट-इन-प्लेस सॉर्टिंग एल्गोरिदम की तालिका

संदर्भ

  1. The bit space requirement of a pointer is O(log n), but pointer size can be considered a constant in most sorting applications.
  2. 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.
  3. 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