लगातार पूर्णांक की बड़ी श्रृंखला के लिए डेटा संरचना?

Question

मान लीजिए कि आपके पास स्मृति में लगातार पूर्णांक की एक बड़ी श्रृंखला है, जिनमें से प्रत्येक बिल्कुल एक श्रेणी से संबंधित है। दो ऑपरेशन ओ (लॉग एन) होना चाहिए: एक श्रेणी से दूसरे श्रेणी में एक श्रेणी को स्थानांतरित करना, और किसी दिए गए श्रेणी के लिए श्रेणी गणना करना।

मुझे पूरा यकीन है कि दूसरे ऑपरेशन को पहले ऑपरेशन के लिए सही कार्यान्वयन के साथ हल किया गया है।

प्रत्येक पूर्णांक एक श्रेणी में शुरू होता है, इसलिए मैंने संतुलित बीएसटी के एक सेट के साथ शुरुआत की। एक बीएसटी से दूसरे में एक उप-स्थानांतरित करना (उदाहरण के लिए, एक श्रेणी को एक अलग श्रेणी में ले जाना) में दो बीएसटी विलय करने के बराबर रनटाइम होता है, जो ओ (एन 1 * एन 2) [1] है।

यह बहुत धीमा है (पायथन में, और सी एक विकल्प नहीं है), और मैं एक कुशल बीएसटी मर्ज ऑपरेशन बनाने के लिए अपने डेटा की अंतर्निहित संरचना का लाभ उठाने का एक तरीका नहीं समझ पाया।

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

संपादित करें (समस्या स्पष्टीकरण): मैं इन मूल्यों को संग्रहीत करने और अपनी डेटा संरचनाओं को बनाने के तरीके पर लचीला हूं। मैं इस बारे में लचीला हूं कि मुझे अपना इनपुट कैसे प्राप्त होता है, जो किसी अन्य एप्लिकेशन से आता है, और निम्न जैसा दिखता है: CATEGORY(cat3, I, J)। मेरा वर्तमान समाधान सीमा में प्रत्येक पूर्णांक के लिए एक नोड के साथ एक पेड़ बनाता है। यह मेरे डेटासेट के आकार के लिए बहुत धीमा है, इसलिए यदि बेहतर तरीका दिया गया है तो मुझे फिर से आर्किटेक्ट करने में खुशी होगी।

कोई भी अनुरोध किसी भी श्रेणी में पूर्णांक की किसी भी संभावित सीमा को स्थानांतरित कर सकता है। दूसरे शब्दों में, CATEGORY(cat1, 1, 10) के बाद CATEGORY(cat3, 5, 15) के अर्थ में श्रेणियां ओवरलैपिंग कर रही हैं, लेकिन इस अर्थ में गैर-ओवरलैपिंग कि प्रत्येक पूर्णांक किसी भी समय बिल्कुल एक श्रेणी में होगा।

Answer 1

जहाँ तक मेरा सवाल समझ में आ आप एक श्रृंखला है [ए, बी] और फार्म के प्रश्नों -

1. किसी विशेष श्रृंखला एक वर्ग

 
E.g. 
R1 R2 C1 
R3 R4 C2 

1. इसे असाइन करें विशेष श्रेणियों में वस्तुओं की कुल संख्या के लिए एक सीमा पूछें। ईजी। आर 1 R4 में श्रेणियों की गिनती को खोजने

एक साधारण कार्यान्वयन शब्दकोशों का उपयोग कर के रूप में ऊपर दिए गए के रूप में मैं इस उदाहरण से वर्णन काम नहीं होगा -

लगता है हम एक श्रृंखला है [1000, 5000]

और हम काम कर के रूप में निम्नानुसार -

 
1 2 C1 
2 3 C2 
3 4 C3 
...... 
4999 5000 C4999 

अब हम निम्नलिखित काम कर

 
1 5000 C5555 

यह अपडेशन/परिवर्तन/हटाए जाने के पहले से सौंपा को पर्वतमाला हे (एन) की सीमाओं कर देगा जहां एन रेंज का अधिकतम आकार है (बी - एक)

डी [ 'श्रेणी'] सेट = (of_all_the_ranges_you_have_in_category)

श्रेणियों में इसी सेट C1, C2 ... C4999 पिछले काम (1 5000 C5555)

या

के लिए आवश्यक हो जाएगा से पिछले पर्वतमाला की इस मामले से हटाया गया

1: { "रोक": 5, "श्रेणी": "सी 1"}, 6: { "रोक": 19, "श्रेणी": "C23"} यहाँ

, को अद्यतन करने प्रत्येक प्रारंभिक मान (1,2,3,4 ..., 4 9 99) के लिए श्रेणी की आवश्यकता अंतिम कार्य (1 5000 सी 5555)

एक बेहतर विकल्प है जो ओ (एलजी एन) में श्रेणियों को अद्यतन करने के लिए एक बेहतर विकल्प होगा हो खंड पेड़ (http://en.wikipedia.org/wiki/Segment_tree)

ऊपर के उदाहरण segm के लिए ईएनटी पेड़ इस

    1000:5000 
         | 
      --------------------- 
      |     | 
      1000:3000   3001:5000 
      |     | 
    ----------------  -------------------- 
    |    |  |     | 
1000:2000  2001:3000 3001:4000  4001:5000 

कुछ ऐसी दिखाई देगी .................................... ............................. .................... ....................................... और

पर पत्ती नोड्स में श्रेणियां होंगी (1: 2, 2: 3, ...)

आप प्रत्येक नोड को एक मूल्य "श्रेणी" असाइन कर सकते हैं और अंतराल को उचित रूप से अंतराल को विभाजित करने वाले पेड़ को पार कर सकते हैं (उदाहरण के लिए 2500 से 4500 में 2500 विभाजन: 3000 और 3001: 4500 और मिलान दिशाओं के साथ नोड्स मिलने तक दोनों दिशाओं में आगे बढ़ें)।

अब जब आप की जरूरत होती है तो नोड्स के बच्चों को एक दिलचस्प बात अपडेट होती है। उदाहरण के लिए 1 5000 C5555 जैसे असाइनमेंट करते समय तुरंत बच्चों को अपडेट करना जारी रखें। इस बात को आलसी प्रचार कहा जाता है और आप यहां इसके बारे में अधिक जान सकते हैं (http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296)।

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

मुझे लगता है कि पूछताछ के लिए एक बेहतर समाधान मौजूद हो सकता है। यह मेरे दिमाग में नहीं आ रहा है।

अद्यतन चलिए एक छोटा सा उदाहरण लेते हैं।

रेंज [1,8]

श्रेणियाँ अनुमति {C1, C2}

 1:8 
    1:4   5:8 
    1:2 3:4  5:6 7:8 
1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 

प्रत्येक नोड 3 क्षेत्रों होगा [श्रेणी, category_counts [], children_update_required = false]

1 5 सी 1

क्वेरी विभाजित हो जाएगी और नोड्स 1: 4 की श्रेणी सी 1 पर सेट की जाएगी और kids_update_required सत्य पर सेट हो जाएंगे, इसके बच्चे अब अपडेट नहीं होंगे (केवल आवश्यक या आलसी प्रचार के दौरान अद्यतन याद रखें)। इसके अलावा नोड 5: 5 वर्ग सी 1

पर निर्धारित किया जाएगा

3 4 सी 2

क्वेरी पेड़ के साथ प्रचार की दिशा में 3 होगा: 4 (और इस प्रक्रिया में 3 तक पहुँचने के लिए: 4, 1: 2 और 3: 4 के श्रेणियों को सी 1 में अपडेट किया जाएगा, 1: 4 के बच्चों_अपडेट_रेक्वायर को झूठी पर सेट किया जाएगा, 1: 2 और 3: 4 के बच्चे_अपडेट_रेक्वायर को सत्य पर सेट किया जाएगा) और अब वर्तमान आवश्यकता के अनुसार 3: 4 से सी 2 की श्रेणी अपडेट कर देगा। इसके बाद यह बच्चों को अपने बच्चों के भविष्य के अपडेट के लिए 3: 4 की आवश्यकता होगी, जो कि इस मामले में पहले से सेट है .. कोई नुकसान नहीं हुआ है)।

Answer 2

आप निम्न फॉर्म

1 : { "stop" : 5, "category" : "C1"}, 
6 : { "stop" : 19, "category" : "C23"}, 
etc 

की एक सादे अजगर शब्दकोश हो सकता है यहाँ कुंजी अपने रेंज की शुरुआत कर रहे हैं और मूल्यों रेंज और श्रेणी इस श्रेणी में गिर जाता है के अंत में होते हैं।

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

1 : { "stop" : 3, "category" : "C1"}, 
4 : { "stop" : 8, "category" : "new category"}, 
9 : { "stop" : 19, "category" : "C23"}, 
etc 

ढूँढना श्रेणी गिनती मामूली बात है, बस लगातार समय में अपने सभी वांछित पर्वतमाला इकट्ठा और श्रेणियों गिनती ..

संपादित करें: सफलतापूर्वक सबसे कम (उच्चतम) संगणना/परिवर्तन प्रदर्शन शुरू करने के लिए कुंजी खोजने के लिए, आप भी हल कर सभी कुंजी के साथ एक सादे अजगर सूची, और द्विविभाजित मॉड्यूल की जरूरत है। यह सूची में इंडेक्स को ओ (लॉगन) समय में रेंज की शुरुआत "डाल" में ढूंढने में मदद करेगा, फिर सबकुछ निरंतर समय में किया जा सकता है, ओ (एन) समय को छोड़कर नई कुंजी डालने के लिए आवश्यक समय bisect.insort_left के साथ सूची।

Answer 3

आप लगातार पूर्णांक के सरणी पर एक पेड़ संरचना का निर्माण कर सकते हैं, जो आपके निरंतर कारक के साथ मदद करनी चाहिए। पहले 0 से शुरू करने के अनुक्रम को पुनर्स्थापित करें, और अनुक्रम की सीमा से बड़ा दो की सबसे छोटी शक्ति है जो काम करें।

अब पूर्णांक 0-7 से बने निम्न पेड़ पर विचार करें, जिसे मैं चार सरणी के रूप में पकड़ सकता हूं, प्रत्येक सरणी क्षैतिज रूप से जा रही है।

  (all) 
    0-3  4-7 
    0-1 2-3 4-5 6-7 
0 1 2 3 4 5 6 7 

एक संख्या है और एक स्तर को देखते हुए, मैं उस स्तर के लिए सरणी में एक ऑफसेट, बस नंबर सही एक स्तर के आधार पर राशि स्थानांतरण करके पता कर सकते।

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

Answer 4

अनुमान:

• कोई पूर्णांक, वास्तव में एक श्रेणी से संबंधित कर सकते हैं ताकि पर्वतमाला मिलते नहीं हैं।
• आने वाली रेंज में सभी पूर्णांक एक श्रेणी से संबंधित हैं।
• कभी-कभी आपको किसी श्रेणी को एक अलग श्रेणी में स्थानांतरित करने के लिए एक श्रेणी को विभाजित करने की आवश्यकता होती है।

(start, end, category) tuples द्वारा प्रतिनिधित्व श्रेणी। रेंज अंतर नहीं करते हैं ताकि आप उनमें से एक पेड़ बना सकें। यह दूर व्यक्तिगत पूर्णांक के पेड़ की तुलना में अधिक किफायती है। श्रेणियों को आदेश देने के लिए (यानी, नोड्स) आप केवल प्रारंभ मान का उपयोग कर सकते हैं, क्योंकि यह अद्वितीय है और किसी अन्य श्रेणी से संबंधित नहीं हो सकता है।

अपने पेड़ स्कैन और प्रत्येक नोड/रेंज कि ​​पूरी तरह से [a, b] रेंज में शामिल है अद्यतन:

आप दूसरी श्रेणी से एक सीमा [a, b] स्थानांतरित करने के लिए है, तो आप के लिए है। यह एक साधारण गहराई है - पहला ट्रैवर्सल। ट्रैवर्सल

• यदि current_node.start < a or current_node.start > b, खोज को रोकें।
• यदि current_node.start >= a and current_node.end > b, तो आपको current_node दो में विभाजित करना होगा; [current_node.start, b] एक नई श्रेणी के होंगे, शेष इसकी मूल श्रेणी का होगा।
• यदि current_node.start < a and current_node.end <= b, तो आप दूसरी तरफ विभाजित हैं।

वृक्ष खोज लॉगरिदमिक है, और नोड विभाजन ओ (1) हैं।

यदि आपका पेड़ कभी भी खंडित हो जाता है, तो आप निकटवर्ती श्रेणियों वाले विलयों को विलय करने पर विचार कर सकते हैं। यह हमेशा माता-पिता और एक बच्चा होगा जिसके परिणामस्वरूप या तो एक डालने या विभाजन से होता है; लगता है और जुड़ता है हमेशा ओ (1) लगता है।

Answer 5

हम की तरह कुछ के रूप में वर्तमान राज्यों का प्रतिनिधित्व कर सकते हैं:

0:cat1 200:cat2 500: cat0 700:cat6 800:cat1 

इसका मतलब यह है 0-200 cat1 है, 200-500, cat2 है आदि हम एक द्विआधारी खोज वृक्ष प्रारंभिक पर keyed में मान संग्रहीत नंबर। प्रत्येक नोड में उस नोड के सभी बच्चों के लिए गणना करने के लिए एक शब्दकोश मैपिंग श्रेणियां भी होंगी।

उन शब्दकोशों को ओ (लॉग) समय में गणना प्राप्त करना आसान बनाना चाहिए। हमें बस प्रश्न में अनुक्रम की शुरुआत और स्टॉप के पथों पर सही संख्याएं जोड़नी होंगी।

हम अनुक्रम X-Y को श्रेणी Z में सेट करने की आवश्यकता होने पर हम क्या करते हैं?

1. यो की वर्तमान श्रेणी (logn) निर्धारित
2. एक्स -YO (के) बीच के सभी मानों निकालें, लेकिन जब से उन नोड्स डालने की लागत अधिक महंगा है, हम इसे कॉल कर सकते हैं हे (1) परिशोधित ।
3. एक्स ओ (लॉग एन)
4. अद्यतन श्रेणी गणना शब्दकोशों में नया नोड डालें।हमें केवल प्रभावित वर्गों के ओ (लॉग एन) माता-पिता को अद्यतन करने की आवश्यकता है, इसलिए यह ओ (लॉग एन)

कुल मिलाकर यह ओ (लॉग एन) समय है।