सभी निकटतम छोटे मान: Difference between revisions

From Vigyanwiki
(Created page with "कंप्यूटर विज्ञान में, सभी निकटतम छोटे मानों की समस्या निम्नलिखि...")
 
No edit summary
 
(15 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, सभी निकटतम छोटे मानों की समस्या निम्नलिखित कार्य है: संख्याओं के अनुक्रम में प्रत्येक स्थिति के लिए, पिछले पदों के बीच उस अंतिम स्थिति की खोज करें जिसमें छोटा मान हो। इस समस्या को समानांतर और गैर-समानांतर एल्गोरिदम दोनों द्वारा कुशलतापूर्वक हल किया जा सकता है: {{harvtxt|Berkman|Schieber|Vishkin|1993}}, जिन्होंने सबसे पहले प्रक्रिया को अन्य समानांतर कार्यक्रमों के लिए एक उपयोगी सबरूटीन के रूप में पहचाना, [[समानांतर रैंडम एक्सेस मशीन]] मॉडल में इसे हल करने के लिए कुशल [[समानांतर एल्गोरिदम]] विकसित किया; इसे [[स्टैक (डेटा संरचना)]]-आधारित एल्गोरिदम का उपयोग करके गैर-समानांतर कंप्यूटर पर [[रैखिक समय]] में भी हल किया जा सकता है। बाद में शोधकर्ताओं ने समानांतर गणना के अन्य मॉडलों में इसे हल करने के लिए एल्गोरिदम का अध्ययन किया है।
[[कंप्यूटर विज्ञान]] में, '''सभी निकटतम छोटे मानों''' की समस्या निम्नलिखित कार्य है: संख्याओं के अनुक्रम में प्रत्येक स्थिति के लिए, पिछले पदों के मध्य उस अंतिम स्थिति की खोज करें जिसमें छोटा मान होते है। इस समस्या को पैरेलल और गैर-पैरेलल एल्गोरिदम दोनों {{harvtxt|बर्कमैन|शिबर|विश्किन|1993}} द्वारा कुशलतापूर्वक हल किया जा सकता है, जिन्होंने सर्वप्रथम प्रक्रिया को अन्य पैरेलल कार्यो के लिए उपयोगी सबरूटीन के रूप में पहचाना है, [[समानांतर रैंडम एक्सेस मशीन|पैरेलल रैंडम एक्सेस मशीन]] मॉडल में इसे हल करने के लिए कुशल [[समानांतर एल्गोरिदम|पैरेलल एल्गोरिदम]] विकसित किया है; इसे [[स्टैक (डेटा संरचना)]]-आधारित एल्गोरिदम का उपयोग करके गैर-पैरेलल कंप्यूटर पर [[रैखिक समय|लीनियर टाइम]] में भी हल किया जा सकता है। इसके पश्चात् शोधकर्ताओं ने पैरेलल गणना के अन्य मॉडलों में इसे हल करने के लिए एल्गोरिदम का अध्ययन किया है।


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


मान लीजिए कि इनपुट बाइनरी [[वैन डेर कॉरपुट अनुक्रम]] है
मान लीजिए कि इनपुट बाइनरी [[वैन डेर कॉरपुट अनुक्रम]] है
:0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.
:0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.
अनुक्रम के पहले तत्व (0) का कोई पिछला मान नहीं है।
अनुक्रम के पहले तत्व (0) का कोई पिछला मान नहीं है। 8 और 4 से पहले का निकटतम (केवल) छोटा मान 0 है। 12 से पहले के सभी तीन मान छोटे हैं, किंतु निकटतम 4 है। इसी तरह जारी रखते हुए, इस अनुक्रम के लिए निकटतम पिछले छोटे मान (अस्तित्व का संकेत डैश द्वारा पिछले छोटे मान के) हैं
8 और 4 से पहले का निकटतम (केवल) छोटा मान 0 है। 12 से पहले के सभी तीन मान छोटे हैं, लेकिन निकटतम 4 है। इसी तरह जारी रखते हुए, इस अनुक्रम के लिए निकटतम पिछले छोटे मान (अस्तित्व का संकेत) एक डैश द्वारा पिछले छोटे मान के) हैं
:—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.
:—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.
अधिकांश अनुप्रयोगों में, निकटतम छोटे मानों की स्थिति की गणना की जानी चाहिए, न कि स्वयं मानों की, और कई अनुप्रयोगों में निम्नलिखित छोटे मान को खोजने के लिए अनुक्रम के उलट के लिए समान गणना की जानी चाहिए जो निकटतम है क्रम।
अधिकांश अनुप्रयोगों में, निकटतम छोटे मानों की स्थिति की गणना की जानी चाहिए, न कि स्वयं मानों की, और अनेक  अनुप्रयोगों में निम्नलिखित छोटे मान को खोजने के लिए अनुक्रम के उलट के लिए समान गणना की जानी चाहिए जो निकटतम क्रम है।


==अनुप्रयोग==
==अनुप्रयोग                                     ==


{{harvtxt|Berkman|Schieber|Vishkin|1993}} कई अन्य समस्याओं का उल्लेख करें जिन्हें निकटतम छोटे मानों की गणना का उपयोग करके समानांतर में कुशलतापूर्वक हल किया जा सकता है। उनमें से निम्नलिखित शामिल हैं:
{{harvtxt|बर्कमैन|शिबर|विश्किन|1993}} ने अनेक अन्य समस्याओं का उल्लेख करें जिन्हें निकटतम छोटे मानों की गणना का उपयोग करके पैरेलल में कुशलतापूर्वक हल किया जा सकता है। उनमें से निम्नलिखित सम्मिलित हैं:
* [[एल्गोरिदम मर्ज करें]], [[ मर्ज़ सॉर्ट ]] के मर्ज चरण की गणना। इन एल्गोरिदम के इनपुट में संख्याओं की दो क्रमबद्ध सरणियाँ शामिल हैं; वांछित आउटपुट एकल क्रमबद्ध सरणी में संख्याओं का समान सेट है। यदि कोई दो क्रमबद्ध सरणियों को जोड़ता है, पहला आरोही क्रम में और दूसरा अवरोही क्रम में, तो आउटपुट में प्रत्येक मान का पूर्ववर्ती या तो उसका निकटतम पिछला छोटा मान या उसका निकटतम अगला छोटा मान होता है (दोनों में से जो भी बड़ा हो) , और क्रमबद्ध आउटपुट सरणी में प्रत्येक मान की स्थिति की गणना इन दो निकटतम छोटे मानों की स्थिति से आसानी से की जा सकती है।
* [[एल्गोरिदम मर्ज करें|मर्ज एल्गोरिदम]] एक [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]] के मर्ज चरण की गणना करते है। इन एल्गोरिदम के इनपुट में संख्याओं की दो क्रमबद्ध सरणियाँ सम्मिलित हैं; वांछित आउटपुट एकल क्रमबद्ध सरणी में संख्याओं का समान सेट है। यदि कोई दो क्रमबद्ध सरणियों को जोड़ता है, पहला आरोही क्रम में और दूसरा अवरोही क्रम में, तो आउटपुट में प्रत्येक मान का पूर्ववर्ती या तो उसका निकटतम पिछला छोटा मान या उसका निकटतम अगला छोटा मान होता है (दोनों में से जो भी बड़ा हो) , और क्रमबद्ध आउटपुट सरणी में प्रत्येक मान की स्थिति की गणना इन दो निकटतम छोटे मानों की स्थिति से आसानी से की जा सकती है।
* [[कार्तीय वृक्ष]]ों का निर्माण। कार्टेशियन वृक्ष एक [[डेटा संरचना]] है जिसे प्रस्तुत किया गया है {{harvtxt|Vuillemin|1980}} और आगे अध्ययन किया गया {{harvtxt|Gabow|Bentley|Tarjan|1984}} श्रेणी खोज अनुप्रयोगों के लिए। बाइनरी खोज के लिए ट्रैप और यादृच्छिक [[ द्विआधारी खोज ]] [[फँसाना]] डेटा संरचनाओं की परिभाषा में कार्टेशियन पेड़ भी उत्पन्न होते हैं। मानों के अनुक्रम के कार्टेशियन वृक्ष में प्रत्येक मान के लिए एक नोड होता है। वृक्ष की जड़ अनुक्रम का न्यूनतम मान है; प्रत्येक दूसरे नोड के लिए, नोड का पैरेंट या तो उसका निकटतम पिछला छोटा मान है या उसका निकटतम अगला छोटा मान है (दोनों में से जो भी मौजूद है और बड़ा है)। इस प्रकार, कार्टेशियन पेड़ों का निर्माण सभी निकटतम छोटे मान एल्गोरिदम के आधार पर रैखिक समय में किया जा सकता है।
* [[कार्तीय वृक्ष|कार्टेशियन ट्री]] का निर्माण। कार्टेशियन ट्री [[डेटा संरचना]] है जिसे {{harvtxt|वुइलेमिन|1980}} द्वारा प्रस्तुत किया गया है और श्रेणी खोज अनुप्रयोगों के लिए {{harvtxt|गैबो|बेंटले|टारजन|1984}} द्वारा आगे अध्ययन किया गया था। बाइनरी खोज के लिए ट्रैप और यादृच्छिक [[ द्विआधारी खोज |बाइनरी सर्च]] [[फँसाना|ट्री]] डेटा संरचनाओं की परिभाषा में कार्टेशियन ट्री भी उत्पन्न होते हैं। मानों के अनुक्रम के कार्टेशियन ट्री में प्रत्येक मान के लिए नोड होता है। ट्री की जड़ अनुक्रम का न्यूनतम मान है; प्रत्येक दूसरे नोड के लिए, नोड का पैरेंट या तो उसका निकटतम पिछला छोटा मान है या उसका निकटतम अगला छोटा मान है (दोनों में से जो भी उपस्थित है और बड़ा है)। इस प्रकार, कार्टेशियन ट्री का निर्माण सभी निकटतम छोटे मान एल्गोरिदम के आधार पर लीनियर टाइम में किया जा सकता है।
* मिलान कोष्ठक. यदि प्रत्येक कोष्ठक की नेस्टिंग गहराई के साथ खुले और बंद कोष्ठक वर्णों का अनुक्रम इनपुट के रूप में दिया गया है, तो प्रत्येक खुले कोष्ठक का मिलान अगला करीबी कोष्ठक है जिसमें कोई बड़ी नेस्टिंग गहराई नहीं है, इसलिए इसे सभी निकटतम द्वारा पाया जा सकता है छोटे मानों की गणना जो करीबी कोष्ठकों के पक्ष में संबंधों को तोड़ देती है। यदि घोंसले की गहराई नहीं दी गई है, तो उनकी गणना [[उपसर्ग योग]] गणना का उपयोग करके की जा सकती है।
* मिलान कोष्ठक. यदि प्रत्येक कोष्ठक की नेस्टिंग गहराई के साथ खुले और संवर्त कोष्ठक वर्णों का अनुक्रम इनपुट के रूप में दिया गया है, तो प्रत्येक खुले कोष्ठक का मिलान अगला निकटतम कोष्ठक है जिसमें कोई बड़ी नेस्टिंग गहराई नहीं है, इसलिए इसे सभी निकटतम द्वारा पाया जा सकता है छोटे मानों की गणना जो निकटतम कोष्ठकों के पक्ष में संबंधों को तोड़ देती है। यदि नेस्टिंग गहराई नहीं दी गई है, तो उनकी गणना [[उपसर्ग योग]] गणना का उपयोग करके की जा सकती है।
इसी तरह की तकनीकों को [[बहुभुज त्रिभुज]], उत्तल पतवार निर्माण (अनुक्रमिक [[ग्राहम स्कैन]] उत्तल पतवार एल्गोरिथ्म को समानांतर करना), दो पेड़ों के ट्रैवर्सल ऑर्डर से पेड़ों का पुनर्निर्माण और क्वाडट्री निर्माण की समस्याओं पर भी लागू किया जा सकता है।<ref>{{harvtxt|Bern|Eppstein|Teng|1999}}.</ref>
इसी तरह की विधियों को [[बहुभुज त्रिभुज]], उत्तल पतवार निर्माण (अनुक्रमिक [[ग्राहम स्कैन]] उत्तल पतवार एल्गोरिथ्म को पैरेलल करना), दो ट्री के ट्रैवर्सल ऑर्डर से ट्री का पुनर्निर्माण और क्वाडट्री निर्माण की समस्याओं पर भी क्रियान्वित किया जा सकता है।<ref>{{harvtxt|Bern|Eppstein|Teng|1999}}.</ref>
==अनुक्रमिक एल्गोरिथ्म                                                    ==


 
अनुक्रमिक कंप्यूटर पर, सभी निकटतम छोटे मान स्टैक (डेटा संरचना) का उपयोग करके पाए जा सकते हैं: कोई मानों को अनुक्रम क्रम में संसाधित करता है, स्टैक का उपयोग उन मानों के अनुवर्ती को बनाए रखने के लिए करता है जो अब तक संसाधित किए गए हैं और किसी से भी छोटे हैं बाद का मूल्य जो पहले ही संसाधित हो चुका है। [[ छद्मकोड |स्यूडोकोड]] में, एल्गोरिथ्म इस प्रकार है।<syntaxhighlight>
==अनुक्रमिक एल्गोरिथ्म==
S = new empty stack data structure
 
for x in the input sequence do
अनुक्रमिक कंप्यूटर पर, सभी निकटतम छोटे मान एक स्टैक (डेटा संरचना) का उपयोग करके पाए जा सकते हैं: कोई मानों को अनुक्रम क्रम में संसाधित करता है, स्टैक का उपयोग उन मानों के अनुवर्ती को बनाए रखने के लिए करता है जो अब तक संसाधित किए गए हैं और किसी से भी छोटे हैं बाद का मूल्य जो पहले ही संसाधित हो चुका है। [[ छद्मकोड ]] में, एल्गोरिथ्म इस प्रकार है।
    while S is nonempty and the top element of S is greater than or equal to x do
एस = नई खाली स्टैक डेटा संरचना
        pop S
इनपुट अनुक्रम में x के लिए करें
    if S is empty then
    जबकि S शून्य नहीं है और S का शीर्ष तत्व x do से बड़ा या उसके बराबर है
        x has no preceding smaller value
        पॉप एस
    else
    यदि S खाली है तो
        the nearest smaller value to x is the top element of S
        x का इससे पहले कोई छोटा मान नहीं है
    push x onto S
    अन्य
</syntaxhighlight>नेस्टेड लूप संरचना होने के अतिरिक्त, इस एल्गोरिदम का चलने का समय रैखिक है, क्योंकि आंतरिक लूप का प्रत्येक पुनरावृत्ति आइटम को हटा देता है जिसे बाहरी लूप के पिछले पुनरावृत्ति में जोड़ा गया था। यह [[स्टैक-सॉर्टेबल क्रमपरिवर्तन]] (इनपुट के लिए जिन्हें इस तरह से सॉर्ट किया जा सकता है) के लिए [[डोनाल्ड नुथ]] के एल्गोरिदम से निकटता से संबंधित है।<ref>{{citation
        x का निकटतम छोटा मान S का शीर्ष तत्व है
    x को S पर दबाएँ
 
नेस्टेड लूप संरचना होने के बावजूद, इस एल्गोरिदम का चलने का समय रैखिक है, क्योंकि आंतरिक लूप का प्रत्येक पुनरावृत्ति एक आइटम को हटा देता है जिसे बाहरी लूप के पिछले पुनरावृत्ति में जोड़ा गया था। यह [[स्टैक-सॉर्टेबल क्रमपरिवर्तन]] (इनपुट के लिए जिन्हें इस तरह से सॉर्ट किया जा सकता है) के लिए [[डोनाल्ड नुथ]] के एल्गोरिदम से निकटता से संबंधित है।<ref>{{citation
  | last = Knuth | first = Donald | author-link = Donald Knuth
  | last = Knuth | first = Donald | author-link = Donald Knuth
  | location = Reading, Mass.
  | location = Reading, Mass.
Line 38: Line 34:
  | title = [[The Art of Computer Programming]]
  | title = [[The Art of Computer Programming]]
  | contribution = Vol. 1: Fundamental Algorithms
  | contribution = Vol. 1: Fundamental Algorithms
  | year = 1968}}.</ref>
  | year = 1968}}.</ref>  
एक और भी सरल रैखिक-समय अनुक्रमिक एल्गोरिदम ({{harvtxt|Barbay|Fischer|Navarro|2012}}, लेम्मा 1) को स्टैक की भी आवश्यकता नहीं है; यह मानता है कि इनपुट अनुक्रम एक सरणी के रूप में दिया गया है <code>A[1,n]</code> आकार का <code>n</code>, और सूचकांक को संग्रहीत करता है <code>j</code> के पूर्ववर्ती छोटे मूल्य का <code>i</code><sup>वें</sup>मूल्य <code>A[i]</code> में <code>P[i]</code>. हम एक कृत्रिम समग्र न्यूनतम मान लेते हैं <code>A[0]</code>:


i के लिए 1 से n तक:
एक और भी सरल रैखिक-समय अनुक्रमिक एल्गोरिदम ({{harvtxt|बार्बे|फिशर|नवारो|2012}}, लेम्मा 1) को स्टैक की भी आवश्यकता नहीं है; यह मानता है कि इनपुट अनुक्रम आकार के <code>n</code> सरणी के रूप में दिया गया है और <code>i</code><sup>वें</sup> मूल्य <code>A[i]</code> के पूर्ववर्ती छोटे मूल्य के सूचकांक <code>j</code> को <code>P[i]</code> में संग्रहीत करता है। हम <code>A[0]</code> कृत्रिम समग्र न्यूनतम मान लेते हैं:<syntaxhighlight>
    जे = आई-1
for i from 1 to n:                                                                                    
    जबकि A[j] >= A[i]:
    j = i-1                                                                                                    
        जे = पी[जे]
    while A[j] >= A[i]:                                                                                                                                                                                                                                                      
    पी[आई] = जे
        j = P[j]                                                                                                              
    P[i] = j                                                                                               
</syntaxhighlight>


==समानांतर एल्गोरिदम==
==पैरेलल एल्गोरिदम                                             ==


{{harvtxt|Berkman|Schieber|Vishkin|1993}} ने दिखाया कि समवर्ती-पढ़ें समवर्ती-लेखन समानांतर रैंडम एक्सेस मशीन पर सभी निकटतम छोटे मानों की समस्या को कुशलतापूर्वक कैसे हल किया जाए। [[सरणी डेटा संरचना]] के रूप में संग्रहीत n मानों के अनुक्रम के लिए, वे दिखाते हैं कि समस्या को कुल कार्य की एक रैखिक मात्रा का उपयोग करके समय O (लॉग लॉग n) में हल किया जा सकता है। उन अनुक्रमों के लिए जहां अंतराल [1,s] में सभी मान पूर्णांक हैं, {{harvtxt|Berkman|Matias|Ragde|1998}} ने इसे O(लॉग लॉग लॉग एस) में सुधार दिया; उन्होंने यह भी दिखाया कि, s के पर्याप्त बड़े मूल्यों के लिए, पिछली दोगुनी लघुगणकीय समय सीमा सबसे अच्छी है जिसे समस्या के लिए प्राप्त किया जा सकता है। इस कार्य के बाद से, सभी निकटतम छोटे मानों की समस्या के लिए समानांतर एल्गोरिदम को समानांतर गणना के अन्य मॉडलों पर भी विकसित किया गया है, जिसमें [[हाइपरक्यूब ग्राफ]]-संरचित संचार नेटवर्क वाले समानांतर कंप्यूटर भी शामिल हैं,<ref>{{harvtxt|Kravets|Plaxton|1996}}.</ref> और बल्क सिंक्रोनस समानांतर मॉडल।<ref>{{harvtxt|He|Huang|2001}}.</ref>
{{harvtxt|बर्कमैन|शिबर|विश्किन|1993}} ने दिखाया कि समवर्ती-पढ़ें समवर्ती-लेखन पैरेलल रैंडम एक्सेस मशीन पर सभी निकटतम छोटे मानों की समस्या को कुशलतापूर्वक कैसे हल किया जाए। [[सरणी डेटा संरचना]] के रूप में संग्रहीत n मानों के अनुक्रम के लिए, वे दिखाते हैं कि समस्या को कुल कार्य की रैखिक मात्रा का उपयोग करके समय O (लॉग लॉग ''n'') में हल किया जा सकता है। उन अनुक्रमों के लिए जहां अंतराल [1,s] में सभी मान पूर्णांक हैं, {{harvtxt|बर्कमैन|मटियास|रगड़े|1998}} ने इसे O (लॉग लॉग लॉग ''s'') में सुधार दिया; उन्होंने यह भी दिखाया कि, s के पर्याप्त बड़े मूल्यों के लिए, पिछली दोगुनी लघुगणकीय समय सीमा सबसे अच्छी है जिसे समस्या के लिए प्राप्त किया जा सकता है। इस कार्य के पश्चात, सभी निकटतम छोटे मानों की समस्या के लिए पैरेलल एल्गोरिदम को पैरेलल गणना के अन्य मॉडलों पर भी विकसित किया गया है, जिसमें [[हाइपरक्यूब ग्राफ]]-संरचित संचार नेटवर्क वाले पैरेलल कंप्यूटर,<ref>{{harvtxt|Kravets|Plaxton|1996}}.</ref> और बल्क सिंक्रोनस पैरेलल मॉडल भी सम्मिलित हैं।<ref>{{harvtxt|He|Huang|2001}}.</ref>
 
==टिप्पणियाँ           ==
 
==टिप्पणियाँ==


{{reflist}}
{{reflist}}
==संदर्भ==
==संदर्भ==


Line 101: Line 94:
  | year = 1980| doi-access = free
  | year = 1980| doi-access = free
  }}.
  }}.
[[Category: स्यूडोकोड उदाहरण सहित लेख]] [[Category: समानांतर कंप्यूटिंग]] [[Category: एल्गोरिदम खोजें]]


[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Templates Vigyan Ready]]
[[Category:एल्गोरिदम खोजें]]
[[Category:समानांतर कंप्यूटिंग]]
[[Category:स्यूडोकोड उदाहरण सहित लेख]]

Latest revision as of 13:14, 4 August 2023

कंप्यूटर विज्ञान में, सभी निकटतम छोटे मानों की समस्या निम्नलिखित कार्य है: संख्याओं के अनुक्रम में प्रत्येक स्थिति के लिए, पिछले पदों के मध्य उस अंतिम स्थिति की खोज करें जिसमें छोटा मान होते है। इस समस्या को पैरेलल और गैर-पैरेलल एल्गोरिदम दोनों बर्कमैन, शिबर & विश्किन (1993) द्वारा कुशलतापूर्वक हल किया जा सकता है, जिन्होंने सर्वप्रथम प्रक्रिया को अन्य पैरेलल कार्यो के लिए उपयोगी सबरूटीन के रूप में पहचाना है, पैरेलल रैंडम एक्सेस मशीन मॉडल में इसे हल करने के लिए कुशल पैरेलल एल्गोरिदम विकसित किया है; इसे स्टैक (डेटा संरचना)-आधारित एल्गोरिदम का उपयोग करके गैर-पैरेलल कंप्यूटर पर लीनियर टाइम में भी हल किया जा सकता है। इसके पश्चात् शोधकर्ताओं ने पैरेलल गणना के अन्य मॉडलों में इसे हल करने के लिए एल्गोरिदम का अध्ययन किया है।

उदाहरण

मान लीजिए कि इनपुट बाइनरी वैन डेर कॉरपुट अनुक्रम है

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

अनुक्रम के पहले तत्व (0) का कोई पिछला मान नहीं है। 8 और 4 से पहले का निकटतम (केवल) छोटा मान 0 है। 12 से पहले के सभी तीन मान छोटे हैं, किंतु निकटतम 4 है। इसी तरह जारी रखते हुए, इस अनुक्रम के लिए निकटतम पिछले छोटे मान (अस्तित्व का संकेत डैश द्वारा पिछले छोटे मान के) हैं

—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.

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

अनुप्रयोग

बर्कमैन, शिबर & विश्किन (1993) ने अनेक अन्य समस्याओं का उल्लेख करें जिन्हें निकटतम छोटे मानों की गणना का उपयोग करके पैरेलल में कुशलतापूर्वक हल किया जा सकता है। उनमें से निम्नलिखित सम्मिलित हैं:

  • मर्ज एल्गोरिदम एक मर्ज़ सॉर्ट के मर्ज चरण की गणना करते है। इन एल्गोरिदम के इनपुट में संख्याओं की दो क्रमबद्ध सरणियाँ सम्मिलित हैं; वांछित आउटपुट एकल क्रमबद्ध सरणी में संख्याओं का समान सेट है। यदि कोई दो क्रमबद्ध सरणियों को जोड़ता है, पहला आरोही क्रम में और दूसरा अवरोही क्रम में, तो आउटपुट में प्रत्येक मान का पूर्ववर्ती या तो उसका निकटतम पिछला छोटा मान या उसका निकटतम अगला छोटा मान होता है (दोनों में से जो भी बड़ा हो) , और क्रमबद्ध आउटपुट सरणी में प्रत्येक मान की स्थिति की गणना इन दो निकटतम छोटे मानों की स्थिति से आसानी से की जा सकती है।
  • कार्टेशियन ट्री का निर्माण। कार्टेशियन ट्री डेटा संरचना है जिसे वुइलेमिन (1980) द्वारा प्रस्तुत किया गया है और श्रेणी खोज अनुप्रयोगों के लिए गैबो, बेंटले & टारजन (1984) द्वारा आगे अध्ययन किया गया था। बाइनरी खोज के लिए ट्रैप और यादृच्छिक बाइनरी सर्च ट्री डेटा संरचनाओं की परिभाषा में कार्टेशियन ट्री भी उत्पन्न होते हैं। मानों के अनुक्रम के कार्टेशियन ट्री में प्रत्येक मान के लिए नोड होता है। ट्री की जड़ अनुक्रम का न्यूनतम मान है; प्रत्येक दूसरे नोड के लिए, नोड का पैरेंट या तो उसका निकटतम पिछला छोटा मान है या उसका निकटतम अगला छोटा मान है (दोनों में से जो भी उपस्थित है और बड़ा है)। इस प्रकार, कार्टेशियन ट्री का निर्माण सभी निकटतम छोटे मान एल्गोरिदम के आधार पर लीनियर टाइम में किया जा सकता है।
  • मिलान कोष्ठक. यदि प्रत्येक कोष्ठक की नेस्टिंग गहराई के साथ खुले और संवर्त कोष्ठक वर्णों का अनुक्रम इनपुट के रूप में दिया गया है, तो प्रत्येक खुले कोष्ठक का मिलान अगला निकटतम कोष्ठक है जिसमें कोई बड़ी नेस्टिंग गहराई नहीं है, इसलिए इसे सभी निकटतम द्वारा पाया जा सकता है छोटे मानों की गणना जो निकटतम कोष्ठकों के पक्ष में संबंधों को तोड़ देती है। यदि नेस्टिंग गहराई नहीं दी गई है, तो उनकी गणना उपसर्ग योग गणना का उपयोग करके की जा सकती है।

इसी तरह की विधियों को बहुभुज त्रिभुज, उत्तल पतवार निर्माण (अनुक्रमिक ग्राहम स्कैन उत्तल पतवार एल्गोरिथ्म को पैरेलल करना), दो ट्री के ट्रैवर्सल ऑर्डर से ट्री का पुनर्निर्माण और क्वाडट्री निर्माण की समस्याओं पर भी क्रियान्वित किया जा सकता है।[1]

अनुक्रमिक एल्गोरिथ्म

अनुक्रमिक कंप्यूटर पर, सभी निकटतम छोटे मान स्टैक (डेटा संरचना) का उपयोग करके पाए जा सकते हैं: कोई मानों को अनुक्रम क्रम में संसाधित करता है, स्टैक का उपयोग उन मानों के अनुवर्ती को बनाए रखने के लिए करता है जो अब तक संसाधित किए गए हैं और किसी से भी छोटे हैं बाद का मूल्य जो पहले ही संसाधित हो चुका है। स्यूडोकोड में, एल्गोरिथ्म इस प्रकार है।

S = new empty stack data structure
for x in the input sequence do
    while S is nonempty and the top element of S is greater than or equal to x do
        pop S
    if S is empty then
        x has no preceding smaller value
    else
        the nearest smaller value to x is the top element of S
    push x onto S

नेस्टेड लूप संरचना होने के अतिरिक्त, इस एल्गोरिदम का चलने का समय रैखिक है, क्योंकि आंतरिक लूप का प्रत्येक पुनरावृत्ति आइटम को हटा देता है जिसे बाहरी लूप के पिछले पुनरावृत्ति में जोड़ा गया था। यह स्टैक-सॉर्टेबल क्रमपरिवर्तन (इनपुट के लिए जिन्हें इस तरह से सॉर्ट किया जा सकता है) के लिए डोनाल्ड नुथ के एल्गोरिदम से निकटता से संबंधित है।[2] एक और भी सरल रैखिक-समय अनुक्रमिक एल्गोरिदम (बार्बे, फिशर & नवारो (2012), लेम्मा 1) को स्टैक की भी आवश्यकता नहीं है; यह मानता है कि इनपुट अनुक्रम आकार के n सरणी के रूप में दिया गया है और iवें मूल्य A[i] के पूर्ववर्ती छोटे मूल्य के सूचकांक j को P[i] में संग्रहीत करता है। हम A[0] कृत्रिम समग्र न्यूनतम मान लेते हैं:

for i from 1 to n:                                                                                      
    j = i-1                                                                                                     
    while A[j] >= A[i]:                                                                                                                                                                                                                                                       
        j = P[j]                                                                                                               
    P[i] = j

पैरेलल एल्गोरिदम

बर्कमैन, शिबर & विश्किन (1993) ने दिखाया कि समवर्ती-पढ़ें समवर्ती-लेखन पैरेलल रैंडम एक्सेस मशीन पर सभी निकटतम छोटे मानों की समस्या को कुशलतापूर्वक कैसे हल किया जाए। सरणी डेटा संरचना के रूप में संग्रहीत n मानों के अनुक्रम के लिए, वे दिखाते हैं कि समस्या को कुल कार्य की रैखिक मात्रा का उपयोग करके समय O (लॉग लॉग n) में हल किया जा सकता है। उन अनुक्रमों के लिए जहां अंतराल [1,s] में सभी मान पूर्णांक हैं, बर्कमैन, मटियास & रगड़े (1998) ने इसे O (लॉग लॉग लॉग s) में सुधार दिया; उन्होंने यह भी दिखाया कि, s के पर्याप्त बड़े मूल्यों के लिए, पिछली दोगुनी लघुगणकीय समय सीमा सबसे अच्छी है जिसे समस्या के लिए प्राप्त किया जा सकता है। इस कार्य के पश्चात, सभी निकटतम छोटे मानों की समस्या के लिए पैरेलल एल्गोरिदम को पैरेलल गणना के अन्य मॉडलों पर भी विकसित किया गया है, जिसमें हाइपरक्यूब ग्राफ-संरचित संचार नेटवर्क वाले पैरेलल कंप्यूटर,[3] और बल्क सिंक्रोनस पैरेलल मॉडल भी सम्मिलित हैं।[4]

टिप्पणियाँ

  1. ↑ Bern, Eppstein & Teng (1999).
  2. ↑ Knuth, Donald (1968), "Vol. 1: Fundamental Algorithms", The Art of Computer Programming, Reading, Mass.: Addison-Wesley.
  3. ↑ Kravets & Plaxton (1996).
  4. ↑ He & Huang (2001).

संदर्भ

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सभी_निकटतम_छोटे_मान&oldid=236992’