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

摘要

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

1. 背景

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

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

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

2. 計(jì)算機(jī)領(lǐng)域的應(yīng)用

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

3. 以矩陣計(jì)算為例（Matlab編譯器下測(cè)試）

% 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. 測(cè)試和分析

測(cè)試結(jié)果如上圖所示，第一個(gè)時(shí)間為Matlab自帶的乘法運(yùn)算，第二個(gè)為我們?cè)紝?shí)現(xiàn)的乘法計(jì)算，第三個(gè)為循環(huán)中行列變換（適應(yīng)列優(yōu)先編譯器的處理）。

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

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

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

最新評(píng)論