std :: vector

Question

में बाइनरी खोज मैं वेक्टर तत्वों की स्थिति को किसी अन्य वेक्टर में देखने की कोशिश कर रहा हूं। यहां मैं binary search जितनी तेजी से कार्यान्वयन का उपयोग करने में रूचि रखता हूं। मेरे पास लंबाई 1 मिलियन या उससे अधिक के विभिन्न वैक्टर हैं, इसलिए मैं कुछ तेज़ी से हासिल करने की कोशिश कर रहा हूं। मेरे मामले में

के बाद स्थितियों:

1)vector जिसमें मैं तलाश कर रहा हूँ क्रमबद्ध किया जाता है।

2) तत्व मैं के लिए हमेशा वहाँ हो जाएगा यानी मैं not found का मामला नहीं है, और मैं एक तेजी से रास्ते में वेक्टर तत्व के सूचकांक प्राप्त करना चाहते हैं तलाश कर रहा हूँ।

मैंने वेक्टर तत्वों के सूचकांक प्राप्त करने के लिए निम्न कोड का प्रयास किया।

#include <iostream> 
#include <vector> 
#include <algorithm> 

template<class Iter, class T> 
Iter binary_find(Iter begin, Iter end, T val) 
{ 
    Iter i = std::lower_bound(begin, end, val); 
    return i; 
} 

int main() { 
    std::vector<std::string> values = {"AAAAAA","AB", "AD" ,"BCD","CD", "DD" }; 
    std::vector<std::string> tests = {"AB", "CD","AD", "DD"}; 
    for(int i=0 ; i < tests.size(); i++) { 
     int pos = binary_find(values.begin(), values.end(), tests.at(i))- values.begin(); 
    std::cout << tests.at(i) << " found at: " << pos <<std::endl; 
    } 
    return 0; 
} 

मैं अगर कोड द्विआधारी खोज कार्यान्वयन के साथ मेल खाता है पता करना चाहते हैं। ??

क्या वेक्टर तत्वों की अनुक्रमणिका प्राप्त करने का कोई तेज़ तरीका है?

इस कोड को बेहतर बनाने के लिए कोई और सुझाव।

Answer 1

binary_find कुछ भी वापस नहीं करता है के बावजूद void वापस जाने के लिए घोषित नहीं किया, तो यह व्यवहार अपरिभाषित है।

इसे ठीक करने के बाद, और यह मानते हुए कि आपके पास क्रमशः वेक्टर की सामग्री के बारे में कोई विशिष्ट ज्ञान नहीं है, बाइनरी खोज काफी अनुकूल है।

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

Answer 2

प्रश्न 1: मैं जानना चाहता हूं कि कोड बाइनरी खोज कार्यान्वयन के साथ मेल खाता है या नहीं ??

हाँ, यह (almost) है। std::lower_bound की जाँच करें, जिसमें कहा गया है:

जटिलता:

औसत पर, पहली और पिछले बीच की दूरी में लघुगणक: लगभग log2 (एन) +1 तत्व तुलना निष्पादित करता है (जहां N इस दूरी है)। गैर-यादृच्छिक-पहुंच इटरेटर्स पर, इटरेटर अग्रिम में एन में अतिरिक्त रैखिक जटिलता उत्पन्न करता है।

---

Q2: वहाँ एक तेज़ तरीका वेक्टर तत्व के सूचकांक प्राप्त करने के लिए है ??।

यह एक बड़ा सवाल है।

---

प्रश्न 3: इस कोड को बेहतर बनाने के लिए कोई और सुझाव।

हैलो दुनिया, Code Review!

---

पीएस - क्या आपने कोड को संकलित भी किया?यह कई संदेश देता है, जैसे: सक्षम, इस तरह चेतावनी के साथ

warning: no return statement in function returning non-void [-Wreturn-type] 

संकलित:

g++ -Wall main.cpp 

Answer 3

http://www.cpluplus.com का कहना है कि binary_search के व्यवहार बराबर है करने के लिए:

template <class ForwardIterator, class T> 
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) { 
    first = std::lower_bound(first, last, val); 
    return (first != last && !(val < *first)); 
} 

तो हाँ, lower_bound अपनी पसंद के हथियार है। लेकिन जब आप अंतर लेते हैं तो आपको distance का उपयोग करना चाहिए। कारण, यदि स्थिति प्राप्त करने का एक तेज़ तरीका है तो उसे उस फ़ंक्शन में घुमाया जाएगा।

जहां तक ​​अन्य सुधार के रूप में, मैं उपयोग करने का सुझाव था सी ++ 14 के begin और end और नहीं एक समारोह है जो केवल एक lower_bound (और ठीक एक मूल्य के वापस जाने के लिए असफल।) तो मैं था जिस तरह से रैप करने के लिए कार्य करता है बुला इस कोड को इस तरह दिखेगा:

auto pos = distance(lower_bound(begin(values), end(values), tests[i]), begin(values));