अलग-अलग मूल्यों की श्रेणियों को संग्रहीत करने और पुनर्प्राप्त करने के लिए मैं किस डेटा संरचना का उपयोग कर सकता हूं?

Question

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

संभव आरंभ और अंत मान 0 और के बीच 4294967295 (2 - 1 या 0xFFFFFFFF), हालांकि वहाँ कई बड़े "छेद" डोमेन है कि कोई सीमा कभी कवर किया जाएगा, यहां तक ​​कि आंशिक रूप से कर रहे हैं। संभावनाओं के डोमेन की तुलना में अधिकतर श्रेणियां बहुत छोटी होंगी: मुझे उम्मीद है कि भारी बहुमत 2000 से अधिक लंबा होगा।

इस संरचना के लिए मेरा सबसे महत्वपूर्ण उपयोग केस उन सभी श्रेणियों को देखना होगा जो दिए गए हैं पूर्णांक मूल्य। अधिकांश समय, मुझे लगता है कि लुकअप विफल हो जाएगा (दिए गए मान वाले कोई सीमा नहीं होगी)।

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

इसके लिए मैं किस प्रकार की डेटा संरचना का उपयोग कर सकता हूं? श्रेणियों की सूची में एक रैखिक खोज अव्यवहारिक है क्योंकि लुकअप अधिकांश समय विफल रहता है; और मुझे बहुत बार लुकअप करने की ज़रूरत है।

Answer 1

मुझे सिस्टम पसंद है। इस तरह कुछ के लिए हल करें [या एफ # सूचियां लेकिन कुछ लोग एफ # जानते हैं]।

यदि सीमा निरंतर है जो टुपल टुपल nums = (प्रारंभ, अंत) के रूप में प्रारंभ और अंत पूर्णांक को आसान बनाता है, अन्यथा टुपल की पहली प्रविष्टि के रूप में स्टार्ट-एंड के साथ टुपल होता है और दूसरे के रूप में सूची आपके लिए काम कर सकती है, टुपल nums = ((प्रारंभ, अंत), सूची)।

Answer 2

यदि आप एक श्रेणी में सभी श्रेणियों की शुरुआत और अंत को एक श्रेणी के रूप में श्रेणी के रूप में संग्रहीत करते हैं तो आप इसे क्रम में कर सकते हैं। यानी mylist = [{45: range1}, {47: range2}, {55: range1}, {57: range2}] फिर आप सूची के माध्यम से स्कैन कर सकते हैं और पहली बार जब आप एक टैग और झूठी देखते हैं तो एक बुलियन सत्य सेट कर सकते हैं दूसरी बार आप इसे देखते हैं। जब आपको अपने से अधिक संख्या मिलती है तो आप बता सकते हैं कि आप किन श्रेणियों के अंदर हैं। आप ओ (लॉग) को सम्मिलित करने के लिए bisect का उपयोग कर सकते हैं, जबकि हटाए गए और आवेषण ओ (एन) हैं। शुभ लाभ! ~ बेन

Answer 3

बाइनरी पेड़ जहां कुंजी प्रारंभ (कम) मान है। एक बार जब आप एक कुंजी पा लेते हैं तो आप काफी आसानी से (उच्च और निचले) देख सकते हैं।

Answer 4

प्रयास 1:

2 द्विआधारी पेड़, शुरू मूल्यों के लिए एक और अंत मूल्यों के लिए एक रखें। दोनों पेड़ों (या सिर्फ 'अंत') के लिए अपने नोड्स को एक आईडी (श्रेणी का प्रारंभ मूल्य) द्वारा अद्वितीय श्रेणियों का संदर्भ देने वाली संपत्ति है।

सूची शुरू करने के लिए 'प्रारंभ' पेड़ पर एक बाइनरी खोज करें जहां सूची आपके खोज मूल्य से कम या बराबर है। 'एंड' पेड़ पर ऐसा ही करें जहां मूल्य खोज मूल्य से अधिक या बराबर है। दोनों पेड़ों से नोड्स के चौराहे का पता लगाएं, और उन श्रेणियों में आपका खोज मूल्य होता है।

आप इष्टतम प्रदर्शन के लिए हैश मानचित्र/सेट का उपयोग करके चौराहे पा सकते हैं।

प्रयास 2:

क्या होगा यदि आप अंतराल जहां कुंजी पहले हालांकि कई बिट्स कि दोनों आरंभ और अंत मूल्यों से साझा किया जाता है के लिए एक हैश सूची रखा?

तो, यदि शुरूआत '11001101' है और अंत '11010010' है, तो कुंजी '110' है। प्रत्येक कुंजी कुंजी साझा करने वाली श्रेणियों (प्रारंभ और अंत) की सूची में मैप करेगी।

जब यह देखने के लिए मूल्य की खोज होती है कि वे किस श्रेणी में हैं, उदाहरण के लिए '00101111', तो आपको अलग-अलग मानों के लिए हैश सूची खोजनी होगी या फिर, जहां बिट्स की संख्या है (32 में मामला)। इस मामले में, आप '00101111', '0010111', '001011', और इसी तरह की खोज करेंगे। प्रत्येक हिट के लिए, आपको वास्तव में जांचना होगा कि खोज मूल्य सीमा में है।

पहली नजर में, यह मुझे लगता है कि औसतन, आपको हर हिट के लिए आधा झूठा सकारात्मक होगा, लेकिन इससे कोई फर्क नहीं पड़ता कि हिट की संख्या कम है, और बड़ी चाबियाँ कम हैं इसे हिट करना चाहिए।

'00101110' की शुरूआत और '01100111' के अंत में थोड़ी सी समस्या है क्योंकि कुंजी '0' होगी जिसका अर्थ है 'झूठी सकारात्मक' की एक बड़ी संख्या होगी। बेहतर होगा अगर 2 अलग-अलग कुंजी, '001' और '01' हों, हालांकि मुझे इस अनुकूलन के लिए विशेष एल्गोरिदम के बारे में निश्चित जानकारी नहीं है। यदि श्रेणियां काफी छोटी हैं और इस समस्या को हल या अनदेखा किया जा सकता है, तो आप बहुत तेजी से लुकअप प्राप्त कर सकते हैं क्योंकि अधिकांश चाबियाँ अपेक्षाकृत लंबी होंगी और खोजों से मेल नहीं खातीं।