कैसे एक बिंदु अंतराल के सेट के भीतर है या नहीं?

Question

मैं यह तय करने का सबसे तेज़ तरीका ढूंढ रहा हूं कि लाइन पर कोई बिंदु इस पंक्ति के उप-समूह में है या नहीं। मैं एक पूर्णांक प्वाइंट दिए गए रहा हूँ, और मैं भी एक "सूची" है या तो:

1. अंक, एक पूर्णांक (3, 10, 1000, आदि)
2. अंतराल का प्रतिनिधित्व करती है कि मैं 2 से प्रतिनिधित्व करते हैं पूर्णांक (2:10 2 से 10 inluded, 50:60, आदि) के सभी पूर्णांक हैं

इस उदाहरण में, यदि मेरे बिंदु का मान 5 है, तो मैं सच हो जाता हूं क्योंकि यह अंतराल में शामिल होता है , 55 के लिए भी। यदि मेरा बिंदु 1000 के बराबर है, तो मैं भी सच लौटाता हूं क्योंकि यह बिंदुओं की सूची से मेल खाता है।

मैं इस स्थिति की जांच करने के लिए एक तेज़ तरीका (रैखिक से तेज़) की तलाश में हूं, जितना संभव हो उतने पूर्णांक को कम करने के बिना (संभवतः, 1: 1000 अंतराल के लिए मैं instanciate नहीं करना चाहता 1000 पूर्णांक)। क्या यह लॉगरिदमिक समय में किया जा सकता है?

धन्यवाद

संपादित करें: क्योंकि एक बार मेरी प्रारंभिक अंतराल कार्रवाई की जाती है मैं 10k अंक

को यह परीक्षण लागू करने की आवश्यकता आप विचार कर सकते हैं कि किसी भी समय डेटा की सूची-प्रक्रिया पूर्व करने के लिए लिया, 0 के बराबर है

Answer 1

हम्म, शायद आप एक अंतराल या एक खंड पेड़ का उपयोग कर सकते हैं:

• http://en.wikipedia.org/wiki/Segment_tree
• http://en.wikipedia.org/wiki/Interval_tree

Answer 2

पहले अंक के एक हैश_मैप की जांच करें। यह सरल जांच है।

फिर पहले समन्वय द्वारा अंतराल के मानचित्र को ऑर्डर करें और फिर बिंदु के निचले_बाउंड को ढूंढें।

फिर जांचें कि क्या आप वापस तत्व में निहित हैं या नहीं। यदि आप उसमें नहीं हैं, तो आप किसी भी में नहीं हैं।

Answer 3

यदि आपके पास पूर्णांक श्रेणी क्रमबद्ध हैं और श्रेणियां गैर-ओवरलैपिंग हैं, तो आप लॉगरिदमिक समय में सही सीमा को खोजने के लिए बाइनरी खोज कर सकते हैं।

क्या इस श्रेणी में कोई बाधा है? उस पर आधारित आप लगातार समय में खोज करने के लिए हैशिंग फ़ंक्शन के साथ आ सकते हैं। लेकिन यह इस बात पर निर्भर करता है कि आपकी बाधाएं कैसे हैं।

Answer 4

आप इसे सबलाइनर समय में कर सकते हैं एक वृक्ष डेटा संरचना (मैं बी-पेड़ की सिफारिश करता हूं), यदि आप पेड़ बनाने के लिए समय निकालने की गणना नहीं करते हैं (ज्यादातर पेड़ एन लॉग एन या इसी तरह के समय लेते हैं बनाने के लिए)।

यदि आपके पास सिर्फ एक सादा सूची है, तो आप रैखिक से बेहतर नहीं कर सकते हैं क्योंकि सबसे बुरे मामले में आपको संभावित रूप से सभी बिंदुओं और अंतराल की जांच करनी पड़ती है।

Answer 5

आप एक Bloom Filter का उपयोग एक बिंदु का परीक्षण कर सकते हैं और देखते हैं अगर यह नहीं है एक अंतराल में, रैखिक ओ (1) समय में। यदि यह उस परीक्षा को पास करता है तो आपको एक अन्य विधि का उपयोग करना चाहिए जैसे बाइनरी खोज यह देखने के लिए कि क्या यह निश्चित रूप से अंतराल का हिस्सा है, ओ (लॉग एन) समय में।

Answer 6

परछाई के बाद, मुझे लगता है कि निम्नलिखित कोड लघुगणक समय में काम करना चाहिए, समय नक्शा बनाने की जरूरत को छोड़कर:

enum pointType { 
    point, 
    open, 
    close 
}; 
std::map<long int, pointType> mapPoints; 

mapPoints.insert(std::pair<long int, pointType>(3, point)); 

//create the 5:10 interval: 
mapPoints.insert(std::pair<long int, pointType>(5, open)); 
mapPoints.insert(std::pair<long int, pointType>(10, close)); 

int number = 4; 
bool inside = false; 
std::map<long int, pointType>::iterator it1 = mapPoints.lower_bound(number); 

if(it1->first == number || it1->second == close) { 
    inside = true; 
} 

मुझे लगता है कि यह रूप में लंबे समय से काम करना चाहिए के रूप में नक्शे को ठीक से गैर से भर जाता है - ओवरलैपिंग अंतराल