नेस्टेड वेक्टर बनाम संगत एरेज़ का प्रभाव प्रभाव

Question

क्या कोई विश्वसनीय परीक्षण है जो स्पष्ट रूप से नेस्टेड वैक्टरों को सी ++ के अंतर्निर्मित सरणी बनाम और लिखने के बीच प्रदर्शन अंतर प्रदर्शित करता है? मैंने सुना है कि नेस्टेड (बहु-आयामी) वैक्टरों का उपयोग आमतौर पर एक ही सरणी में तत्वों तक पहुंचने की तुलना में कुछ प्रदर्शन ओवरहेड होता है (जहां सभी तत्व संगत स्मृति में संग्रहीत होते हैं), लेकिन यह सब मेरे लिए काल्पनिक प्रतीत होता है। मुझे अभी तक कोई अंतर नहीं दिख रहा है जो वास्तव में इन मतभेदों को दिखाता है। क्या वे महत्वपूर्ण हैं? मुझे यकीन है कि यह परिदृश्य पर निर्भर करता है, लेकिन एक अनुभवहीन प्रोग्रामर के रूप में, मुझे पूरा यकीन नहीं है कि इन मतभेदों का स्तर कितना महत्वपूर्ण हो गया है।

Answer 1

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

मैं अनुकूलन के सामान्य नियम का पालन करता हूं, जो सबसे पहले चीजों को सबसे सरल तरीके से लिखना है और फिर जब आप साबित कर सकते हैं कि एक बाधा है तो अनुकूलन का प्रयास करें।

Answer 2

दो बातें नेस्टेड और चपटा सरणियों के बीच क्रम मतभेद के लिए योगदान:
कैशिंग व्यवहार और अविवेक

• सीपीयू कैश के एक पदानुक्रम का उपयोग सीधे बहुत जल्दी-जल्दी रैम तक पहुँचने से बचने के लिए। यह इस तथ्य का फायदा उठाता है कि अधिकांश मेमोरी एक्सेस संगत हैं या एक निश्चित अस्थायी इलाके है, यानी हाल ही में जो एक्सेस किया गया था, उसे जल्द ही एक्सेस किया जाएगा।
  इसका मतलब है कि यदि आपके नेस्टेड सरणी के भीतर के सरणी बड़े हैं, तो आप एक फ्लैट सरणी पर कोई अंतर नहीं देखेंगे यदि आप एक संगत फैशन में मानों को फिर से भरते हैं। इसका मतलब यह है कि जब फ्लैट सरणी के लिए मूल्यों की एक श्रृंखला पर पुनरावृत्ति होती है, तो आपके भीतर के लूप को घोंसले वाले सरणी के लिए लगातार तत्वों पर फिर से भरना चाहिए, आपके भीतर के लूप को सबसे निचले सरणी पर फिर से भरना चाहिए।
• यदि आपके एक्सेस पैटर्न यादृच्छिक हैं, तो समय में सबसे महत्वपूर्ण अंतर संकेत हैं:
  एक फ्लैट सरणी के लिए, आप A[(Z * M + Y) * N + X] जैसे कुछ का उपयोग करते हैं, इसलिए आप 4 अंकगणितीय परिचालन करते हैं और फिर स्मृति एक्सेस करते हैं।
  एक नेस्टेड सरणी के लिए, आप A[Z][Y][X] का उपयोग करते हैं, इसलिए वास्तव में तीन परस्पर निर्भर स्मृति पहुंच होती है: A[Z][Y] और इससे भी पहले आप A[Z] जान सकते हैं। आधुनिक सीपीयू के सुपरस्काकर आर्किटेक्चर की वजह से, समानांतर में निष्पादित किए जा सकने वाले संचालन विशेष रूप से कुशल, परस्पर निर्भर संचालन इतने ज्यादा नहीं होते हैं। तो आपके पास कुछ अंकगणितीय परिचालन और एक तरफ एक मेमोरी लोड है और दूसरी तरफ तीन परस्पर निर्भर भार है, जो काफी धीमी है। यह संभव हो सकता है कि के कुछ मूल्यों के लिए A और A[Z] की सामग्री कैश पदानुक्रम में पाई जा सकती है, लेकिन यदि आपका घोंसला वाला सरणी पर्याप्त रूप से बड़ा है, तो यह पूरी तरह से कैश में फिट नहीं होगा, इस प्रकार सरणी में एक ही यादृच्छिक अभिगम के लिए केवल एक कैश मिस और लोड (फ्लैट) की बजाय एकाधिक कैश मिस और मेमोरी लोड (नेस्टेड)।

इसके अलावा his question देखते हैं, कैशिंग (मेरा उत्तर) और अविवेक (पीटर जवाब) है, जो भी एक उदाहरण है जहां नेस्ट और फ्लैट सरणियों के बीच कोई उल्लेखनीय मतभेद देखते हैं प्रदान करता है की एक अधिक विस्तृत चर्चा के लिए नीचे दिए गए विशेष रूप से कम जवाब (निश्चित रूप से अनुक्रमण बग फिक्सिंग के बाद;))

तो अगर आप जानना चाहते हैं कि उन दोनों के बीच महत्वपूर्ण मतभेद हैं क्रम चाहते हैं, मेरा उत्तर होगा:

• आप रैंडम एक्सेस करते हैं, तो आप निश्चित रूप से होगा एकाधिक अप्रत्यक्ष नोटिस ओएनएस, इस प्रकार नेस्टेड सरणी के लिए एक बड़ा रनटाइम होता है।

• आप सन्निहित पहुँच और छोरों की सही आदेश (अंतरतम पाश = अंतरतम सरणी फ्लैट सरणी के लिए/अंतरतम इंडेक्स) और बहु-आयामी सरणी के अपने अंतरतम आयाम काफी बड़ी है का उपयोग करते हैं तो, अंतर लापरवाह होगा, क्योंकि संकलक आंतरिकतम लूप से सभी संकेतों को स्थानांतरित करने में सक्षम होगा।