stl मानचित्र प्रदर्शन?

Question

मैं map<MyStruct, I*> map1; का उपयोग कर रहा हूं। जाहिर है कि मेरे कुल ऐप समय का 9% वहां खर्च किया जाता है। विशेष रूप से मेरे प्रमुख कार्यों में से एक की एक पंक्ति पर। नक्शा बहुत बड़ा नहीं है (< 1k लगभग हमेशा, < 20 आम है)।

क्या कोई वैकल्पिक कार्यान्वयन है जिसका उपयोग मैं करना चाहता हूं? मुझे लगता है कि मुझे अपना खुद नहीं लिखना चाहिए, लेकिन अगर मैंने सोचा कि यह एक अच्छा विचार था तो मैं कर सकता था।

अतिरिक्त जानकारी: मैं हमेशा तत्व जोड़ने से पहले जांचता हूं। यदि कोई कुंजी मौजूद है तो मुझे किसी समस्या की रिपोर्ट करने की आवश्यकता है। एक बिंदु के बाद से मैं लुकअप के लिए भारी नक्शा का उपयोग करूँगा और कोई और तत्व नहीं जोड़ूंगा।

Answer 1

क्या यह insert करने के लिए जल्दी होगा और यह जांचें कि pair.secondfalse है यदि कुंजी पहले से मौजूद है?

इस

if (myMap.insert(make_pair(MyStruct, I*)).second == false) 
{ 
    //report error 
} 
else 
    // inserted new value 

तरह के बजाय हर बार एक find कॉल कर?

Answer 2

जिस तरह से आप मानचित्र का उपयोग कर रहे हैं, आप MyStruct इंस्टेंस के आधार पर लुकअप कर रहे हैं और आपके विशेष कार्यान्वयन के आधार पर, आवश्यक तुलना महंगा हो सकती है या नहीं भी हो सकती है।

Answer 3

यह एक लंबा शॉट हो सकता है, लेकिन छोटे संग्रह के लिए, कभी-कभी सबसे महत्वपूर्ण कारक cache प्रदर्शन होता है।

std::map के बाद से लागू करता है एक लाल काला पेड़ है, जो [AFAIK] नहीं बहुत कैश-कुशल - शायद एक std::vector<pair<MyStruct,I*>> के रूप में नक्शे को लागू करने में एक अच्छा विचार हो सकता है, और वहाँ द्विआधारी खोज का उपयोग करें [बजाय नक्शे के लुक-अप] map की तुलना में कैश में फ़िट होने की अधिक संभावना है, क्योंकि कम से कम यह केवल कुशल होना चाहिए [तत्वों को सम्मिलित करना बंद करें], क्योंकि std::vectormap की तुलना में कैश में फिट होने की अधिक संभावना है।

यह कारक [सीपीयू-कैश] आमतौर पर उपेक्षित और बड़े ओ नोटेशन में निरंतर छिपा हुआ होता है, लेकिन बड़े संग्रह के लिए इसका मुख्य प्रभाव हो सकता है।

Answer 4

क्या कोई वैकल्पिक कार्यान्वयन है जिसका उपयोग मैं करना चाहता हूं? मुझे लगता है कि मुझे अपना खुद नहीं लिखना चाहिए, लेकिन अगर मैंने सोचा कि यह एक अच्छा विचार था तो मैं कर सकता था।

यदि आप अच्छी तरह से समस्या को समझते हैं, तो आपको विस्तार से बताया जाना चाहिए कि आपका कार्यान्वयन बेहतर होगा।

map उचित संरचना है? यदि ऐसा है, तो आपकी मानक लाइब्रेरी का कार्यान्वयन अच्छी गुणवत्ता (अच्छी तरह अनुकूलित) की संभावना होगी।

MyStruct तुलना सरल हो सकती है?

समस्या कहां है - आकार बदलना? देखो?

क्या आपने अपनी संरचनाओं के लिए कॉपी को कम और आवंटित किया है?

Answer 5

map के बजाय आप unordered_map कोशिश कर सकते हैं जो तत्व खोजने के लिए पेड़ के बजाय हैश कुंजी का उपयोग करता है। This answerunordered_mapmap से अधिक पसंद करते समय कुछ संकेत देता है।

Answer 6

सबसे पहले आपको यह समझने की आवश्यकता है कि नक्शा क्या है और आप कौन से संचालन का प्रतिनिधित्व कर रहे हैं। एक std::map एक संतुलित बाइनरी पेड़ है, लुकअप O(log N) संचालन लेगा, जिनमें से प्रत्येक कुंजी की तुलना में कुछ अतिरिक्त है जो आप ज्यादातर मामलों (सूचक प्रबंधन) में अनदेखा कर सकते हैं। सम्मिलन सम्मिलन के बिंदु का पता लगाने के लिए लगभग उसी समय लेता है, साथ ही नए नोड का आवंटन, पेड़ में वास्तविक सम्मिलन और पुनर्वितरण। जटिलता फिर से O(log N) है हालांकि छुपे हुए स्थिरांक अधिक हैं।

जब आप यह निर्धारित करने का प्रयास करते हैं कि प्रविष्टि से पहले मानचित्र में कोई कुंजी है, तो आप लुकअप की लागत ले रहे हैं और यदि यह सफल नहीं होता है, तो प्रविष्टि के बिंदु का पता लगाने के लिए एक ही लागत है। आप std::map::insert का उपयोग करके अतिरिक्त लागत से बच सकते हैं जो एक जोड़ी को एक पुनरावर्तक के साथ वापस लौटाता है और एक बूल आपको बताता है कि सम्मिलन वास्तव में हुआ था या तत्व पहले से ही वहां था।

सिवाय इसके, आप (MyStruct सिर्फ एक int या उनमें से हजार पकड़ सकता है) को समझने के लिए महंगा यह अपनी चाबी है, जो क्या सवाल शो से बाहर हो जाता है की तुलना करने की जरूरत है, जो कुछ आप में लेने की जरूरत है लेखा।

अंत में, यह मामला है कि एक map अपनी आवश्यकताओं के लिए सबसे कारगर डेटा संरचना नहीं है हो सकता है, और आप या तो एक std::unordered_map (हैश तालिका) के उपयोग पर विचार के लिए निरंतर समय सम्मिलन उम्मीद है कि (यदि हैश फंक्शन चाहते हो सकता है भयानक) या छोटे डेटा सेट के लिए भी एक सादा आदेशित सरणी (या std::vector) सेट करता है जिस पर आप तत्वों का पता लगाने के लिए बाइनरी खोज का उपयोग कर सकते हैं (इससे अधिक महंगे प्रविष्टियों की लागत पर आवंटन की संख्या कम हो जाएगी, लेकिन यदि आयोजित प्रकार छोटे होते हैं, यह इसके लायक हो सकता है)

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

Answer 7

टिप्पणियों में कहा गया है कि उचित कोड के बिना, आपको देने के लिए बहुत ही सार्वभौमिक उत्तर हैं। हालांकि, अगर MyStruct वास्तव में बड़ी है तो स्टैक प्रतिलिपि महंगा हो सकती है।

template <typename T> struct deref_cmp { 
    bool operator()(std::shared_ptr<T> lhs, std::shared_ptr<T> rhs) const { 
    return *lhs < *rhs; 
    } 
}; 

std::map<std::shared_ptr<MyStruct>, I*, deref_cmp<MyStruct>> mymap; 

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

आप कहते हैं कि करने के लिए इस

template <typename T> struct NullDeleter { 
    void operator()(T const*) const {} 
}; 
// needle being a MyStruct 
mymap.find(std::shared_ptr<MyStruct>(&needle,NullDeleter())); 

जरूरत नहीं की तरह एक तत्व को देखने चाहेंगे, तो इस अनुकूलन करने के लिए और अधिक संभावित है।