सी ++ मूल्य

Question

द्वारा सरणी के तत्व की अनुक्रमणिका प्राप्त करें अब तक, मैं एक वेक्टर में सरणी संग्रहीत कर रहा हूं और फिर मिलान तत्व ढूंढने के लिए वेक्टर के माध्यम से लूपिंग कर रहा हूं और फिर अनुक्रमणिका को वापस कर रहा हूं।

क्या सी ++ में ऐसा करने का कोई तेज़ तरीका है? एसटीएल संरचना जो मैं सरणी को स्टोर करने के लिए उपयोग करता हूं वह वास्तव में मेरे लिए महत्वपूर्ण नहीं है (यह एक वेक्टर नहीं होना चाहिए)। मेरी सरणी भी अद्वितीय है (कोई दोहराव तत्व नहीं) और आदेश दिया गया (उदाहरण के लिए समय में आगे की तारीखों की एक सूची)।

Answer 1

चूंकि तत्वों को सॉर्ट किया गया है, इसलिए आप मेल खाने वाले तत्व को खोजने के लिए बाइनरी खोज का उपयोग कर सकते हैं। सी ++ मानक पुस्तकालय में std::lower_bound एल्गोरिदम है जिसका उपयोग इस उद्देश्य के लिए किया जा सकता है। मैं, अपने स्वयं के द्विआधारी खोज एल्गोरिदम में यह लपेटकर सिफारिश करेंगे स्पष्टता और सादगी के लिए:

/// Performs a binary search for an element 
/// 
/// The range `[first, last)` must be ordered via `comparer`. If `value` is 
/// found in the range, an iterator to the first element comparing equal to 
/// `value` will be returned; if `value` is not found in the range, `last` is 
/// returned. 
template <typename RandomAccessIterator, typename Value, typename Comparer> 
auto binary_search(RandomAccessIterator const first, 
        RandomAccessIterator const last, 
        Value    const& value, 
        Comparer     comparer) -> RandomAccessIterator 
{ 
    RandomAccessIterator it(std::lower_bound(first, last, value, comparer)); 
    if (it == last || comparer(*it, value) || comparer(value, *it)) 
     return last; 

    return it; 
} 

(सी ++ स्टैंडर्ड लाइब्रेरी एक std::binary_search है, लेकिन यह एक bool रिटर्न: true अगर सीमा अन्यथा तत्व, false शामिल हैं। यदि आप तत्व के लिए इटरेटर चाहते हैं तो यह उपयोगी नहीं है।)

एक बार जब आप तत्व के लिए पुनरावृत्ति प्राप्त कर लेते हैं, तो आप श्रेणी में तत्व की अनुक्रमणिका की गणना करने के लिए std::distance एल्गोरिदम का उपयोग कर सकते हैं।

इन दोनों एल्गोरिदम std::vector और सामान्य सरणी सहित दोनों यादृच्छिक अभिगम अनुक्रम समान रूप से अच्छी तरह से काम करते हैं।

Answer 2

यदि आप किसी इंडेक्स के साथ एक मूल्य जोड़ना चाहते हैं और इंडेक्स को जल्दी से ढूंढना चाहते हैं तो आप std::map या std::unordered_map का उपयोग कर सकते हैं। डेटा पर प्रदर्शन करने वाले अन्य परिचालनों के आधार पर आप इन्हें अन्य डेटा संरचनाओं (उदा। std::list या std::vector) के साथ भी जोड़ सकते हैं।

उदाहरण के लिए, जब वेक्टर बनाने हम भी एक लुकअप तालिका बनाने के लिए:

vector<int> test(test_size); 
unordered_map<int, size_t> lookup; 
int value = 0; 
for(size_t index = 0; index < test_size; ++index) 
{ 
    test[index] = value; 
    lookup[value] = index; 
    value += rand()%100+1; 
} 

अब सूचकांक आप बस को देखने के लिए:

size_t index = lookup[find_value]; 

एक हैश तालिका आधारित डेटा संरचना का उपयोग करना (जैसे unordered_map) एक काफी शास्त्रीय स्थान/समय व्यापार है और जब आप बहुत सारे लुकअप करने की ज़रूरत होती है तो इस तरह के "रिवर्स" लुकअप ऑपरेशन के लिए बाइनरी खोज करने से बेहतर प्रदर्शन कर सकते हैं। दूसरा फायदा यह है कि यह भी काम करता है जब वेक्टर रद्द नहीं होता है।

मस्ती के लिए

:-) मैं VS2012RC में एक त्वरित बेंचमार्क एक रेखीय खोज के साथ और एक वेक्टर पर देखने के लिए unordered_map का उपयोग कर, सभी के साथ जेम्स 'द्विआधारी खोज कोड की तुलना किया है:

करने के लिए ~ 50000 तत्वों unordered_set महत्वपूर्ण (x3-4) अपेक्षित ओ (लॉग एन) व्यवहार को प्रदर्शित करने वाली बाइनरी खोज से बाहर है, कुछ हद तक आश्चर्यजनक परिणाम यह है कि unordered_map यह 10000 तत्वों के पिछले ओ 00 (1) व्यवहार को खो देता है, शायद हश टकराव के कारण, शायद एक कार्यान्वयन मुद्दा।

संपादित करें: unordered मानचित्र के लिए max_load_factor() 1 है इसलिए कोई टकराव नहीं होना चाहिए। बहुत बड़े वैक्टरों के लिए बाइनरी खोज और हैश टेबल के बीच प्रदर्शन में अंतर कैशिंग से संबंधित प्रतीत होता है और बेंचमार्क में लुकअप पैटर्न के आधार पर भिन्न होता है।

Choosing between std::map and std::unordered_map आदेशित और अनियंत्रित मानचित्रों के बीच अंतर के बारे में बात करता है।