PHP 中巧用陣列降低程式的時間複雜度

時間複雜度是開發人員用來衡量應用程式演算法優劣的主要因素。客觀地說，演算法的優劣除了和時間複雜度有關，還與空間複雜度有密切關係。而隨著設備硬體配置的不斷提升，對中小型應用程式來說，對演算法的空間複雜度的要求也寬鬆了不少。不過，在當今 Web2.0 時代，對應用程式的時間複雜度卻有了更高的要求。

什麼是演算法的時間複雜度呢？摘要來說，是指從演算法中選取一個能代表演算法的原始操作，以原操作重複執行的次數作為演算法的時間量度。影響時間複雜度的因素有二：一是原操作的執行時間，二是原操作因控制結構所造成的執行次數。要把演算法的時間複雜度降下來，降低原操作的執行次數是較為容易的方法，也是主要方法。本文所述的方法，是透過巧用 PHP 的數組，降低原始操作的執行次數，從而達到降低演算法時間複雜度的需求，和大家分享。

演算法的時間量度記作T(n)=O(f(n))，它表示演算法中基本運算重複執行的次數是問題規模n 的某個函數f(n)，也就是說隨著問題規模n 的增大，演算法執行時間的成長率和f(n) 的成長率相同。多數情況下，我們把最深層迴圈內的語句當作原始操作來討論演算法的時間複雜度，因為它的執行次數和包含它的語句的頻度相同。一般情況下，對一個問題只需選擇一個基本操作來討論演算法的時間複雜度。有時也需要同時考慮多種基本操作。

在Web 開發中，通常一個功能的執行時間或回應時間，不僅跟伺服器的回應能力、處理能力有關，還涉及第三方工具的互動時間，如對資料庫的連結時間和對資料進行存取的時間。因而在選定原始操作是，需要綜合考慮應用程式各方面的因素，以最大影響程式執行時間的操作為原始操作，來衡量演算法的時間複雜度。也就是說，需要程式設計師在編寫程式碼的時候，對重要操作的執行時間能有基本的認知。

我們先看一個例子，假設 Web 程式的開發語言是 PHP，後台採用 DB2 資料庫，PHP 透過 PEAR::DB 資料抽象層來實現對資料庫的存取。

資料庫中有學生表STUDENTS（見表1），班級表CLASSES（見表2），學生成績表SCORES（見表3），需要在Web 頁面中顯示出本次考試數學成績超過90 分的同學姓名和班上。

表1. STUDENTS Table

列名   描述   

SID    學號   

STUNAME年齡   

CLASSID    班級號   

…    

 

表2. CLASSES Table

 

表2. CLASSES Table

列名描述   

CLASSID    班級號   

CLASSNAME    班級名   

…    

SID    學生學號   

COURSE    學科   

SCORE    成績   

…習慣的不同，要解決這個問題，通常有兩種做法（存取資料庫的操作以PEAR::DB 的方式表示），參考方法1、2。

[ 方法 1 ]對 STUDENTS, CLASSES, SCORES 三個表做聯合查詢，一次獲取滿足條件的學生資訊和班級資訊。 PHP 演算法說明如下：

$querystr = "select distinct S.STUNAME as STUNAME,C.CLASSNAME as CLASSNAME ".

        LAS     "where S. SID=R.SID and S.CLASSID=C.CLASSID and R.COURSE='Math' ".

"and R.SCORE>=90";

$result = $db2handle->query( $querystr ); //從資料庫取得資料

while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){

 //讀取並顯示資料

 echo "StudentName=".$row['STUNAME']."/t  ClassName=" .$row['CLASSNAME']."/n";
}//Done

 

 


[ 方法2 ]從SCORES 表中找出符合條件的學生學號，然後從STUDENTS 表中找出學生的姓名和班級編碼，最後在CLASSES 表中取得班級的名稱。 PHP 演算法描述如下：

$scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//從資料庫取得滿足條件的學生學號
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
   //讀取學生的學號，並在STUDENTS表中找出學生的姓名和班級編號
   $studentstr = "lectlectstudentent SID='".$score['SID']."'";
   $studata =$db2handle->query( $studentstr);
   $stu=$ data->fetchRow(DB_FETCHTCHDE_D OC);姓名
   echo "StudentName=".$stu['STUNAME']."/t    ";
   //讀去學生的班級編號，並在CLASSES表中找出該學生所在班級名稱
   $2SN. CLASSES where CLASSID='".$stu['CLASSID']."'";
   $classdata = $db2handle->query( $classstr);
   $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);學生的班級
   echo "CLASSNAME=".$class['CLASSNAME']."/n";
}//end while for getting each student's ID. Done
    

對於這樣的算法曾有描述，相信會有似相識對於大家的感覺。這也是大多程式設計師廣泛使用的演算法。因為已經習慣了將思考中的演算法邏輯直接譯成程式碼，而往往沒有時間和心思來斟酌演算法的優劣。這裡來分析一下這兩種演算法的時間複雜度。

因 Web 伺服器讀取並顯示資料的時間相對較小，一般在 10ms 的數量級，而從 DB2 資料庫中查詢並獲取資料的時間數量級會是 100ms 的數量級，並且隨查詢資料量的增加而增加。所以查詢資料庫的操作可作為量度時間複雜度的原操作，以 STUDENTS 表和 SCORES 表中的資料量作為問題規模 n( 通常情況下，CLASSES 表的資料量較小且相對穩定 )。

對於方法 1，隨著問題規模 n 的增加，存取資料庫的次數為常數 1。因而，時間複雜度為 T(n)=O(1)。對於方法 2，假設 SCORES 表中滿足條件的記錄有 m 個，則原始操作的執行次數為 m+1。也就是說隨著資料規模 n 的增大，原操作的執行次數成線性成長。可見時間複雜度為 T(n)=O(n)。可見，方法 1 的時間複雜度低。

那麼方法 1 的問題在哪裡？主要因為方法 1 會增加資料庫負載，也就是原操作的執行時間受問題規模 n 的影響比較大。假設 STUDENTS，CLASSES，SCORES 的記錄數分別為 X, Y, Z。那麼在執行聯合查詢操作時，在資料庫中會形成一個記錄數為 X*Y*Z 的矩陣，然後在這個矩陣中尋找滿足條件的記錄數，最後取得記錄的 STUNAME 資訊和 CLASSNAME。這樣，任何一個表中的數據增加，都會造成矩陣表中記錄的成倍增加

主要思路:在所需數據中存在相對簡單且數據量穩定的情況下，利用PHP 數組(Array) 的下標(Index) 可以為字串(String) 的特點，巧妙的將資料暫時存放到數組中。這樣可以透過下標 (Index) 快速取得所需值，從而降低對資料庫的查詢次數，進而降低演算法的時間複雜度。

[ 方法 3 ]從 CLASSES 表中取得 CLASSID 和 CLASSNAME 的對應關係存放到 ClassArray 一維數組中，從 STUDENTS 表中取得 SID 和 STUNAME 以及 CLASSID 的對應關係存放到 StuArray 二維數組中。之後從 SCORES 表中找出符合條件的學生學號，從 StuArray 陣列讀取學生的姓名和班級編號，從 ClassArray 讀取班級的名稱。 PHP 演算法描述如下：

$ClassArray = Array();
$StuArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
($classdata = $db2handle->query( $classstr);
while( $class=$ classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
   //產生ClassArray數組，下標Index以CLASSID命名，對應的值為CLASSNAME
 AME $ClassArray[$class['CLASSID']SNID]; }//end while $ClassArray
$stustr="select SID,STUNAME,CLASSID from STUDENTS";
$studata = $db2handle->query( $stustr);
while( $stu=$studata ->fetchRow(DB_FETCHIN ){
   //產生StuArray數組，下標Index以SID命名，對應的值為STUNAME和CLASSID
   $StuArray[$stu ['SID']]['STUNAME'] = $stu['STUNAME']; $StuArray[$stu ['SID']]['CLASSID'] = $stu['CLASSID'];
}//end while $StuArray
$scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//從資料庫取得符合條件的學生學號
while( $score=$scoredata->fetchRow(DB_FETCHDE_ASSOC) ){
//讀取學生的學號，並從StuArray讀取學生的姓名，從ClassArray中讀取班級名稱
   echo "StudentName=".$StuArray[ $score['SID'] ]['STUNAME']. "/t  ";
   echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."/n";
}//end while for getting each student's ID. Done
    

改良後方法的時間複雜度仍為T(n)=O(1)。和方法 1 相比，方法 3 不必擔心因某一個表中的記錄增加而引起的資料庫查詢代價的成倍增加。和方法 2 相比，時間複雜度降低的同時，也沒有影響演算法空間複雜度。可謂一舉兩得。

雖然此最佳化方法簡單易用，但並不是說它是萬能的。使用時需要考慮「度」的問題。假設 STUDENTS 表的資料量很大，那么生成 StuArray 的時候對系統記憶體的消耗就會增加，這樣演算法的空間複雜度就會受到影響。另外，當資料量夠大時，影響演算法執行時間的主要因素就發生了變化，需要重新選擇原始操作。針對 STUDENTS 表記錄數大，CLASSES 表記錄少且穩定的情景，可以考慮用巢狀查詢和陣列結合的方式，對演算法進行最佳化。這裡給出方法 4，以供參考。

[ 方法 4 ]從 CLASSES 表中取得 CLASSID 和 CLASSNAME 的對應關係存放到 ClassArray 一維數組中。從 SCORES 表中查詢符合條件的學生學號，作為查詢 STUDENTS 表的查詢條件，取得學生的 STUNAME 和 CLASSID。之後從 ClassArray 讀取班級的名稱。 PHP 演算法說明如下：

$ClassArray = Array();

$classstr = "select CLASSID,CLASSNAME from CLASSES";

$classdata = $db2handle->query( $classstr); $classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
   //產生ClassArray數組，下標Index以CLASSID命名，對應的值為CLASSNAME
 AME $ClassArray[$class['CLASSID']SN.];
}//end while $ClassArray
$stustr = "select STUNAME,CLASSID from STUDENTS where SID in ".
         "(select distinct SID from SCORES where COUR      "(select distinct SID from SCORES where COUROUR; $db2handle->query( $stustr);
//從資料庫取得符合條件的學生姓名和班級編號
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
   ////////////////////////////////////////並從ClassArray讀取班級名稱
   echo "StudentName=".$stu ['STUNAME']."/t  ";
   echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."/n ";
}//end while for getting each student's Info. Done
    



方法3 和方法4 中引用了數組這個小技巧，巧妙地降低了演算法的時間複雜度。在實際應用程式中，演算法邏輯要複雜得多，對演算法的最佳化需要綜合考慮多方面的因素。需要提出的是，本文所述的方法不僅適用於 PHP 應用程式。如果程式語言的陣列支援以字串作為下標，就可以考慮採用本文提出的方法：巧用陣列的下標來降低演算法的時間複雜度。對於不支援字串做數組下標的程式語言，可以考慮使用建立雜湊表來達到相同的效果。