सी ++ push_back बनाम इन्सर्ट बनाम

Question

मैं वर्तमान में सी ++ के साथ वैक्टर का उपयोग कर एक आवेदन कर रहा हूं।

मुझे पता है कि पूर्व-अनुकूलन सभी बुराइयों की जड़ कैसे है।

लेकिन मैं वास्तव में उत्सुक होने में मदद नहीं कर सकता।

मैं अन्य वैक्टरों के हिस्सों को एक और वेक्टर में जोड़ रहा हूं।
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

:
हम कहूँगा वेक्टर एक आकार कि 300

की कभी नहीं परिवर्तन के बाद से मैं हमेशा वेक्टर

के अंत में संलग्न करना होगा यह तेजी से करने के लिए है

या वे वेक्टर के माध्यम से लूप करने के लिए तेज़ी से होंगे जो मैं जोड़ना चाहता हूं और push_back या emplace के साथ प्रत्येक आइटम को अलग-अलग जोड़ना चाहता हूं (अभी भी पहले से ही आरक्षित कर रहा हूं)। (अनिश्चित जो तेज है)

कोई भी इस पर मेरी सहायता कर सकता है?

Answer 1

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

तो, insertकम से कम तेजी से एक पाश में push_back के रूप में होना चाहिए। इस विशेष मामले में, insert का एक स्मार्ट कार्यान्वयन उन सभी तत्वों के लिए एक reserve कर सकता है जिन्हें आप सम्मिलित करना चाहते हैं। push_back हर बार वेक्टर की क्षमता की जांच करनी होगी। लाइब्रेरी को आउटमार्ट करने की कोशिश न करें :)

Answer 2

लार्समैन कहते हैं, जितना अधिक आप एक लाइब्रेरी कॉल में करते हैं, अधिक संभावना है कि यह अधिक कुशल हो। insert के मामले में वेक्टर में, लाइब्रेरी आमतौर पर लगभग पुन: आवंटन पर करेगी, और प्रत्येक स्थानांतरित तत्व को सबसे अधिक बार कॉपी करने के लिए। यदि आप लूप और push_back का उपयोग करते हैं, तो यह कई बार पुनः आवंटित कर सकता है, जो काफी धीमा हो सकता है ( परिमाण के क्रम की तरह)।

प्रकार के आधार पर, तथापि, यह भी तेजी से कुछ करने के लिए हो सकता है की तरह:

a.resize(300); 
std::copy(b.begin(), b.end(), a.end() - 300); 

मैंने पाया इस सरल अदिश प्रकार के लिए तेजी से होने के लिए (जैसे int) एक पर जी ++ का उपयोग करते हुए इंटेल मशीन

Answer 3

मुझे लगता है कि यह वास्तव में संकलक (लाइब्रेरी कार्यान्वयन), संकलन विकल्पों और वास्तुकला पर निर्भर करता है। इंटेल जिऑन पर अनुकूलन (/ ओवर ड्राफ्ट) के बिना VS2005 में एक त्वरित बेंचमार्क कर:

std::vector<int> a; 
std::vector<int> b; 

// fill 'a' with random values for giggles 

timer.start() 
// copy values from 'a' to 'b' 
timer.stop() 

मैं "कॉपी मूल्यों के इन विभिन्न तरीकों का उपयोग कर 10 000 000 मदों के लिए ये परिणाम प्राप्त ...":

'बी' के लिए
1. रिजर्व स्पेस दें, फिर के लिए लूप का उपयोग कर b.push_back(a[i]);: 0.808 सेकंड
2. आकार 'बी', तो के लिए लूप सूचकांक काम b[i] = a[i]; का उपयोग कर: 0.264 सेकंड
3. कोई फिर से आकार देने 'बी', बस b.insert(b.end(), a.begin(), a.end());: 0.021 सेकंड (आरक्षित पहले के साथ कोई महत्वपूर्ण अंतर)
4. std::copy(a.begin(), a.end(), std::back_inserter(b));: 0.944 सेकंड (0.871 आरक्षित पहले के साथ)
5. आकार 'बी', तो आधार संकेत memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int)); पर memcopy: 0.061 सेकंड
012,

ऑप्टिमाइज़ेशन चालू होने के साथ (/ ऑक्स) हालांकि, यह एक अलग कहानी है।

1. push_back पाश: मैं और अधिक भेदभाव प्राप्त करने के लिए 100 000 000 करने के लिए आकार बढ़ाने के लिए किया था .659 सेकंड
2. सूचकांक पाश: 0.482 सेकंड
3. डालने: 0.210 सेकंड (आरक्षित पहले के साथ कोई महत्वपूर्ण अंतर)
4. std :: प्रतिलिपि: पहले आरक्षित के साथ 0.422 सेकंड। इसके बिना एक bad_alloc मिला।
5. memcpy: 0.329 सेकंड

क्या नोट करने के लिए दिलचस्प है कि अनुकूलन के साथ या बिना, सम्मिलित विधि रैखिक बढ़ाया है। ऑप्टिमाइज़ेशन के बिना अन्य विधियां स्पष्ट रूप से अक्षम थीं लेकिन फिर भी उनके साथ उतनी तेज नहीं हो सका। जेम्स कन्ज़ ने नोट किया, यह जी ++ पर अलग है। सत्यापित करने के लिए अपने मंच के साथ एक परीक्षण चलाएं।