14
यह पता लगाने का सबसे तेज़ तरीका क्या है कि unordered_map कंटेनर में एक निर्दिष्ट कुंजी वाला आइटम है?unordered_map: कौन सा तेजी से ढूंढता है() या गिनती()?
A
उत्तर
13
वे बराबर प्रदर्शन के बारे में होगा। आपको एल्गोरिदम का उपयोग करना चाहिए जो आप जो करने की कोशिश कर रहे हैं उसे सबसे अच्छा व्यक्त करता है।
उस पर विस्तृत करने के लिए, आम तौर पर count()find() का उपयोग करके कार्यान्वित किया जाएगा। उदाहरण के लिए, libcxx में, count() कार्यान्वित किया जाता है के रूप में return (find(__k) != end());
1
मुझे लगता है कि यहां खोज सबसे अच्छा विकल्प है, आगे जाने की कोई आवश्यकता नहीं है।
http://www.cplusplus.com/reference/unordered_map/unordered_map/find/
1
find() और count() सी में कई कंटेनरों पर लागू होते हैं ++।
मानचित्रों, सेट इत्यादि के लिए हमेशा निरंतर निष्पादन समय होगा, क्योंकि यह केवल हैश की गणना करता है, और पाए गए पहले तत्व (end()) में एक पुनरावर्तक देता है।
count() दूसरी ओर, निरंतर निष्पादन समय ओ (ई) है, जहां ई प्रदान की गई कुंजी की संख्या कितनी बार पाई जाती है। सबसे खराब स्थिति, एक संग्रह है, जहां सभी सदस्य एक ही कर रहे हैं तो count एक जटिलता हे (एन)
map या unordered_map डुप्लिकेट के लिए अनुमति नहीं देते हो सकता था, इसलिए उनके asymptotic रन टाइम ही होगा।
विकल्प आपके कोड में अर्थशास्त्र पर निर्भर करता है। यदि आप सिर्फ यह जांचना चाहते हैं कि कोई कुंजी मौजूद है, तो आप केवल count का उपयोग कर सकते हैं। यदि आप यह जांचना चाहते हैं कि कोई कुंजी मौजूद है या नहीं, और उसके मान का उपयोग करें, तो find के लिए जाएं क्योंकि आपके पास पहले से ही उस तत्व को इंगित करने वाला एक इटरेटर होगा।
'unordered_map' जानता है कि इसमें अनन्य कुंजी हैं, इसलिए 'गिनती()' पहले मैच पर रुक जाएगी (जब तक कार्यान्वयन टूट नहीं जाता है, लेकिन आपको यह मानना चाहिए कि यह नहीं है) –