C語言行優(yōu)先和列優(yōu)先的問題深入分析

摘要

本文主要探討的是“行優(yōu)先”原則和“列優(yōu)先”原則的問題。

1. 背景

首先了解“行優(yōu)先”和“列優(yōu)先”的知識，這兩種方式在數(shù)學上的直觀描述如下，給定如下矩陣：

根據(jù)行優(yōu)先的原則，其排序方式為

根據(jù)列優(yōu)先的原則，其排序方式為

2. 計算機領域的應用

行列優(yōu)先原則在計算機領域的應用主要如下。行優(yōu)先或者列優(yōu)先沒有好壞，但其直接涉及到對內存中數(shù)據(jù)的最佳存儲訪問方式。因為在內存使用上，程序訪問的內存地址之間連續(xù)性越好，程序的訪問效率就越高；相應地，程序訪問的內存地址之間連續(xù)性越差。所以，我們應該盡量在行優(yōu)先機制的編譯器，比如C/C++，CUDA等等上，采用行優(yōu)先的數(shù)據(jù)存儲方式；在列優(yōu)先機制的編譯器，比如Fortune, Matlab等等上，采用列優(yōu)先的數(shù)據(jù)存儲方式。但這種思想滲透到編程中之后，代碼的質量就會提高一個檔次。

3. 以矩陣計算為例（Matlab編譯器下測試）

% data 
A = [ 1 1 
   2 2 
   3 3  
   4 4 
   5 5 
   6 6 
   7 7 
   8 8 
   9 9]; 
B = [ 1 2 3 4 5 6 7 8 9 
   1 2 3 4 5 6 7 8 9]; 
C = zeros(9,9); 
 
% The method of matrix multiplication in Matlab 
tic  
C = A*B; 
toc 
 
 
%　Our impletation method of matrix multiplication 
tic 
for ra = 1:9 % raws of the matrix A 
  for cb = 1:9 % columns of the matrix B 
    for len = 1:2  
      C(ra,cb) = A(ra,len)*B(len,cb)+C(ra,cb);  
    end 
  end 
end 
toc 
 
 
% Optimal method 1  
tic 
for cb = 1:9 % columns of the matrix B 
  for ra = 1:9 % raws of the matrix A 
    for len = 1:2  
      C(ra,cb) = A(ra,len)*B(len,cb)+C(ra,cb);  
    end 
  end 
end 
toc 
 
 
% Advanced optimal method 2 
A = A'; % you can also directly given A = [ 1 2 3 4 5 6 7 8 9  
    %                  1 2 3 4 5 6 7 8 9]; 
B = [ 1 2 3 4 5 6 7 8 9 
   1 2 3 4 5 6 7 8 9]; 
tic 
for i = 1:9 % columns of the matrix A 
  for j = 1:9 % columns of the matrix B 
    for len = 1:2 
      C(i,j) = A(len,i)*B(len,j)+C(i,j); 
    end 
  end 
end      
toc 

4. 測試和分析

測試結果如上圖所示，第一個時間為Matlab自帶的乘法運算，第二個為我們原始實現(xiàn)的乘法計算，第三個為循環(huán)中行列變換（適應列優(yōu)先編譯器的處理）。

最重要的是第四個是本人原創(chuàng)的矩陣乘法方法，簡單地說就是將A矩陣轉置，然后設計相應的算法實現(xiàn)矩陣乘運算。在這個點上，希望在理解原理的基礎上能給讀者一些啟發(fā)。在本例中，這樣做效率最高，原因其一是本例中原始數(shù)據(jù)結構上適合我這樣處理；原因其二是這樣做的目的是使得任何一個子乘法的處理上，兩乘數(shù)所在的內存空間上都是連續(xù)，而不僅僅是一個連續(xù)（注意：這是本文的核心，讀者理解透了一定會很有收獲，認真看我給出的程序實現(xiàn)。這是核心，不懂的可以交流思想）！

另外，本文中我給出的這個方法是矩陣乘法里面最優(yōu)的方法，至少數(shù)學邏輯上是這樣。之所以Matlab自帶的乘法計算之所以性能還不錯，是因為Matlab自帶的運算都是經(jīng)過優(yōu)化的，包括硬件加速，系統(tǒng)加速等自己設計的應用很能調用加速方法。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

最新評論