push_back

Question

मैं एक सी ++ दिनचर्या अनुकूलित करने की कोशिश कर रहा हूं। इस दिनचर्या में मुख्य बाधा वस्तुओं के वेक्टर के push_back() है। मैंने इसके बजाय एक डेक का उपयोग करने की कोशिश की और यहां तक ​​कि एक सूची की कोशिश की। लेकिन अजीब तरह से (और सिद्धांत के विपरीत) डेक और सूची कार्यान्वयन वेक्टर समकक्ष की तुलना में बहुत धीमी गति से चलते हैं।

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

कोई बात नहीं?

नोट: वेक्टर रिजर्व() कार्यान्वयन को बढ़ा सकता था लेकिन आकार में अज्ञात होने के कारण नहीं किया जा सकता है।

धन्यवाद।

Answer 1

क्या आप ऑब्जेक्ट्स को खुद को वापस दबा रहे हैं, या उनके लिए एक पॉइंटर? प्वाइंटर्स आमतौर पर बहुत तेज़ होंगे क्योंकि ऑब्जेक्ट्स के आकार की तुलना में कॉपी करने के लिए केवल 4-8 बाइट्स हैं।

Answer 2

आपको दिनचर्या के व्यवहार पर अधिक जानकारी देना होगा।

एक स्थान पर आप push_back() की गति के बारे में चिंतित हैं, आप clear() के बारे में चिंतित हैं। क्या आप कंटेनर बना रहे हैं, फिर कुछ डंप कर रहे हैं?

परिणाम आप clear() के लिए देखते हैं क्योंकि vector<> केवल स्मृति का एक singl ब्लॉक जारी करने के लिए है, deque<> कई रिलीज करने के लिए है, और list<> प्रत्येक तत्व के लिए एक रिलीज करने के लिए है रहे हैं।

Answer 3

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

Answer 4

डेक या सूची की तुलना में निर्माण या स्पष्ट करने के लिए वेक्टर तेजी से होने की उम्मीद है; यह एक सरल डेटा संरचना है।

1. जांच पर्याप्त के लिए वेक्टर बड़ा है नया आइटम पकड़:

   vector::push_back के संबंध में, यह दो काम करने की है।

2. नया आइटम डालें।

आप आम तौर पर चीजों को बस वेक्टर आकार बदलने और आइटम स्थापित करने के लिए operator[] का उपयोग करके चरण 1 को नष्ट करने से तेजी लाने के कर सकते हैं।

अद्यतन: मूल पोस्टर ने एक उदाहरण के लिए कहा। बार 128 मेगा सम्मिलन, और आउटपुट

push_back   : 2.04s 
reserve & push_back : 1.73s 
resize & place  : 0.48s 

नीचे कोड जब संकलित और जी ++ -O3 एक पुराने पी 4 मशीन पर Debian/लेनी पर साथ चलाते हैं।

#include <iostream> 
#include <time.h> 
#include <vector> 

int main(int,char**) 
{ 
    const size_t n=(128<<20); 

    const clock_t t0=clock(); 
    { 
    std::vector<unsigned char> a; 
    for (size_t i=0;i<n;i++) a.push_back(i); 
    } 
    const clock_t t1=clock(); 
    { 
    std::vector<unsigned char> a; 
    a.reserve(n); 
    for (size_t i=0;i<n;i++) a.push_back(i); 
    } 
    const clock_t t2=clock(); 
    { 
    std::vector<unsigned char> a; 
    a.resize(n); 
    for (size_t i=0;i<n;i++) a[i]=i; 
    } 
    const clock_t t3=clock(); 

    std::cout << "push_back   : " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 
    std::cout << "reserve & push_back : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 
    std::cout << "resize & place  : " << (t3-t2)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 

    return 0; 
} 

Answer 5

push_back() धीमी गति से किया जा रहा है और रिजर्व कोई मदद नहीं किया जा रहा है के बारे में, MSVC में इस्तेमाल एसटीएल के कार्यान्वयन कुछ इस तरह काम करता है: मैं 10 तत्वों लगता है के लिए जब आप पहली बार एक वेक्टर यह अंतरिक्ष के पास सुरक्षित बना सकते हैं। तब से, जब भी यह पूरा हो जाता है, यह वेक्टर में तत्वों की संख्या 1.5 गुणा के लिए जगह सुरक्षित रखता है। तो, 10, 15, 22, 33, 49, 73, 105, 157 की तरह कुछ ... पुन: आवंटन महंगा है।

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

आपको यह सुनिश्चित करने के लिए रिलीज मोड में प्रोफ़ाइल की आवश्यकता है कि कौन सी रणनीति सर्वोत्तम काम करती है।

Answer 6

यदि आप नहीं जानते कि आप कितनी ऑब्जेक्ट जोड़ रहे हैं तो इष्टतम समाधान के साथ आने में बहुत मुश्किल है। आप जो भी कर सकते हैं वह लागत कम करने की कोशिश कर रहा है जो आप जानते हैं - जो इस मामले में है कि आपका वेक्टर लगातार बदल रहा है।

आप इसे दो तरीकों से कर सकते हैं;

1) अपने ऑपरेशन को भवन और अंतिम रूप देने के लिए विभाजित करें। यह वह जगह है जहां आप एक वेक्टर में सूची बनाते हैं जो पर्याप्त होने की गारंटी है और जब इसे किसी अन्य वेक्टर में कॉपी किया जाता है।

उदा।

std::vector<Foo> hugeVec; 
hugeVec.reserve(1000); // enough for 1000 foo's 

// add stuff 

std::vector<Foo> finalVec; 
finalVec = hugeVec; 

2) वैकल्पिक रूप से, जब आपका वेक्टर ऑब्जेक्ट्स के दूसरे सेट के लिए पर्याप्त कॉल रिजर्व होता है;

if (vec.capacity() == vec.size()) 
    vec.reserve(vec.size() + 16); // alloc space for 16 more objects 

आप एक अलग कंटेनर कि सभी तत्वों को एक आकार बदलने पर कॉपी की जा रही प्रदान न करने के लिए चुन सकते हैं, लेकिन अपने टोंटी तो नए तत्व के लिए व्यक्तिगत स्मृति आवंटन हो सकता है।

Answer 7

यदि आप वेक्टर तेज होना चाहते हैं, तो आपको पर्याप्त स्थान आरक्षित करना होगा। यह एक बड़ा अंतर बनाता है, क्योंकि प्रत्येक बढ़ता महंगा है। यदि आप नहीं जानते हैं, तो एक अच्छा अनुमान लगाओ।

Answer 8

यदि किसी ऑब्जेक्ट की प्रति धीमी है तो "push_back()" धीमा हो सकता है। यदि डिफ़ॉल्ट कन्स्ट्रक्टर तेज़ है और आपके पास प्रतिलिपि से बचने के लिए स्वैप का उपयोग करने का कोई तरीका है, तो आपके पास बहुत तेज़ प्रोग्राम हो सकता है।

void test_vector1() 
{ 
    vector<vector<int> > vvi; 
    for(size_t i=0; i<100; i++) 
    { 
     vector<int> vi(100000, 5); 
     vvi.push_back(vi); // copy of a large object 
    } 
} 

void test_vector2() 
{ 
    vector<int> vi0; 
    vector<vector<int> > vvi; 
    for(size_t i=0; i<100; i++) 
    { 
     vector<int> vi(100000, 5); 
     vvi.push_back(vi0); // copy of a small object 
     vvi.back().swap(vi); // swap is fast 
    } 
} 

परिणाम:

VS2005-debug 
* test_vector1 -> 297 
* test_vector2 -> 172 

VS2005-release 
* test_vector1 -> 203 
* test_vector2 -> 94 

gcc 
* test_vector1 -> 343 
* test_vector2 -> 188 

gcc -O2 
* test_vector1 -> 250 
* test_vector2 -> 156 

Answer 9

आप आप इसके साथ क्या करने जा रहे हैं के अनुसार अपने कंटेनर चुनना है।

प्रासंगिक कार्य हैं: विस्तार (push के साथ), सम्मिलन (सभी की आवश्यकता नहीं हो सकती है), निष्कर्षण, हटाना।

cplusplus.com पर, प्रति कंटेनर प्रकार के संचालन का एक बहुत अच्छा अवलोकन है।

यदि ऑपरेशन push -बाउंड है, तो यह समझ में आता है कि वेक्टर अन्य सभी को धड़कता है। डेक के बारे में अच्छी बात यह है कि यह निश्चित भाग आवंटित करता है, इसलिए खंडित स्मृति का अधिक कुशल उपयोग करेगा।