कैश दो मैट्रिक्स

Question

मैं कैश के अनुकूल विधि का उपयोग कर 2 मैट्रिक्स गुणा करने का इरादा गुणा करने के लिए अनुकूल विधि

(कि चूक की कम संख्या के लिए नेतृत्व करेंगे) मुझे पता चला है कि यह एक कैश अनुकूल पक्षांतरित समारोह के साथ किया जा सकता है ।

लेकिन मुझे यह एल्गोरिदम नहीं मिल रहा है। क्या मैं यह जान सकता हूं कि इसे कैसे प्राप्त किया जाए?

Answer 1

जो शब्द आप खोज रहे हैं वह थ्रैशिंग है। Google yields more results में थ्रैशिंग मैट्रिक्स गुणा के लिए खोज रहे हैं।

ग के लिए एक मानक गुणा एल्गोरिथ्म = एक * ख की तरह

void multiply(double[,] a, double[,] b, double[,] c) 
{ 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
      for (int k = 0; k < n; k++) 
       C[i, j] += a[i, k] * b[k, j]; 
} 

मूल रूप से विचार करेंगे, बड़े चरणों में तेजी स्मृति नेविगेट प्रदर्शन के लिए हानिकारक है। बी [के, जे] में के के लिए एक्सेस पैटर्न, जे] बिल्कुल ऐसा कर रहा है। तो बजाय स्मृति में चारों ओर कूद की, हम संचालन को पुनर्व्यवस्थित कर सकते हैं ऐसी है कि सबसे भीतरी छोरों केवल मैट्रिक की दूसरी पहुँच सूचकांक पर काम:

void multiply(double[,] a, double[,] B, double[,] c) 
{ 
    for (i = 0; i < n; i++) 
    { 
     double t = a[i, 0]; 
     for (int j = 0; j < n; j++) 
     c[i, j] = t * b[0, j]; 

     for (int k = 1; k < n; k++) 
     { 
     double s = 0; 
     for (int j = 0; j < n; j++) 
      s += a[i, k] * b[k, j]; 
     c[i, j] = s; 
     } 
    } 
} 

यह उदाहरण है कि पृष्ठ पर दिया गया था। हालांकि, दूसरा विकल्प बी [के, *] की सामग्री को पहले से एक सरणी में कॉपी करना है और आंतरिक सरणी गणनाओं में इस सरणी का उपयोग करना है। यह दृष्टिकोण आम तौर पर विकल्पों की तुलना में बहुत तेज़ विकल्प है, भले ही इसमें डेटा कॉपी करना शामिल हो। भले ही यह काउंटर-अंतर्ज्ञानी प्रतीत हो, भले ही आप अपने लिए प्रयास करें।

void multiply(double[,] a, double[,] b, double[,] c) 
{ 
    double[] Bcolj = new double[n]; 
    for (int j = 0; j < n; j++) 
    { 
     for (int k = 0; k < n; k++) 
      Bcolj[k] = b[k, j]; 

     for (int i = 0; i < n; i++) 
     { 
      double s = 0; 
      for (int k = 0; k < n; k++) 
       s += a[i,k] * Bcolj[k]; 
      c[j, i] = s; 
     } 
    } 
} 

Answer 2

@ सीज़र का जवाब सही नहीं है। उदाहरण के लिए, आंतरिक लूप

for (int k = 0; k < n; k++) 
    s += a[i,k] * Bcolj[k]; 

ए के i-th कॉलम के माध्यम से जाता है।

निम्नलिखित कोड यह सुनिश्चित करना चाहिए कि हम हमेशा पंक्ति से डेटा पंक्ति पर जाएं।

void multiply(const double (&a)[I][K], 
       const double (&b)[K][J], 
       const double (&c)[I][J]) 
{ 
    for (int j=0; j<J; ++j) { 
     // iterates the j-th row of c 
     for (int i=0; i<I; ++i) { 
     c[i][j] = 0; 
     } 

     // iterates the j-th row of b 
     for (int k=0; k<K; ++k) { 
      double t = b[k][j]; 
      // iterates the j-th row of c 
      // iterates the k-th row of a 
      for (int i=0; i<I; ++i) { 
      c[i][j] += a[i][k] * t; 
      } 
     } 
    } 
}