कुशलता से आदेश दिया गया डेटा-स्ट्रक्चर जो डुप्लिकेट कुंजी का समर्थन करता है

Question

मैं एक डेटा संरचना की तलाश में हूं जो प्रविष्टियों को कुशलता से आदेश देता है। मैं इन वस्तुओं (इस मामले में व्यक्तियों) को किसी विशेष चर के मूल्य (इस मामले में फिटनेस) के आधार पर ऑर्डर करना चाहता हूं।

डेटा संरचना को डुप्लिकेट कुंजी की अनुमति देनी चाहिए क्योंकि अलग-अलग व्यक्तियों में एक विशेष फिटनेस मान हो सकता है। यह एक समस्या है क्योंकि उदाहरण के लिए TreeMap डेटा संरचना डुप्लिकेट कुंजी की अनुमति नहीं देती है। मैं इस प्रकार के पेड़ की तरह संरचना का उपयोग करना पसंद करूंगा क्योंकि इसकी दक्षता ओ (लॉग एन) है।

यदि मैंने व्यक्तियों को आदेशित सूची में डाला है, तो दक्षता ओ (एन) तक गिर जाएगी, और व्यक्तियों को डालने के बाद सॉर्ट करना बहुत ही कुशल नहीं होगा।

क्या कोई डेटा संरचना कुशल है, जो व्यक्तियों को आदेश देती है और डुप्लिकेट-कुंजी का समर्थन करती है?

मैं डेटा संरचना के निर्माण के बाद अक्सर प्रविष्टियों को जोड़ और निकाल दूंगा ताकि संरचना के निर्माण के बाद वस्तुओं को सॉर्ट करना बहुत महंगा हो।

Answer 1

Apache Commons और Guava दोनों मल्टीमैप्स का समर्थन करते हैं, जो आप खोज रहे हैं।

वैकल्पिक रूप से, अपने USECASE पर निर्भर करता है, तो आप एक ArrayList में तत्वों इकट्ठा होते हैं और ओ (n एलजी n) कुल समय में बाद में यह सॉर्ट कर सकते हैं।

या, आप एक तुलना को परिभाषित कर सकते हैं जो फिटनेस की तुलना बराबर की तुलना में फिटनेस की पहली और अन्य विशिष्ट गुणों की जांच करता है।

Answer 2

यदि आप सभी व्यक्तियों को जोड़े जाने के बाद ही ऑर्डर की परवाह करते हैं, और बाद में कोई नया व्यक्ति नहीं जोड़ते हैं, तो एक ऐरेलिस्ट को सॉर्ट करना शायद सबसे तेज़ विकल्प है।

अन्यथा, आप ट्रीसेट का उपयोग कर सकते हैं, और एक तुलनित्र है जो पहले फिटनेस की तुलना करता है, और फिर identity hash code द्वारा फिटनेस बराबर (या किसी अन्य विशिष्ट संपत्ति द्वारा) होते हैं। इस प्रकार आपकी सभी वस्तुएं अलग होंगी, लेकिन उन्हें फिटनेस द्वारा क्रमबद्ध किया जाएगा।

Answer 3

शास्त्रीय कंप्यूटर विज्ञान में, डेटा संरचना जिसे आप ढूंढ रहे हैं उसे Priority Queue कहा जाता है।

ऐसा इसलिए होता है कि जावा 1.5 के बाद, मानक जावा क्लास लाइब्रेरी में कार्यान्वयन है: java.util.PriorityQueue।

मैं इसका उपयोग करूंगा।

Answer 4

यदि आप नियमित TreeMap का उपयोग करना चाहते हैं तो आप इसे मूल्यों के बजाय स्टोर वैल्यू रैपर बना सकते हैं। ये रैपर तब एक ही कुंजी के साथ एकाधिक स्टोर करेंगे।

अन्यथा आप बाइनरी खोज पेड़ के आधार पर किसी प्रकार की क्रमबद्ध सूची संरचना का उपयोग कर सकते हैं। मैंने कुछ समय पहले लिखा था जो यहां उपलब्ध है: http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/ लेकिन मुझे यकीन है कि अधिक मानक कार्यान्वयन मौजूद हैं। इस तरह की संरचना का लाभ यह है कि contains(Object) विधि रैखिक समय के बजाय समय लॉगरिदमिक में चलती है।