खोज और छँटाई कार्यों में युवा टेबल

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

युवा तालिका अवधारणा

हम एक यंग टेबल को आंशिक रूप से ऑर्डर किए गए लगभग न्यूमेरिकल मैट्रिक्स कहते हैं। आंशिक आदेश का मतलब है कि इस तरह के मैट्रिक्स का प्रत्येक तत्व अपने ऊपरी और बाएं पड़ोसियों के मूल्यों से अधिक नहीं है (बशर्ते कि तत्व में ये पड़ोसी सामान्य हैं)। लगभग पूर्ण का अर्थ निम्न है: मैट्रिक्स की पहली j पंक्तियाँ (शून्य से (j-1) वें) पूरी तरह से तालिका में भरी हुई हैं, पहले l तत्व j-th पंक्ति में भरे गए हैं, शेष सभी पंक्तियाँ खाली हैं। एक युवा तालिका का एक उदाहरण निम्नलिखित आकृति में दिखाया गया है।

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

आइटम डालें और हटाएं

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

केवल इसके ऊपरी बाएं कोने में स्थित सबसे बड़ा तत्व यंग टेबल से हटा दिया जाएगा। सबसे पहले, हम इस सेल को टेबल के अंतिम कब्जे वाले सेल से x मान में स्थानांतरित करते हैं, जिसके बाद एलिमेंट डीसेंट ऑपरेशन लागू किया जाता है। इस ऑपरेशन को उठाने के लिए समान रूप से किया जाता है, लेकिन दूसरी तरफ (दाएं और नीचे), जब तक कि वर्तमान तत्व में कम और सही पड़ोसी नहीं होते हैं, या ये पड़ोसी (या केवल एक ही अगर कोई दूसरा नहीं है) x से कम या बराबर हैं। अंतिम आंकड़े से तालिका से सबसे बड़ी वस्तु को हटाने की प्रक्रिया नीचे दी गई है।

जाहिर है, ऊपर वर्णित सम्मिलन और विलोपन कार्यों के साथ यंग टेबल वास्तव में प्राथमिकता के साथ कतार एडीटी का कार्यान्वयन है। इस कार्यान्वयन की एक दिलचस्प विशेषता यह है कि सम्मिलन और हटाने का समय ओ (अधिकतम (आर, सी)) के क्रम का है, जहां आर और सी मैट्रिक्स के आयाम हैं। यदि हम r = c लगाते हैं, तो हम पाते हैं कि सम्मिलन समय O (n ^0.5 ) के क्रम का है, जहाँ n तालिका में तत्वों की संख्या है। हम नीचे मानते हैं कि n तत्वों को संग्रहीत करने के लिए, हम सबसे छोटे संभव आकार m = int (छत (sqrt (n))) के एक वर्ग तालिका का उपयोग करते हैं।

युवा तालिकाओं के साथ छंटनी

यह स्पष्ट है कि प्राथमिकता के साथ ADD कतार का कार्यान्वयन होने पर, आप किसी दिए गए संख्यात्मक अनुक्रम की छँटाई को व्यवस्थित कर सकते हैं। इस तरह की छँटाई की योजना तुच्छ है: सबसे पहले, उनके X के सभी तत्वों को कतार में लिखें, फिर कतार से सभी तत्वों को हटा दें और अंत से शुरू होकर X पर लिखें। e। दाएं से बाएं)। इस प्रकार, सबसे बड़ा तत्व एक्स के अंत में लिखा जाएगा, अगला सबसे बड़ा - एक्स के penultimate सेल के लिए, आदि। जाहिर है, कतार में तत्वों को डालने (हटाने) के समय इस तरह की छंटाई का समय एक्स में तत्वों की संख्या n के उत्पाद के बराबर होगा। यानी प्राथमिकता तालिका के रूप में यंग टेबल का उपयोग करते समय, छँटाई जटिलता ओ (एन ^1.5 ) होगी। इसका अर्थ है कि प्रस्तावित एल्गोरिथ्म asymptotically quadratic (सम्मिलन) और रैखिक-लॉगरिदमिक एल्गोरिदम (विलय) के बीच एक मध्यवर्ती स्थिति पर कब्जा कर लेता है और शेल प्रकार का एक करीबी पड़ोसी है।
वर्णित सामान्य छंटनी योजना मानती है कि कतार को संग्रहीत करने के लिए एक अलग डेटा संरचना का उपयोग किया जाता है, अर्थात। वॉल्यूम की अतिरिक्त मेमोरी n से कम नहीं। हालाँकि, पिरामिड के लिए, यंग की तालिकाओं को एक्स के अनुक्रम (सरणी) से परे जाने के बिना जगह में छांटना संभव है। ऐसा करने के लिए, ध्यान दें कि 1) हर बार जब कोई तत्व एक्स से बाहर निकाला जाता है, तो उसे तुरंत टेबल में डाला जाता है और इसके विपरीत ( यानी आवश्यक स्मृति की कुल मात्रा हर समय स्थिर रहती है और n के बराबर होती है); 2) मेट्रिक्स आमतौर पर कंप्यूटर मेमोरी लाइन में लाइन के रूप में संग्रहीत होते हैं, वास्तव में, एक-आयामी सरणी (या हम खुद इस तरह की भंडारण योजना को व्यवस्थित कर सकते हैं)। इन विचारों के आधार पर, हम निम्नलिखित सरल सॉर्टिंग एल्गोरिथ्म प्राप्त करते हैं, जो यंग टेबल में (MoveUp) और डिसेंट (MoveDown) तत्वों को बढ़ाने के लिए दो सहायक कार्यों का उपयोग करता है। समय के प्रत्येक क्षण में, एक्स के बाएं हिस्से में एक युवा तालिका होती है, दाहिने हिस्से में अनुक्रम एक्स होता है। पहले पास में, हम एक तत्व में एक तालिका के साथ शुरू करते हैं और धीरे-धीरे एक्स से तत्वों को जोड़ते हैं। दूसरे पास में, हम अनुक्रमिक रूप से तालिका से सबसे बड़े तत्व को निकालते हैं और इसे बदलते हैं। तालिका के अंतिम तत्व के साथ, तालिका के आकार को एक से कम करते हुए। यह इस तथ्य की ओर जाता है कि एक्स का पुनर्निर्माण किया गया क्रम आरोही क्रम में क्रमबद्ध है।

from math import * def YoungTableauSort(X, n): m = int(ceil(sqrt(n))) #   for i in range(1,n): #   MoveUp(X,i,m) for i in range(1,n): #   X[0], X[ni] = X[ni], X[0] MoveDown(X,ni,m) def MoveUp(X,i,m): while True: t = i if i%m and X[i-1]<X[t]: t = i-1 #    if i/m and X[im]<X[t]: t = im #    if i==t: return #    X[i], X[t] = X[t], X[i] i = t def MoveDown(X,k,m): # k -     i = 0 while True: t = i if i%m+1<m and i+1<k and X[i+1]>X[t]: t = i+1 #    if i/m+1<m and i+m<k and X[i+m]>X[t]: t = i+m #    if i==t: return #  X[i], X[t] = X[t], X[i] i = t 

कुल मिलाकर, हमारे पास एक इन-प्लेस सॉर्टिंग एल्गोरिदम है जो सबसे खराब स्थिति में ओ (एन ^1.5 ) समय के दौरान काम करता है।

युवा तालिका खोज

मान लीजिए कि हम एक यंग टेबल (एक-आयामी सरणी का प्रतिनिधित्व करते हैं, जैसा कि ऊपर किया गया था) को कंटेनर के रूप में उपयोग करना चाहते हैं। ऐसे कंटेनर किन कार्यों का समर्थन कर सकते हैं? सबसे पहले, एक नया तत्व डालें, और दूसरी बात, सबसे बड़े तत्व की खोज करें (विशेष रूप से, आपको खोज करने की आवश्यकता नहीं है, क्योंकि यह तत्व सबसे पहले है), सबसे बड़ा तत्व हटाएं, और इसे एक क्रम में परिवर्तित करें। उपरोक्त ऑपरेशन पिरामिड में भी अंतर्निहित हैं। पिरामिड के अलावा यंग की तालिका क्या सेट करती है, यह कुशलतापूर्वक वस्तुओं की खोज करने की क्षमता है। आप पिरामिड में सबसे बड़े तत्व के अलावा कुछ और पा सकते हैं, इसके सभी तत्वों की सबसे खराब खोज (सबसे खराब स्थिति में)। लेकिन यंग टेबल में, ओ (एन ^0.5 ) के आदेश के एक ही समय में किसी भी तत्व की खोज की जा सकती है। इस तरह की खोज के लिए एल्गोरिथ्म निम्नानुसार है। हम तालिका के ऊपरी दाएं कोने से तत्व x की खोज शुरू करते हैं (एक आयामी सरणी में यह संख्या एम -1 के साथ एक तत्व है)। यदि वर्तमान आइटम खोज के बराबर है, तो खोज पूरी हो गई है। यदि वर्तमान तत्व वांछित से कम है, तो आपको तालिका को एक कदम बाईं ओर स्थानांतरित करने की आवश्यकता है, क्योंकि नीचे दिए गए सभी तत्व एक्स की तुलना में जानबूझकर छोटे होंगे। यदि कहीं चलना नहीं है, तो खोज को असफल घोषित किया जाता है। यदि वर्तमान तत्व वांछित से बड़ा है, तो आपको एक सेल नीचे जाने की आवश्यकता है। यदि वर्तमान रेखा अंतिम है, तो एक बदलाव संभव नहीं है - खोज असफल है। यदि वर्तमान पंक्ति अंतिम नहीं है, लेकिन वर्तमान एक के नीचे कोई तत्व नहीं है, तो हमें फिर से बाईं ओर स्थानांतरित करना होगा (तालिका के बाएं किनारे तक पहुंचने के लिए एक चेक के साथ)। ऐसे फ़ंक्शन के लिए कोड नीचे दिया गया है।

 def Find(X,k,m,x): # k -     i = m-1 while True: if X[i]==x: return i #  if X[i]<x or i/m+1<m and i+m>=k: #    if i%m: i -= 1 else: return -1 else: #    if i/m<m-1 and i+m<k: i += m else: return -1 

यह सत्यापित करना आसान है कि खोज करते समय तालिका में देखी गई वस्तुओं की संख्या तालिका के आकार के दोगुने से अधिक नहीं होती है, अर्थात। फिर, यह O (n ^0.5 ) के आदेश की एक मात्रा है। एक युवा तालिका में नंबर 4 को खोजने का एक उदाहरण निम्नलिखित आंकड़े में दिखाया गया है।

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

युवा तालिकाओं पर उपरोक्त संचालन के लिए, कोई 1 जोड़ सकता है समय ओ (एन ^0.5 ) के साथ किसी भी तत्व के मूल्य में बदलाव; 2) समय ओ (एन ^0.5 ) में एक मनमाना तत्व को हटाने; 3) सबसे छोटे तत्व की खोज, जो आमतौर पर निरंतर समय में किया जाता है, क्योंकि सबसे छोटा तत्व, यंग टेबल की परिभाषा के आधार पर, या तो अंतिम गैर-रिक्त कक्ष में या अंतिम गैर-रिक्त पंक्ति के अंतिम कक्ष में स्थित है।
इस प्रकार, युवा तालिकाओं को द्विआधारी खोज पेड़ों के अपेक्षाकृत सरल एनालॉग के रूप में माना जा सकता है, फायदे: कार्यान्वयन में आसानी, डेटा भंडारण के लिए कम ओवरहेड; नुकसान: मूल संचालन का निष्पादन समय "लॉगरिदमिक" नहीं है, लेकिन "रूट-स्क्वायर", अतिप्रवाह की समस्या है - तालिका में जगह समाप्त होने के बाद, हम या तो एक नई पंक्ति जोड़ सकते हैं (पूर्ण पुनर्गठन किए बिना, लेकिन तालिका की कठोरता का उल्लंघन करते हैं, जिससे कमी हो सकती है। संचालन की दक्षता), या बड़े आकार के एक नए वर्ग तालिका में एक पूर्ण पुनर्गठन करते हैं। इन कमियों को तथाकथित बाइनरी यंग टेबल की मदद से आंशिक रूप से हल किया जाता है, जिसे मैं निकट भविष्य में किसी भी तरह लिखने की कोशिश करूंगा।