एलजी (एन) समय में एरलांग में बाइनरी खोज

Question

मैं एरलांग में बाइनरी खोज करने के लिए संभावित काम के आसपास खोज कर रहा था और मुझे http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/ मिला लेकिन मैं सोच रहा था कि ब्लॉग में समाधान ओ (एलजी एन) में चलता है या नहीं। अब बाइनरी खोज के लिए पुनरावृत्ति है: टी (एन) = टी (एन/2) + सी जो मुझे ओ (एलजी एन) का निष्पादन समय देता है।

चूंकि एक सी सरणी में आपके पास O (1) समय में किसी तत्व को एक्सेस करने की शक्ति है। लेकिन erlang में अगर सूची के मध्य तक पहुंचने में सीएन समय लगता है, तो द्विआधारी खोज रैखिक खोज के रूप में गरीब के रूप में रैखिक समग्र समय में चलता है।

मैं सूचियों में आया: सूची में nth आइटम खोजने के लिए nth/2 BIF लेकिन मुझे इसके निष्पादन समय के बारे में निश्चित नहीं है।

कोई टिप्पणी?

Answer 1

कुछ डेटा संरचनाएं हैं जो ओर्लैंड में ओ (1) पहुंच की अनुमति देती हैं: ईटीएस टेबल, टुपल्स और बाइनरी।

अब, उनमें से कोई भी बाइनरी खोज के लिए वास्तव में उपयुक्त नहीं होगा। ईटीएस तालिका शुरुआत से खोज का समर्थन करती है, और अन्यथा, परिणाम लौटने पर डेटा को आपकी प्रक्रिया में कॉपी किया जाता है, जो आपके उपयोग के मामले के लिए इष्टतम नहीं होने की संभावना है।

टुपल्स ओ (1) element/2 के साथ पहुंच की अनुमति देता है, लेकिन उन्हें संशोधित करने के लिए एक निश्चित ओवरहेड होता है (यही कारण है कि सरणी मॉड्यूल tuples के पेड़ों का उपयोग करता है)।

तो फिर तुम बाइनरी (<<1,2,3,4,5>>) है, जो गणित सूचक के लिए, निम्न उदाहरण की तरह कुछ इसी तरह के लिए अनुमति देते हैं:

1> Sorted = <<$a,$b,$c,$d,$e,$f,$g,$h>>. 
<<"abcdefgh">> 
2> <<_:3/binary, X:1/binary, _/binary>> = Sorted. 
<<"abcdefgh">> 
3> X. 
<<"d">> 

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

आपकी सबसे अच्छी शर्त मूल्यों की एक सूची का उपयोग करने की संभावना होगी, इसे क्रमबद्ध करें, फिर element/2 के साथ नेविगेट करने के लिए list_to_tuple/1 का उपयोग करें।

हालांकि मैं आपकी खोज करने के लिए पेड़ का उपयोग करने की दृढ़ता से अनुशंसा करता हूं; यह एक संतुलित पेड़ बनाने के लिए gb_tree मॉड्यूल का उपयोग करने के लिए बहुत आसान होगा और अभी भी ओ (लॉग एन) खोज प्राप्त करें।

Answer 2

nth ओ (एन) है। निरंतर पहुंच डेटा संरचना (लगभग सी में लगभग सरणी) के लिए array module का उपयोग करें।