हैश सेट किसके लिए है?

हैश-सेट डेटा संरचना (और सामान्य रूप से सेट) एक ऐसी दुर्लभ संरचना है जो सभी मानक पुस्तकालयों में नहीं पाई जाती है। .NET फ्रेमवर्क में, उदाहरण के लिए, यह केवल संस्करण 3.5 के साथ दिखाई दिया। हालांकि, कुछ मामलों में, हैश-सेट काफी उपयोगी हो सकता है।

इस लेख में मैं दिखाऊंगा कि जब यह हैश-सेट का उपयोग करने के लिए समझ में आता है और आपको इसके लिए क्या भुगतान करना होगा।



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

• आइटम जोड़ें।
• आइटम हटाएं।
• जांचें कि क्या कोई आइटम मौजूद है।
• सभी तत्वों के माध्यम से जाओ।

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

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

रूबी में, एल्गोरिथ्म इस प्रकार है:

def group_elements(elements, ignore_list) groups = [] for element in elements assigned = false for group in groups #   ,     true; #  ,  false. if group.accept(element, ignore_list) assigned = true break end end #      , #     . if !assigned groups << Group.new(element) end end return groups end 

यहां बताया गया है कि समूह :: स्वीकार () पद्धति कैसे लागू की जाती है:

 class Group ... def accept(element, ignore_list) for my_element in @elements if my_element.match(element) @elements << element return true end end return false end ... end 

और अंत में, तत्व :: मैच () विधि:

 class Element ... def match(element, ignore_list) #  . my_tags_filtered = @tags.select { |tag| !ignore_list.include?(tag) } its_tags_filtered = element.tags.select { |tag| !ignore_list.include?(tag) } #  . intersection = my_tags_filtered & its_tags_filtered #        #      . return intersection.length > 0 && intersection.length == [my_tags_filtered.length, its_tags_filtered.length].max end ... end 

यहां एक माथे का कार्यान्वयन है, जहां दोनों टैग स्वयं को सूचीबद्ध करते हैं और अनदेखी सूची नियमित गतिशील सरणियां हैं। वह है, ign_list.include ऑपरेशन? रैखिक जटिलता है। इसके अलावा, याद रखें कि टैग 5-10 वर्णों की औसत लंबाई के साथ तार होते हैं, और स्ट्रिंग तुलना में रैखिक जटिलता होती है। यह देखते हुए कि समूहन में O (n ² ) जटिलता है, बुनियादी तुलना संचालन का अनुकूलन उत्पादकता में उल्लेखनीय वृद्धि दे सकता है।

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

मैंने २०००-३००० के क्रम के तत्वों की संख्या के साथ उपरोक्त रूबी एल्गोरिथ्म के दो कार्यान्वयन की तुलना की, २-१५ UTF-UT वर्णों के टैग आकार और प्रति तत्व टैग की संख्या, औसतन ५. हैश-सेट के साथ सरणी को प्रतिस्थापित करते हुए लगभग १० का प्रदर्शन लाभ दिया समय।

सामान्य तौर पर, हैश-सेट आपको सेट - चौराहे, संघ और घटाव पर अधिक आशावादी संचालन लागू करने की अनुमति देते हैं। हालांकि, उनके अतिरेक के बारे में मत भूलना। हैश-सेट अपने तत्वों को संग्रहीत करने के लिए आवश्यक से अधिक मेमोरी आरक्षित करते हैं, इसलिए यह केवल मध्यम-आकार के सेट (100-10000 तत्वों) के लिए उनका उपयोग करने के लिए समझ में आता है। वास्तव में, आप तेजी से गणना प्राप्त करने के लिए मेमोरी बर्बाद कर रहे हैं। बड़े सेटों के लिए, पेड़ों का उपयोग किया जाना चाहिए।