युवा बाइनरी टेबल्स

तो, जैसा कि वादा किया गया था , जंग तालिकाओं के विषय की निरंतरता। आपको याद दिला दूं कि यंग टेबल एक संख्यात्मक मैट्रिक्स को संदर्भित करता है जिसमें कुछ विशेष गुण होते हैं। एक मैट्रिक्स एक दो आयामी सरणी है। और यहां एक स्वाभाविक सवाल उठना चाहिए - क्यों, वास्तव में, सरणी को दो-आयामी होना चाहिए? लेकिन क्या होगा अगर हम एक ही सिद्धांत पर तीन या चार आयामों की एक तालिका को लागू करने की कोशिश करते हैं , और निश्चित रूप से, पांच सितारे ! आप इस बारे में पढ़ सकते हैं कि यह सामान्यीकरण हमें कटौती के तहत कहां ले जाएगा ...

वन-डायमेंशनल यंग टेबल्स

यंग टेबल के आयाम को अनंत तक ले जाने से पहले, आइए देखें कि हमारे पीछे क्या है। दो से कम केवल एक है (शून्य की गिनती नहीं, लेकिन शून्य आयाम की एक युवा तालिका शून्य स्थान की तरह कुछ है - कोई नहीं जानता कि यह क्या है, लेकिन यह सुंदर लगता है)।
तो, एक आयामी युवा तालिका - यह क्या है? पिछले विषय में दी गई परिभाषा के बाद, यह केवल एक-आयामी सरणी है जो अवरोही क्रम में क्रमबद्ध है, जिनमें से सभी गैर-रिक्त कोशिकाएं इसकी शुरुआत में स्थित हैं।

इस मामले में तत्वों के चढ़ाई और वंश (यंग टेबल पर बुनियादी संचालन) को टेबल के दाएं से बाएं (वृद्धि) या बाएं से दाएं (वंश) के रैखिक देखने के लिए कम किया जाता है:

def MoveUp(X, i): while i>0 and X[i]>X[i-1]: X[i], X[i-1] = X[i-1], X[i] i -= 1 def MoveDown(X, n): i = 0 while i+1<n and X[i]a>X[i+1]: X[i], X[i-1] = X[i-1], X[i] i += 1 

छँटाई एल्गोरिथ्म ही व्यावहारिक रूप से यहाँ वर्णित एक से अलग नहीं है ।

 def YoungSort(X, n): for i in range(1,n): MoveUp(X,i) for i in range(1,n): X[0], X[ni] = X[ni], X[0] MoveDown(X,ni) 

एक चौकस पाठक यह नोटिस करेगा कि इस तरह का पहला चक्र एक मानक सम्मिलित प्रकार से अधिक कुछ नहीं है। सच है, परिणाम अवरोही क्रम में एक अनुक्रम है। इसलिए, दूसरा चक्र इस क्रम का एक चालाक उल्टा उपचार करता है। यह स्पष्ट है कि इस उपचार को और अधिक कुशलता से किया जा सकता है, लेकिन अब हमारा लक्ष्य युवा तालिका की अवधारणा को मनमाने आयाम के मामले में सामान्य बनाने की कोशिश करना है, इसलिए एक विशिष्ट मामले का अनुकूलन (और यहां तक ​​कि इस तरह के एक साधारण) का कोई मतलब नहीं है।

सामान्यीकृत युवा टेबल्स

हम एक सामान्यीकृत यंग टेबल की परिभाषा के लिए निम्नलिखित लेते हैं: एक यंग टेबल एक आंशिक रूप से ऑर्डर किया गया लगभग भरा हुआ आयाम की संख्या d है।
आंशिक आदेश देने और लगभग पूर्णता के गुणों का निर्धारण करने के लिए, हम एक सरणी के सेल (तत्व) के शीर्ष पड़ोसी की अवधारणा को पेश करते हैं। चलो कुछ सरणी कोशिकाओं को सूचकांकों i ₁ , i ₂ , ..., i _d द्वारा विशेषता दी जाती है। फिर, किसी दिए गए सेल का शीर्ष पड़ोसी कोई भी सेल है जिसके सभी सूचकांकों, एक के अपवाद के साथ, इस सेल के सूचकांकों के बराबर हैं, और शेष इंडेक्स दिए गए सेल के संबंधित सूचकांक से बिल्कुल कम है। उदाहरण के लिए, सूचकांक वाले सेल [1,0,5,3] के तीन ऊपरी पड़ोसी हैं: [0,0,5,3], [1,0,4,3] और [1,0,5,2]। इस प्रकार, यदि किसी सेल के सभी सूचकांक नोज़ेरो हैं, तो उसके बिल्कुल ऊपरी पड़ोसी हैं, और यदि सभी सूचकांक शून्य हैं, तो ऊपर से कोई पड़ोसी नहीं हैं - हम ऐसे तत्व को यंग टेबल के ऊपर कहते हैं।
फिर, आंशिक आदेश का मतलब है कि युवा तालिका के किसी भी तत्व का मूल्य इस तालिका में उसके सभी ऊपरी पड़ोसियों के मूल्यों से अधिक नहीं है।
लगभग भरे हुए का मतलब है कि अगर यंग टेबल की कुछ सेल भरी हुई है (यानी कुछ मूल्य शामिल हैं), तो इसके सभी ऊपरी पड़ोसी भी भरे हुए हैं।
यह दिखाना आसान है कि प्रत्येक आयाम के साथ (जब एक को छोड़कर सभी सूचकांक निश्चित होते हैं), यंग टेबल की कोशिकाओं के मान एक गैर-बढ़ते अनुक्रम बनाते हैं। नतीजतन, तालिका का सबसे बड़ा तत्व हमेशा अपने शीर्ष पर स्थित होता है।
दुर्भाग्य से, पहले से ही तीन-आयामी युवा तालिकाओं का दृश्य काफी कठिनाइयों से भरा हुआ है, इसलिए पाठक को अपनी बहुआयामी कल्पना को शामिल करने के लिए आमंत्रित किया जाता है, जिससे उसे (कल्पना), यदि आवश्यक हो तो साधारण दो-आयामी युवा तालिकाओं के चित्रों के साथ मदद मिलती है।
चढ़ाई और वंश के संचालन को एक स्पष्ट तरीके से सामान्यीकृत किया जाता है। जब एक निश्चित तत्व बढ़ जाता है, तो उसके सभी पड़ोसी ऊपर से चले जाते हैं, अगर कम मूल्यों वाले पड़ोसी पाए जाते हैं, तो सबसे छोटा जिसे चुना जाता है, वह वर्तमान के साथ स्थानों को बदलता है और नए वर्तमान तत्व के लिए प्रक्रिया जारी रहती है। यदि सभी ऊपरी पड़ोसियों के मूल्य वर्तमान से अधिक हैं, तो चढ़ाई खत्म हो गई है। तीन-आयामी युवा तालिका में एक तत्व को उठाने का एक उदाहरण चित्र में दिखाया गया है (केवल तालिका का एक टुकड़ा दिखाया गया है)।

वंश को समान रूप से निष्पादित किया जाता है, लेकिन नीचे से सभी पड़ोसियों को स्थानांतरित कर दिया जाता है (कोशिकाएं जिसके लिए वर्तमान एक ऊपरी पड़ोसी है) और उनमें से सबसे बड़ा चुना जाता है।
इन दो ऑपरेशनों का उपयोग करके, आप तालिका में एक नए तत्व की प्रविष्टि को लागू कर सकते हैं और तालिका से सबसे बड़े तत्व को हटा सकते हैं। और सम्मिलन और विलोपन की सहायता से, छँटाई बस कार्यान्वित की जाती है। सिद्धांत रूप में, एसेंट और डिसेंट का कार्यान्वयन, डी-डायमेंशनल टेबल के लिए भी विशेष कठिनाइयों का कारण नहीं होना चाहिए, लेकिन, फिर भी, हम पहले इन दो ऑपरेशनों की जटिलता का आकलन करने का प्रयास करेंगे।
हम मान लेंगे कि डी-डायमेंशनल यंग टेबल का प्रत्येक इंडेक्स 0 से एम -1 तक भिन्न होता है। चलो सबसे खराब स्थिति लेते हैं - तालिका अंत तक भरी हुई है (तत्वों की संख्या n = m ^d ), इसके अंतिम तत्व को उठाना आवश्यक है, जो (ऐसा हुआ) सबसे बड़ा है। यानी चढ़ाई के अंत में, यह तत्व तालिका के शीर्ष पर होना चाहिए। क्योंकि प्रत्येक पुनरावृत्ति पर उठाने की प्रक्रिया के दौरान, ठीक एक तत्व सूचकांक एक से घटता है, तो आपको डीएम सत्यापन के आदेश को पूरा करना होगा। प्रत्येक पुनरावृत्ति पर, एक विनिमय किया जाता है, और डी तुलना (पड़ोसियों को देखने पर) से अधिक नहीं। कुल, एक उठाने का संचालन (सबसे खराब स्थिति में) हमें ओ (डी ² मीटर) कार्यों का खर्च आएगा। इसका मतलब यह है कि इस तरह के संचालन में पहले से ही ओ (डी ² एमएन) कार्यों का खर्च आएगा। यह देखते हुए कि n = m ^d , हम एक d- आयामी युवा तालिका का उपयोग करके छँटाई की जटिलता का निम्नलिखित अनुमान प्राप्त करते हैं: O (d ² n ^{1 + 1 / d} )।
अच्छी खबर यह है कि d में वृद्धि के साथ, घातांक 1 + 1 / d कम हो जाता है: 2 (एक आयामी युवा तालिका), 1.5 (मानक युवा तालिका), 1.33, 1.25, 1.2, आदि, इस सभी लागत 1 की सीमा में, क्या हम वास्तव में पार कर सकते हैं त्वरित छँटाई! अब बुरी खबर यह है कि बढ़ते d के साथ, इस डिग्री के सामने गुणांक भी बढ़ जाता है। यह दिखाने के लिए आसान है (व्युत्पन्न का उपयोग करके) कि इष्टतम विकल्प ₂ डी एन लॉग के बराबर पैरामीटर डी है। हम इस मान को सूत्र O (d ² n ^{1 + 1 / d} ) में प्रतिस्थापित करते हैं और सरल परिवर्तनों के बाद हमें अंतिम अनुमान O (nlog ² n) मिलता है - यही है, क्रांति रद्द हो गई है, क्योंकि परिणामी अनुमान विषम रूप से थोड़ा सा है, लेकिन इष्टतम रैखिक-भौगोलिक से भी बदतर ...

युवा बाइनरी टेबल्स

यद्यपि हमने दिखाया है कि सबसे अच्छे मामले में भी, यंग टेबल का उपयोग करके छांटना असममित इष्टतमता तक नहीं पहुंचता है, फिर भी हम ऐसी तालिकाओं के सर्वश्रेष्ठ को लागू करने का प्रयास करेंगे, अर्थात। आयाम की एक तालिका d = log ₂ n, जिसे हम एक बाइनरी यंग टेबल कहेंगे। हालांकि इस तरह की तालिका का उपयोग प्रभावी छंटाई को व्यवस्थित करने के लिए नहीं किया जा सकता है, फिर भी, यह संभव है कि कोई व्यक्ति इसके लिए एक उपयोगी एप्लिकेशन ढूंढ सकेगा। और सब से ऊपर, एक बाइनरी यंग टेबल को लागू करना सिर्फ एक अच्छा प्रोग्रामिंग व्यायाम है।
पहले, आइए एक बाइनरी यंग टेबल की अवधारणा को औपचारिक रूप दें। हम आयाम d की एक बाइनरी यंग टेबल कहेंगे, जिसमें प्रत्येक सूचकांक केवल दो मान 0 और 1. ले सकता है। यदि हम ऐसी तालिका की क्षमता को n द्वारा निरूपित करते हैं, तो हमें वह n = 2 ^d या d = log ₂ n मिलता है। छोटे घ मानों के लिए ऐसी तालिकाओं के उदाहरण निम्नलिखित आकृति में दिखाए गए हैं। हाँ, समझदार पाठक कहेंगे, लेकिन ये आयाम d के हाइपरक्यूब हैं! और वह बिल्कुल सही होगा।

अब स्मृति में बहुआयामी सरणियों के मानक लेआउट का उपयोग करके इस तरह के हाइपरक्यूब को एक रैखिक सरणी में विस्तारित करें - सबसे कम सूचकांक सबसे तेज़ी से बदलता है। उदाहरण के लिए, पिछले आंकड़े से आयाम d = 3 की तालिका पर विचार करें।

हम जो देखते हैं - सूचकांक द्विआधारी संख्या प्रणाली में संख्याओं के रूप में व्याख्या की जाती है, 0, 1, 2, 3, आदि का क्रम बनाते हैं। यही है, हमें एक बाइनरी यंग टेबल में सेल के निर्देशांक को एक रेखीय तालिका में उसी सेल के निर्देशांक में परिवर्तित करने के लिए एक सरल एल्गोरिथ्म मिला। खैर, हम जानते हैं कि कैसे बिट्स के साथ काम करना है! ऐसा लगता है कि हम कर सकते हैं ...
यंग टेबल की प्रमुख अवधारणाएं ऊपरी और निचले सेल पड़ोसी हैं। बाइनरी यंग झांकी के संबंध में, इन अवधारणाओं को निम्नानुसार परिभाषित किया गया है: इंडेक्स i (एक रैखिक तालिका में) के साथ एक सेल को इंडेक्स j के साथ एक सेल के ऊपरी पड़ोसी कहा जाता है, अगर i का बिट प्रतिनिधित्व j के बिट प्रतिनिधित्व से मेल खाता है, तो बिल्कुल बिट के अलावा, जो j में है इकाई, और आई में - शून्य। तदनुसार, इस परिभाषा में सेल j, सेल i का निचला पड़ोसी होगा। उदाहरण के लिए, सेल नंबर 6 = 110 ₂ सेल नंबर 7 = 111 ₂ का ऊपरी पड़ोसी है, और सेल नंबर 2 का निचला पड़ोसी 2 = _{10 2 है} ।

तत्वों का उन्नयन और वंश

चढ़ाई और वंश के संचालन को ठीक उसी तरह से परिभाषित किया गया है जैसे वे सामान्यीकृत तालिकाओं के लिए ऊपर परिभाषित किए गए थे। द्विआधारी तालिकाओं के लिए इन कार्यों को लागू करने के लिए, ऊपरी और निचले पड़ोसियों के बस किए गए दृढ़ संकल्प के आधार पर, हमें एक पूर्णांक के सभी इकाई (ऊपर) या शून्य (नीचे) बिट्स की गणना के लिए एक प्रभावी एल्गोरिथ्म की आवश्यकता होती है। विशेष रूप से उन लोगों के लिए जो इस दिशा में सोचने के लिए बहुत आलसी हैं, हेनरी वॉरेन की एक अद्भुत पुस्तक है "प्रोग्रामर्स के लिए एल्गोरिदम ट्रिक्स", जहां हमारे हित करने वाले सूत्र हैं। इसलिए, संख्या x के सबसे दाहिने भाग को शून्य करने के लिए, ऑपरेशन x & (x-1) का उपयोग किया जाता है। अंतिम शून्य को एक से सही शून्य से बदलने के लिए, समान ऑपरेशन x | (x + 1) का उपयोग किया जाता है। ये ऑपरेशन (एक तंबू के साथ कुछ नृत्य) एक दिए गए पूर्णांक में सभी इकाइयों (शून्य) की गणना को व्यवस्थित करने के लिए पर्याप्त हैं।

कार्यान्वयन

निम्नलिखित वेक्टर एक्स द्वारा प्रस्तुत एक बाइनरी यंग टेबल के लिए तत्वों को ऊपर उठाने और कम करने के संचालन का कार्यान्वयन है।

 def MoveUp(X, i): while True: t = i j = i while j: #       i k = j-1 l = k&i if X[t]>X[l]: t = l #     j = k&j if i==t: return #   X[i], X[t] = X[t], X[i] #   i = t 

वंश के दौरान, पड़ोसी अपनी संख्या के आरोही क्रम में क्रमबद्ध होते हैं, इसलिए, पहले खाली पड़ोसी (तालिका आकार से बड़ी संख्या के साथ) का पता लगाने पर, खोज समाप्त हो जाती है।

 def MoveDown(X, n): i = 0 while True: t = i j = i while True: #      k = j+1 l = k|i if l>=n: break #     -  if X[t]<X[l]: t = l #     j = k|j if i==t: return #  X[i], X[t] = X[t], X[i] i = t 

पहले से ही मानक योजना के अनुसार छँटाई की जाती है।

 def YoungTableauSort(X, n): for i in range(1,n): #    MoveUp(X,i) for i in range(1,n): #   X[0], X[ni] = X[ni], X[0] MoveDown(X,ni) 

एक निष्कर्ष के बजाय

तो हमने क्या हासिल किया है? कोई कहेगा कि कुछ खास नहीं है, और अपने तरीके से सही होगा। सॉर्टिंग स्पष्ट रूप से इष्टतम तक नहीं पहुंचती है, खोना, उदाहरण के लिए, पिरामिडल छँटाई, समान सिद्धांतों पर व्यवस्थित। समान कारणों से, बाइनरी यंग तालिकाओं के आधार पर प्राथमिकता के साथ एडीटी कतार का कार्यान्वयन पिरामिडों का उपयोग करके समान कार्यान्वयन के लिए नीच है। इसके अलावा, मानक तालिकाओं से बाइनरी से मारे गए लोगों के लिए संक्रमण, शायद, पिरामिड पर युवा तालिकाओं का एकमात्र लाभ एक मनमाना तत्व की खोज है। आपको याद दिला दूं कि दो आयामी तालिकाओं में ऐसी खोज O (n ^1/2 ) समय में की जाती है, लेकिन बाइनरी तालिकाओं में, एक मनमाने मूल्य की खोज के लिए पूरी तालिका के लगभग पूर्ण गणना की आवश्यकता होगी, अर्थात। n समय में रैखिक। दूसरी ओर, जैसा कि वे कहते हैं, जो जोखिम नहीं उठाता है, वह शैंपेन नहीं पीता है। हमने एक नए सॉर्टिंग एल्गोरिदम के साथ आने की कोशिश की और हम सफल रहे। हाँ, और इस तरह के एक दुर्लभ प्रदर्शन के साथ हे (nlog ² n)! और फिर भी, लेखक को अभी भी एक उम्मीद है कि इस तरह के एक सुंदर डेटा संरचना में बस कुछ दिलचस्प और उपयोगी गुण होने चाहिए, जो कि कुछ पाठक संभवतः खोज सकते हैं। आपका ध्यान के लिए धन्यवाद!

संदर्भ:

1. कोरमन टी। एट अल। - एल्गोरिदम। निर्माण और विश्लेषण, 2009
2. फुल्टन डब्ल्यू - यंग टेबल्स, 2006
3. वारेन जी - प्रोग्रामर के लिए एल्गोरिथम ट्रिक्स, 2004

पुनश्च: वैसे, मैं पूरी तरह से इस विचार को स्वीकार करता हूं कि ऊपर वर्णित सब कुछ एक बार किसी के द्वारा खुले तौर पर खोला गया था। अगर किसी को इस तरह की जानकारी है तो मैं बहुत आभारी रहूंगा और वह इसे साझा करने के लिए तैयार है!