在大矩陣中複製瓷磚的高效算法

我有N個方形矩陣，所有相同大小的MxM都必須複製到包含NxN矩陣的矩陣中，以對稱方式排列。上半部分和下半部分包含像這種方案中相同矩陣的轉置版本。在大矩陣中複製瓷磚的高效算法

N = 4

m1 m2 m3 m4 
m2'm1 m2 m3 
m3'm2'm1 m2 
m4'm3'm2'm1

產生數據最初填充只在上排和第一列，留下其餘的空的算法。

m1 m2 m3 m4 
m2'0 0 0 
m3'0 0 0 
m4'0 0 0

我想找到一個有效的索引方案，以填補所有這一切已經被填充線的元素開始大矩陣。請記住，m1 ... mn是MxM大小的矩形矩陣，並且該矩陣按列主要順序排列。矩陣不是那麼大，所以不需要利用很多地方和緩存相關的東西。

平凡算法如下所示，其中X是矩陣。

int toX = 0, fromX = 0, toY = 0, fromY = 0; 
    for (int i = 1; i < N; ++i) { 
    for (int j = 1; j < N; ++j) { 
     for (int ii = 0; ii < M; ++ii) { 
     for (int jj = 0; jj < M; ++jj) { 
      fromX = (i - 1) * dim + ii; 
      fromY = (j - 1) * dim + jj; 
      toX = i * dim + ii; 
      toY = j * dim + jj; 
      X(toX, toY) = X(fromX, fromY); 
     } 
     } 
    } 
    }

你能找到更好的方法嗎？

來源

2011-02-17 Alex Darsonik

大矩陣將充滿了從較小的矩陣拍攝元素其中前幾列將包含按行主排列的第一個矩陣的所有元素，這是我的理解正確？ – 2011-02-17 11:05:33

根據您的應用程序，可能沒有必要存儲所有這些轉置的矩陣。如果m1是對稱的，你甚至可以剔除m1矩陣的下半部分。

事實上，它甚至可能是獨自離開所有這些矩陣，做你的矩陣運算逐塊可行的（加法和乘法與標量簡單，乘用載體將是一個比較複雜一點）

如果你真的需要整個矩陣，你可能會被對角填充基質，通過做這樣的事情，即獲得一個略低操作計數：

int toX = 0, fromX = 0, toY = 0, fromY = 0; 

// m1 (note that this part can be sped up further if m1 is symmetric) 

for (int ii = 0; ii<M; ii++){   
    for (int jj = 0; jj<M; jj++){ 
     fromX = ii; 
     fromY = jj; 
     toX = fromX; 
     toY = fromY; 
     for (int k=1; k<N; k++){    
      toX += dim; 
      toY += dim; 
      X(toX, toY) = X(fromX, fromY); 
     }    
    }   
}  


// m2 to m(N-1) 

for (int i = 2; i < N; i++){  
    for (int ii = 0; ii<M; ii++){   
     for (int jj = 0; jj<M; jj++){ 
      fromX = i*dim+ii; 
      fromY = jj; 
      toX = fromX; 
      toY = fromY; 
      for (int k=i; k<N; k++){    
       toX += dim; 
       toY += dim; 
       X(toX, toY) = X(fromX, fromY); 
       X(toY, toX) = X(fromX, fromY); 
      }    
     }   
    }  
}

來源

2011-02-17 12:58:13 toochin

在大矩陣中複製瓷磚的高效算法

回答

相關問題