सी ++ वेक्टर बनाम ऐरे (समय)

Question

मुझे मेरे साथ दो कार्यक्रम मिल गए हैं, दोनों एक ही काम कर रहे हैं। वे सिर्फ मूल्य के लिए एक बुलियन सरणी/वेक्टर सेट कर रहे हैं। वेक्टर का उपयोग करने वाले कार्यक्रम को चलाने के लिए 27 सेकंड लगते हैं जबकि 5 गुना अधिक आकार वाले सरणी वाले प्रोग्राम में 1 से कम समय लगता है। मैं इस सटीक कारण को जानना चाहता हूं कि ऐसा बड़ा अंतर क्यों है? क्या वेक्टर वास्तव में अक्षम हैं?

प्रोग्राम का उपयोग वैक्टर

#include <iostream> 
#include <vector> 
#include <ctime> 

using namespace std; 

int main(){ 
const int size = 2000; 
time_t start, end; 
time(&start); 
vector<bool> v(size); 
for(int i = 0; i < size; i++){ 
    for(int j = 0; j < size; j++){ 
    v[i] = true; 
    } 
} 
time(&end); 
cout<<difftime(end, start)<<" seconds."<<endl; 
} 

रनटाइम - 27 सेकंड

प्रोग्राम का उपयोग सरणी

#include <iostream> 
#include <ctime> 

using namespace std; 

int main(){ 
const int size = 10000; // 5 times more size 
time_t start, end; 
time(&start); 
bool v[size]; 
for(int i = 0; i < size; i++){ 
    for(int j = 0; j < size; j++){ 
    v[i] = true; 
    } 
} 
time(&end); 
cout<<difftime(end, start)<<" seconds."<<endl; 
} 

रनटाइम - < 1 सेकंड

प्लेटफार्म - विजुअल स्टूडियो 2008 ओएस - विंडोज विस्टा 32 बिट एसपी 1 प्रोसेसर इंटेल (आर) पेंटियम (आर) दोहरी सीपीयू T2370 @ 1.73GHz मेमोरी (RAM) 1.00 जीबी

धन्यवाद

खुशी के लिए खोज

Answer 1

आप std :: bool के वेक्टर का उपयोग कर रहे हैं और ऐसा नहीं है कि आप क्या सोचते हैं!

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

Click here for some info on vector of bool.

इसके अलावा, आप एक unoptimized निर्माण चल रहा जा सकता है (लगभग निश्चित रूप से कई बार आप सूचीबद्ध दिया, 27 सेकंड 4 लाख पुनरावृत्तियों के लिए अपमानजनक है)। मानक टेम्पलेट लाइब्रेरी इनलाइन फ़ंक्शन कॉल और एलिइड अस्थायी जैसे चीजों को करने के लिए ऑप्टिमाइज़र पर बहुत अधिक निर्भर करती है। इस अनुकूलन की कमी से बूल के वेक्टर के लिए विशेष रूप से भारी प्रदर्शन गिरावट आती है क्योंकि जब आप इसमें अनुक्रमण करते हैं तो उसे प्रॉक्सी ऑब्जेक्ट वापस करना पड़ता है, क्योंकि आप थोड़ा सा पता नहीं ले सकते हैं, इसलिए ऑपरेटर [] वापस नहीं आ सकता संदर्भ।

Click here for more info on proxied containers

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

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

मैं अपने पाश ज्यादा मेरी मशीन पर परीक्षण करने के लिए बड़ा करना था, लेकिन यहाँ दो मेरी मशीन पर bool लूप के अपने वेक्टर के बनाता है, एसटीएल कोड पर अनुकूलक झंडे के प्रभाव

$ g++ main.cpp 
$ ./a.out 
17 seconds. 
$ g++ -O2 main.cpp 
$ ./a.out 
1 seconds. 

Answer 2

एक है दिखा है इस

Using arrays or std::vectors in C++, what’s the performance gap?

Answer 3

अन्य उत्तर को देखने के बहुत अच्छे हैं, लेकिन आप आसानी से इसे अपने आप को this method द्वारा जवाब दे।

जोड़ा गया: टिप्पणियों के जवाब में, मैं आपको बताता हूं कि मेरा क्या मतलब है। मैं विंडोज़ पर वीसी चला रहा हूं, लेकिन यह किसी भी भाषा/ओएस पर काम करता है। मैंने अपना पहला कार्यक्रम और 20000 तक आकार बढ़ाया ताकि यह काफी देर तक चल सके। फिर जब यह चल रहा था, मैंने कई स्टैकशॉट लिया। वे सभी इस तरह दिखेगा:

std::vector<bool,std::allocator<bool> >::begin() line 93 + 25 bytes 
std::vector<bool,std::allocator<bool> >::operator[]() line 132 + 37 bytes 
main() line 24 + 12 bytes 
mainCRTStartup() line 206 + 25 bytes 
KERNEL32! 7c817077() 

तो क्या है कि कहना है कि यह अनिवार्य रूप से खर्च कर रहा है यह सभी लाइन 24 पर अनुक्रमण ऑपरेशन में समय आ गया है, और कारण यह है कि समय बिताने है कि [] ऑपरेटर है है begin ऑपरेटर को कॉल करना। और अधिक विस्तार से:

for(int j = 0; j < size; j++){ 
==> v[i] = true; 
} 

कि कॉल:

main() line 24 + 12 bytes 

इस कोड है

std::vector<bool,std::allocator<bool> >::operator[]() line 132 + 37 bytes 

जो इस कोड है (है कि मैं एक छोटा सा पुन: स्वरूपित):

reference operator[](size_type _P){ 
==> return (*(begin() + _P)); 
} 

जो कॉल करता है:

std::vector<bool,std::allocator<bool> >::begin() line 93 + 25 bytes 

जो (और अधिक विस्तार में) इस कर रही है:

92:  iterator begin() 
93:   {return (_First); } 
00402890 push  ebp 
00402891 mov   ebp,esp 
00402893 sub   esp,44h 
00402896 push  ebx 
00402897 push  esi 
00402898 push  edi 
00402899 push  ecx 
0040289A lea   edi,[ebp-44h] 
0040289D mov   ecx,11h 
004028A2 mov   eax,0CCCCCCCCh 
004028A7 rep stos dword ptr [edi] 
004028A9 pop   ecx <=============== 
004028AA mov   dword ptr [ebp-4],ecx 
004028AD mov   eax,dword ptr [ebp-4] 
004028B0 mov   eax,dword ptr [eax+4] 
004028B3 pop   edi 
004028B4 pop   esi 
004028B5 pop   ebx 
004028B6 mov   esp,ebp 
004028B8 pop   ebp 
004028B9 ret 

क्या यह क्या कर रही है 0xCC के 68 बाइट्स (कुछ डिबग कारण के लिए) स्टैक पर लिख रहा है की begin पता हो रही है के भाग के रूप असाइनमेंट करने से पहले v[i] के पते की गणना करने के हिस्से के रूप में वेक्टर।

यह करने का समय 100% के करीब है, क्योंकि यह कई नमूने में से प्रत्येक पर किया जा रहा था। क्या आप अनुमान लगा सकते हैं कि यह लगभग हर समय अपना खर्च कर रहा था? मैं नहीं कर सका।

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

तो - लोग आपको बता सकता है क्या यह कर हो सकता है, लेकिन यह पता चलता खुद के लिए पता लगाने के लिए यह क्या वास्तव में कर रही है।

आपके पर्यावरण पर यह निस्संदेह अलग होगा।

Answer 4

std::vector<bool> प्रदर्शन की बजाय स्मृति खपत के लिए अनुकूलित किया गया है।

आप std::vector<int> का उपयोग करके इसे चालित कर सकते हैं। तब आपके पास प्रदर्शन की कमी नहीं होनी चाहिए।