वेक्टर या मानचित्र, जिसका उपयोग करने के लिए?

Question

मैंने कई लोगों को यह कहते हुए सुना है कि अगर कंटेनर में अपेक्षित तत्वों की संख्या अपेक्षाकृत छोटी है तो के बजाय std::vector का उपयोग करना बेहतर है, हालांकि मैं केवल लुकअप के लिए कंटेनर का उपयोग करता हूं और पुनरावृत्ति के लिए नहीं।

इसके पीछे असली कारण क्या है?

स्पष्ट रूप से मानचित्र का लुकअप प्रदर्शन वेक्टर की तुलना में भी बुरा नहीं हो सकता है (हालांकि यह नैनोसेकंड/माइक्रोसॉन्ड में हो सकता है) तो क्या इसका उपयोग स्मृति उपयोग के साथ कुछ करना है?

क्या वेक्टर वर्चुअल एड्रेस स्पेस के खंडन में मानचित्र से बेहतर/खराब है?

मैं एसटीएल लाइब्रेरी का उपयोग कर रहा हूं जो विजुअल स्टूडियो (यानी माइक्रोसॉफ्ट कार्यान्वयन) के साथ आता है जो अन्य कार्यान्वयन से कोई फर्क पड़ता है?

Answer 1

मुझे लगता है कि आप map<A, B> की तुलना vector<pair<A, B> > के साथ कर रहे हैं।

सबसे पहले, एक बहुत छोटे वेक्टर में एक आइटम ढूंढना मानचित्र में एक ही चीज़ से आसानी से तेज़ हो सकता है, क्योंकि वेक्टर में सभी मेमोरी हमेशा संगत होती है (और इसलिए कंप्यूटर के कैश और ऐसी चीजों के साथ अधिक अच्छी तरह से खेलती है) , और वेक्टर में कुछ खोजने के लिए आवश्यक तुलना की संख्या मानचित्र के समान ही हो सकती है। मानचित्र में तत्व ढूंढना बहुत बड़े कंटेनरों की सीमा में कम परिचालन की आवश्यकता है।

वह बिंदु जहां नक्शे वैक्टर से तेज़ हो जाते हैं, आपके प्रोसेसर पर, मानचित्र में कौन सा डेटा है, और प्रोसेसर के कैश में स्मृति की तरह सूक्ष्म चीजों पर निर्भर करता है। आम तौर पर, वह बिंदु जहां नक्शा तेजी से हो जाता है, लगभग 5-30 तत्व होंगे।

एक हैश कंटेनर का उपयोग करने का एक विकल्प है। उन्हें अक्सर hash_map या unordered_map नाम दिया जाता है। hash_map नाम की कक्षाएं आधिकारिक मानक का हिस्सा नहीं हैं (और वहां कुछ प्रकार हैं); std::tr1::unordered_map है। एक हैश नक्शा अक्सर लुकअप के लिए सामान्य मानचित्र से तेज़ होता है, इस पर ध्यान दिए बिना कि इसमें कितने तत्व हैं, लेकिन चाहे यह वास्तव में तेज़ है कि कुंजी क्या है, यह कैसे धोया जाता है, आपको किस मूल्य से निपटना है, और कैसे कुंजी की तुलना std :: मानचित्र में की जाती है। यह चीजों को std :: मानचित्र जैसे विशिष्ट क्रम में नहीं रखता है, लेकिन आपने कहा है कि आपको इसकी परवाह नहीं है। मैं हैश मैप्स को विशेष रूप से अनुशंसा करता हूं अगर चाबियाँ पूर्णांक या पॉइंटर्स हों, क्योंकि ये हैश बहुत जल्दी है।

Answer 2

मानचित्र आमतौर पर बाइनरी खोज पेड़ों के रूप में लागू होते हैं, और एक बाइनरी पेड़ चलना हमेशा थोड़ा ओवरहेड (तुलना करने, लिंक चलने आदि) के साथ आता है। वेक्टर मूल रूप से केवल सरणी होते हैं। बहुत कम मात्रा में डेटा के लिए, शायद 8 या 12 तत्व, कभी-कभी यह एक बाइनरी खोज पेड़ चलने के बजाय सरणी पर एक रैखिक खोज करने के लिए तेज़ होता है।

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

मैप्स तो वैक्टर की कैश प्रभावित दर कभी कभी ऐसे मामलों में जहां आप सामने से सभी तत्वों से अधिक पुनरावृत्ति कर रहे हैं में एक छोटे से बेहतर हो सकता है, सब ढेर से अधिक छोटे आवंटन का एक समूह है करने के लिए वैक्टर सन्निहित हैं, जबकि करते हैं समर्थन करना।

Answer 3

यदि आप एक बार में अपने सभी प्रविष्टियां कर रहे हैं तो बहुत सारे लुकअप कर रहे हैं, तो आप वेक्टर का उपयोग कर सकते हैं और जब आप डालने के माध्यम से इसे सॉर्ट कर सकते हैं; फिर त्वरित लुकअप करने के लिए निचला_बाउंड का उपयोग करें। यह बड़ी संख्या में वस्तुओं के लिए भी मानचित्र का उपयोग करने से तेज़ हो सकता है।

Answer 4

मुझे लगता है कि आपको उस कंटेनर का उपयोग करना चाहिए जो पहले और सबसे महत्वपूर्ण डेटा को फिट करे। std :: vector उन स्थितियों में उपयोग किया जाता है जहां आप सी या प्री-एसटीएल सी ++ में एक सरणी का उपयोग करेंगे: आप तेजी से निरंतर समय के साथ मूल्यों को स्टोर करने के लिए स्मृति का एक संगत ब्लॉक चाहते हैं। std :: मानचित्र को मानों के लिए कुंजी मैप करने के लिए उपयोग किया जाना चाहिए। यहां प्राथमिक ओवरलैप एक वेक्टर बनाम एक नक्शा बनाम आकार के साथ आकार के रूप में है। उस मामले में दो चिंताएं हैं: इंडेक्स निरंतर हैं? यदि नहीं, तो आप शायद वेक्टर के साथ स्मृति बर्बाद कर देंगे। दूसरा, आप क्या दिखने का समय चाहते हैं? एक वेक्टर में निरंतर समय लुकअप होता है, जबकि std :: map को आम तौर पर आरबी पेड़ के रूप में कार्यान्वित किया जाता है, जिसमें ओ (लॉग एन) लुक-अप टाइम होता है, और यहां तक ​​कि हैश मैप (जैसे TR1 unordered_map) आमतौर पर एक खराब जटिलता होती है, क्योंकि इंडेक्स (या उसके हैश) को एक बाल्टी में मैप किया जाएगा जिसमें कई मान हो सकते हैं।

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

वैसे भी, डेटा को स्पष्ट तरीके से मॉडल करने का प्रयास करें। समयपूर्व अनुकूलन अक्सर ज्यादा मदद नहीं करता है।

Answer 5

"डिफ़ॉल्ट रूप से, जब आपको कंटेनर की आवश्यकता होती है तो वेक्टर का उपयोग करें" - Bjarne Stroustrup।

अन्यथा, मैं बहुत अच्छा सहायक हो करने के लिए इस छोटे प्रवाह चार्ट पाते हैं:

http://homepages.e3.net.nz/~djm/cppcontainers.html

Answer 6

एक और तरीका है इस को देखने के लिए, अगर हम, छोटे कंटेनरों के बारे में बात कर रहे हैं तो दोनों में से कोई जा रहा है देखने के लिए बहुत लंबा समय लगता है। जब तक आप इस कंटेनर को बहुत तंग पाश पर नहीं खोज रहे हैं, तो समय में अंतर शायद नगण्य होगा।

उस स्थिति में, मैं देखता हूं कि कौन सा कंटेनर आप जो करना चाहते हैं उससे अधिक बारीकी से मेल खाता है। यदि आप किसी विशेष मूल्य की तलाश में हैं, तो नक्शा की अंतर्निहित खोज() विधि लूप बनाने और वेक्टर पर पुनरावृत्ति करने से बहुत आसान (और उपयोग करने में कम जटिल) होगी।

आप समय और यहां कुछ नैनो-सेकंड से अधिक समय के लायक हैं।

Answer 7

मूल रूप से, मानचित्र देखने के लिए उपयोग किए जाते हैं।

लेकिन, कभी-कभी std::vector का उपयोग std::map के बजाय भी देखने के लिए किया जा सकता है।

यदि आपके कुंजी-मूल्य जोड़े में बहुत कम तत्व होने जा रहे हैं, तो आप std::vector<std::pair<x,y>> में भी कुंजी का उपयोग करके एक पुनरावृत्ति खोज के लिए जा सकते हैं।

यह इस तथ्य के कारण है कि हैशिंग में समय लगता है, खासकर हैशिंग स्ट्रिंग्स और मानचित्र में अन्य परिचालनों के लिए ढेर में डेटा संग्रहीत करना।

आप केवल std :: map में बेहतर अंतर देखेंगे, यदि आपके पास अधिक तत्व हैं जिसमें आपको देखना है और जब आप अपने तत्वों की सूची में लगातार खोज करना चाहते हैं।