सभी निकटतम छोटे मान

कंप्यूटर विज्ञान में, सभी निकटतम छोटे मानों की समस्या निम्नलिखित कार्य है: संख्याओं के अनुक्रम में प्रत्येक स्थिति के लिए, पिछले पदों के बीच उस अंतिम स्थिति की खोज करें जिसमें छोटा मान होते है। इस समस्या को समानांतर और गैर-समानांतर एल्गोरिदम दोनों Berkman, Schieber & Vishkin (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.

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

अनुप्रयोग

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

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

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

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

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

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

नेस्टेड लूप संरचना होने के अतिरिक्त, इस एल्गोरिदम का चलने का समय रैखिक है, क्योंकि आंतरिक लूप का प्रत्येक पुनरावृत्ति आइटम को हटा देता है जिसे बाहरी लूप के पिछले पुनरावृत्ति में जोड़ा गया था। यह स्टैक-सॉर्टेबल क्रमपरिवर्तन (इनपुट के लिए जिन्हें इस तरह से सॉर्ट किया जा सकता है) के लिए डोनाल्ड नुथ के एल्गोरिदम से निकटता से संबंधित है। एक और भी सरल रैखिक-समय अनुक्रमिक एल्गोरिदम (Barbay, Fischer & Navarro (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

समानांतर एल्गोरिदम

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

संदर्भ

• Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012), "LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations", Theoretical Computer Science, 459: 26–41, arXiv:1009.5863, doi:10.1016/j.tcs.2012.08.010.
• Berkman, Omer; Matias, Yossi; Ragde, Prabhakar (1998), "Triply-logarithmic parallel upper and lower bounds for minimum and range minima over small domains", Journal of Algorithms, 28 (2): 197–215, doi:10.1006/jagm.1997.0905.
• Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values", Journal of Algorithms, 14 (3): 344–370, doi:10.1006/jagm.1993.1018.
• Bern, Marshall; Eppstein, David; Teng, Shang-Hua (1999), "Parallel construction of quadtrees and quality triangulations" (PDF), International Journal of Computational Geometry & Applications, World Scientific Publishing Company, 9 (6): 517–532, doi:10.1142/S0218195999000303.
• Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), "Scaling and related techniques for geometry problems", STOC '84: Proc. 16th ACM Symp. Theory of Computing, New York, NY, USA: ACM, pp. 135–143, doi:10.1145/800057.808675, ISBN 0-89791-133-4.
• He, Xin; Huang, Chun-Hsi (2001), "Communication efficient BSP algorithm for all nearest smaller values", Journal of Parallel and Distributed Computing, 61 (10): 1425–1438, doi:10.1006/jpdc.2001.1741.
• Kravets, D.; Plaxton, C. G. (1996), "All nearest smaller values on the hypercube", IEEE Trans. Parallel and Distributed Systems, 7 (5): 456–462, doi:10.1109/71.503770.
• Vuillemin, Jean (1980), "A unifying look at data structures", Commun. ACM, New York, NY, USA: ACM, 23 (4): 229–239, doi:10.1145/358841.358852.