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

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

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

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

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

एस = नई खाली स्टैक डेटा संरचना
इनपुट अनुक्रम में x के लिए करें
    जबकि S शून्य नहीं है और S का शीर्ष तत्व x do से बड़ा या उसके बराबर है
        पॉप एस
    यदि S खाली है तो
        x का इससे पहले कोई छोटा मान नहीं है
    अन्य
        x का निकटतम छोटा मान S का शीर्ष तत्व है
    x को S पर दबाएँ

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

i के लिए 1 से n तक:
    जे = आई-1
    जबकि A[j] >= A[i]:
        जे = पी[जे]
    पी[आई] = जे

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

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