यह प्रदर्शन में सुधार क्यों करता है?

Question

मेरे पास लूप के लिए दो हैं जो मूल रूप से दो अलग-अलग सरणी में दिखते हैं (प्रत्येक में चोटी पर 2-4k आकार होता है) और इन मानों के आधार पर एक 3 सरणी में मान सेट करें। कुछ अजीब कारणों के लिए कोड के इस टुकड़े के प्रदर्शन के बीच एक कारक दो अंतर है, जिस पर मैं दो लूप के लिए दो ऑर्डर देता हूं।

यह पहला सेटअप है। यह 150 में ~ मेरी पीसी पर मिलीसेकेंड कार्यान्वित:

public static int[] SchoolMultiplication(int[] a, int[] b, int numberBase) 
{ 
    List<double> times = new List<double>(); 
    TimeTest timeTest = new TimeTest(); 

    int aLen = a.Length; 
    int bLen = b.Length; 

    int[,] resultMatrix = new int[a.Length + b.Length, aLen]; 
    int[] result = new int[a.Length + b.Length]; 

    timeTest.Start(); 

    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
    { 
     for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 

     { 
      resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
     } 
    } 

अब अगर मैं इस

for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 
{ 
    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
{ 
     resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
    } 
} 

की तरह लेकिन छोरों के आदेश में कुछ भी नहीं बदल विधि के कुल समय चल रहा है के बारे में ~ 400 मिलीसेकेंड के लिए चला जाता है । लूप ऑर्डर का एक सरल विनिमय लगभग 300% तक प्रदर्शन में सुधार कैसे करता है? मुझे लगता है कि यह किसी प्रकार का कैशिंग या पॉइंटर प्रदर्शन की बात है?

Answer 1

यह एक डेटा व्यवस्था की बात है। स्मृति के बारे में एक आयाम सरणी के रूप में सोचें। इस तरह डिस्क पर वास्तव में चीजें व्यवस्थित की जाती हैं (जहां तक ​​कंप्यूटर का संबंध है।) इसलिए जब आप बहु-आयाम सरणी बनाते हैं, जब आप लूप ऑर्डर बदलते हैं तो आप बदलते हैं कि सरणी कैसे घुमाया जाता है। क्रम में पढ़ने के बजाय, आप स्थिति से स्थिति में कूद रहे हैं।

---

एक बहु आयाम सरणी आप के लिए इस तरह दिखता है:

और कंप्यूटर के लिए इस तरह। traversing के इष्टतम तरीका नीचे तीर निम्नलिखित अनुक्रमित है:

तो जब आप बदलते हैं तो आप सरणी सरणी पाशन इस तरह चल रहा है:

इस प्रकार आप अधिक कैश छूट जाए मिलता है और एक गरीब प्रदर्शन कर एल्गोरिथ्म ।

Answer 2

यह कैश हिट/मिस से संबंधित होने की संभावना है। अंतर अनुक्रमिक बनाम बिखरी हुई पहुंच में निहित है जो एक कैश लाइन के आकार के ऊपर आकार में है।

सादा सी ++ लूप के लिए, यह लूप पर थोड़ा प्रदर्शन करने के लिए लूप को पीछे की ओर लाने में भी मदद करेगा। यह सुनिश्चित नहीं है कि यह .NET के लिए कैसे फिट बैठता है।

Answer 3

लोकैलिटी, इलाके, डेटा की इलाके। विकिपीडिया (जो बेहतर कहते हैं की तुलना में मैं होता) से:

रैखिक डेटा संरचनाओं: क्योंकि कोड छोरों कि सूचकांक द्वारा सरणियों या अन्य डेटा संरचना को संदर्भित करने के लिए करते हैं शामिल इलाका अक्सर तब होता है। अनुक्रमिक इलाके, स्थानिक इलाके का एक विशेष मामला तब होता है जब प्रासंगिक डेटा तत्व व्यवस्थित होते हैं और रैखिक रूप से उपयोग किए जाते हैं। उदाहरण के लिए, आधार पते से उच्चतम तत्व तक, एक-आयामी सरणी में तत्वों का सरल ट्रैवर्सल स्मृति में सरणी के अनुक्रमिक इलाके का उपयोग करेगा। [2] अधिक सामान्य समतुल्य इलाका तब होता है जब रैखिक ट्रैवर्सल समान संरचना और आकार वाले समेकित डेटा संरचनाओं के लंबे क्षेत्र से अधिक होता है, और इसके अतिरिक्त, पूरे ढांचे तक पहुंच नहीं है, बल्कि संरचनाओं के पारस्परिक रूप से समान तत्व हैं। यह वह मामला है जब मैट्रिक्स को पंक्तियों के क्रमिक मैट्रिक्स के रूप में दर्शाया जाता है और आवश्यकता है मैट्रिक्स के एक कॉलम तक पहुंचना।

Answer 4

मुझे Code Complete में इसके बारे में पढ़ना याद है।अधिकांश भाषाओं में, सरणी अनुक्रमिक रूप से सेट की गई अंतिम इंडेक्स के साथ स्थापित की जाती हैं, ताकि आप पहले इंडेक्स पर फिर से घुमाए जाने के बजाय, पिछले इंडेक्स पर पुनरावृत्ति करते समय बाइट्स को सीधे पंक्ति में एक्सेस कर रहे हों।

Answer 5

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

Fastest way to loop through a 2d array?

लेकिन, shhhh हम प्रदर्शन सही के बारे में परवाह नहीं करना पड़ेगा? :)

Answer 6

मैं यह भी सोचूंगा कि एरे और बी के सापेक्ष आकार में अंतर आएगा।

यदि कोई। लम्बाई बड़ा है और बी। लम्बाई छोटा है, तो दूसरा विकल्प तेज़ होना चाहिए। इसके विपरीत, यदि कोई। लम्बाई छोटा है और बी। लम्बाई बड़ा है, तो पहला विकल्प तेज़ होगा। समस्या आंतरिक लूप की सेटअप/टियरडाउन लागत से परहेज कर रही है।

Btw, तुम क्यों है

पूर्णांक एलेन = a.Length करते हैं;

लेकिन फिर भी एक तरंग सीधे कॉल करें? ऐसा लगता है कि आपको एक या दूसरे को चुनना चाहिए।