|
|
王丹丹 , IBM 中國(guó)系統(tǒng)與技術(shù)中心軟件工程師，自從 2006 年加入 IBM，一直從事 Web 系統(tǒng)設(shè)計(jì)和開(kāi)發(fā)工作，有五年 php 應(yīng)用程序設(shè)計(jì)開(kāi)發(fā)經(jīng)驗(yàn)。
通常開(kāi)發(fā)人員在寫程序的時(shí)候，往往是把已經(jīng)設(shè)計(jì)好或者構(gòu)思好的運(yùn)算邏輯，直接用編程語(yǔ)言翻譯出來(lái)。程序能順利編譯通過(guò)，那是很令人高興的事情。如果此時(shí)程序的運(yùn)行時(shí)間還能接受，就會(huì)沉浸在寫代碼的成就感當(dāng)中，常常在這個(gè)過(guò)程中忽略代碼的優(yōu)化。只有當(dāng)程序運(yùn)行速度受到影響時(shí)，才回過(guò)頭去考慮優(yōu)化的事情。本文主要是介紹在 php的編程中，如何巧用數(shù)組來(lái)降低因多層循環(huán)而引起的時(shí)間復(fù)雜度的問(wèn)題。特別是當(dāng)程序需要多次與數(shù)據(jù)庫(kù)交互時(shí)，用此方法來(lái)優(yōu)化你的代碼，將會(huì)帶給意想不到的效果。
什么是算法的時(shí)間復(fù)雜度
時(shí)間復(fù)雜度是開(kāi)發(fā)人員用來(lái)衡量應(yīng)用程序算法優(yōu)劣的主要因素。客觀地說(shuō)，算法的優(yōu)劣除了和時(shí)間復(fù)雜度有關(guān)，還與空間復(fù)雜度密切相關(guān)。而隨著設(shè)備硬件配置的不斷提升，對(duì)中小型應(yīng)用程序來(lái)說(shuō)，對(duì)算法的空間復(fù)雜度的要求也寬松了不少。不過(guò)，在當(dāng)今 Web2.0 時(shí)代，對(duì)應(yīng)用程序的時(shí)間復(fù)雜度卻有了更高的要求。
什么是算法的時(shí)間復(fù)雜度呢？概要來(lái)說(shuō)，是指從算法中選取一個(gè)能代表算法的原操作，以原操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。影響時(shí)間復(fù)雜度的因素有兩個(gè)：一是原操作的執(zhí)行時(shí)間，二是原操作因控制結(jié)構(gòu)引起的執(zhí)行次數(shù)。要把算法的時(shí)間復(fù)雜度降下來(lái)，降低原操作的執(zhí)行次數(shù)是較為容易的方法，也是主要方法。本文所講述的方法，是通過(guò)巧用 php 的數(shù)組，降低原操作的執(zhí)行次數(shù)，從而達(dá)到降低算法時(shí)間復(fù)雜度的需求，和大家分享。
算法的時(shí)間量度記作 T(n)=O(f(n))，它表示算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模 n 的某個(gè)函數(shù) f(n)，也就是說(shuō)隨著問(wèn)題規(guī)模 n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n)的增長(zhǎng)率相同。多數(shù)情況下，我們把最深層循環(huán)內(nèi)的語(yǔ)句作為原操作來(lái)討論算法的時(shí)間復(fù)雜度，因?yàn)樗膱?zhí)行次數(shù)和包含它的語(yǔ)句的頻度相同。一般情況下，對(duì)一個(gè)問(wèn)題只需選擇一種基本操作來(lái)討論算法的時(shí)間復(fù)雜度即可。有時(shí)也需要同時(shí)考慮多種基本操作。
在 Web開(kāi)發(fā)中，通常一個(gè)功能的執(zhí)行時(shí)間或響應(yīng)時(shí)間，不僅僅跟服務(wù)器的響應(yīng)能力、處理能力有關(guān)，還涉及第三方工具的交互時(shí)間，如對(duì)數(shù)據(jù)庫(kù)的鏈接時(shí)間和對(duì)數(shù)據(jù)進(jìn)行存取的時(shí)間。因而在選定原操作是，需要綜合考慮應(yīng)用程序各方面的因素，以最大影響程序執(zhí)行時(shí)間的操作為原操作，來(lái)衡量算法的時(shí)間復(fù)雜度。也就是說(shuō)，需要程序員在編寫代碼的時(shí)候，對(duì)重要操作的執(zhí)行時(shí)間能有基本的認(rèn)識(shí)。
常見(jiàn)程序中的時(shí)間復(fù)雜度分析
我們先看一個(gè)例子，假設(shè) Web 程序的開(kāi)發(fā)語(yǔ)言是 php，后臺(tái)采用 DB2 數(shù)據(jù)庫(kù)，php 通過(guò) PEAR::DB 數(shù)據(jù)抽象層來(lái)實(shí)現(xiàn)對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)。
實(shí)例
數(shù)據(jù)庫(kù)中有學(xué)生表 STUDENTS（見(jiàn)表 1），班級(jí)表 CLASSES（見(jiàn)表 2），學(xué)生成績(jī)表 SCORES（見(jiàn)表 3），需要在 Web 頁(yè)面中顯示出本次考試數(shù)學(xué)成績(jī)超過(guò) 90 分的同學(xué)姓名和所在班級(jí)。
表 1. STUDENTS Table
列名
描述
SID
學(xué)號(hào)
STUNAME
姓名
GENDER
性別
AGE
年齡
CLASSID
班級(jí)號(hào)
…
表 2. CLASSES Table
列名
描述
CLASSID
班級(jí)號(hào)
CLASSNAME
班級(jí)名
…
表 3. SCORES Table
列名
描述
SID
學(xué)生學(xué)號(hào)
COURSE
學(xué)科
SCORE
成績(jī)
…
根據(jù)個(gè)人編程習(xí)慣的不同，要解決這個(gè)問(wèn)題，通常有兩種做法（訪問(wèn)數(shù)據(jù)庫(kù)的操作用 PEAR::DB 的方式表示），參看方法 1、2。
[ 方法 1 ]對(duì) STUDENTS, CLASSES, SCORES 三個(gè)表做聯(lián)合查詢，一次獲取滿足條件的學(xué)生信息和班級(jí)信息。php 算法描述如下：
清單 1. 方法 1
復(fù)制代碼 代碼如下:
$querystr = "select distinct S.STUNAME as STUNAME,C.CLASSNAME as CLASSNAME ".
"from STUDENTS as S,CLASSES as C,SCORES as R ".
"where S.SID=R.SID and S.CLASSID=C.CLASSID and R.COURSE='Math' ".
"and R.SCORE>=90";
$result = $db2handle->query( $querystr ); //從數(shù)據(jù)庫(kù)中獲取數(shù)據(jù)
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//讀取并顯示數(shù)據(jù)
echo "StudentName=".$row['STUNAME']."/t ClassName=".$row['CLASSNAME']."/n";
}//Done
[ 方法 2 ]從 SCORES 表中找出滿足條件的學(xué)生學(xué)號(hào)，然后從 STUDENTS 表中查找學(xué)生的姓名和班級(jí)編碼，最后在 CLASSES 表中獲取班級(jí)的名稱。php 算法描述如下：
清單 2. 方法 2
復(fù)制代碼 代碼如下:
$scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//從數(shù)據(jù)庫(kù)中獲取滿足條件的學(xué)生學(xué)號(hào)
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//讀取學(xué)生的學(xué)號(hào)，并在STUDENTS表中查找學(xué)生的姓名和班級(jí)編號(hào)
$studentstr = "select STUNAME,CLASSID from STUDENTS where SID='".$score['SID']."'";
$studata =$db2handle->query( $studentstr);
$stu=$studata->fetchRow(DB_FETCHMODE_ASSOC);
//顯示學(xué)生的姓名
echo "StudentName=".$stu['STUNAME']."/t ";
//讀去學(xué)生的班級(jí)編號(hào)，并在CLASSES表中查找該學(xué)生所在班級(jí)名稱
$classstr = "select CLASSNAME from CLASSES where CLASSID='".$stu['CLASSID']."'";
$classdata = $db2handle->query( $classstr);
$class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
//顯示學(xué)生的班級(jí)
echo "CLASSNAME=".$class['CLASSNAME']."/n";
}//end while for getting each student's ID. Done
對(duì)于這樣的算法描述，相信大家會(huì)有似曾相識(shí)的感覺(jué)。這也是大多程序員廣泛使用的算法。因?yàn)橐呀?jīng)習(xí)慣了將思維中的算法邏輯直接譯成代碼，而往往沒(méi)有時(shí)間和心思來(lái)斟酌算法的優(yōu)劣。這里來(lái)分析一下這兩種算法的時(shí)間復(fù)雜度。
因Web 服務(wù)器讀取并顯示數(shù)據(jù)的時(shí)間相對(duì)較小，一般在 10ms 的數(shù)量級(jí)，而從 DB2 數(shù)據(jù)庫(kù)里查詢并獲取數(shù)據(jù)的時(shí)間數(shù)量級(jí)會(huì)是 100ms的數(shù)量級(jí)，并且隨查詢數(shù)據(jù)量的增加而增加。所以查詢數(shù)據(jù)庫(kù)的操作可作為量度時(shí)間復(fù)雜度的原操作，以 STUDENTS 表和 SCORES表中的數(shù)據(jù)量作為問(wèn)題規(guī)模 n( 通常情況下，CLASSES 表的數(shù)據(jù)量較小且相對(duì)穩(wěn)定 )。
對(duì)于方法 1，隨著問(wèn)題規(guī)模n 的增大，訪問(wèn)數(shù)據(jù)庫(kù)的次數(shù)為常量 1。因而，時(shí)間復(fù)雜度為 T(n)=O(1)。對(duì)于方法 2，假設(shè) SCORES 表中滿足條件的記錄有 m個(gè)，則原操作的執(zhí)行次數(shù)為 m+1。也就是說(shuō)隨著數(shù)據(jù)規(guī)模 n 的增大，原操作的執(zhí)行次數(shù)成線性增長(zhǎng)。可見(jiàn)時(shí)間復(fù)雜度為T(n)=O(n)。可見(jiàn)，方法 1 的時(shí)間復(fù)雜度低。
那么方法 1 的問(wèn)題在哪里？主要因?yàn)榉椒?1會(huì)增大數(shù)據(jù)庫(kù)負(fù)載，也就是原操作的執(zhí)行時(shí)間受問(wèn)題規(guī)模 n 的影響比較大。假設(shè) STUDENTS，CLASSES，SCORES 的記錄數(shù)分別為X, Y, Z。那么在執(zhí)行聯(lián)合查詢操作時(shí)，在數(shù)據(jù)庫(kù)中會(huì)形成一個(gè)記錄數(shù)為 X*Y*Z的矩陣，然后在這個(gè)矩陣中查找滿足條件的記錄數(shù)，最后獲取記錄的 STUNAME 信息和CLASSNAME。這樣，任何一個(gè)表中的數(shù)據(jù)增加，都會(huì)造成矩陣表中記錄的成倍增加。
用數(shù)組來(lái)優(yōu)化算法
主要思路 :在所需數(shù)據(jù)中存在相對(duì)簡(jiǎn)單且數(shù)據(jù)量穩(wěn)定的情況下，利用 php 數(shù)組 (Array) 的下標(biāo) (Index) 可以為字符串 (String)的特點(diǎn)，巧妙的將數(shù)據(jù)臨時(shí)存放到數(shù)組中。這樣可以通過(guò)下標(biāo) (Index) 快速獲取所需值，從而降低對(duì)數(shù)據(jù)庫(kù)的查詢次數(shù)，進(jìn)而降低算法的時(shí)間復(fù)雜度。
[ 方法 3 ]從CLASSES 表中獲取 CLASSID 和 CLASSNAME 的對(duì)應(yīng)關(guān)系存放到 ClassArray 一維數(shù)組中，從 STUDENTS表中獲取 SID 和 STUNAME 以及 CLASSID 的對(duì)應(yīng)關(guān)系存放到 StuArray 二維數(shù)組中。之后從 SCORES表中找出滿足條件的學(xué)生學(xué)號(hào)，從 StuArray 數(shù)組中讀取學(xué)生的姓名和班級(jí)編號(hào)，從 ClassArray 中讀取班級(jí)的名稱。php算法描述如下：
清單 3. 方法 3
復(fù)制代碼 代碼如下:
$ClassArray = Array();
$StuArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//生成ClassArray數(shù)組，下標(biāo)Index以CLASSID命名，對(duì)應(yīng)的值為CLASSNAME
$ClassArray[$class['CLASSID']] = $class['CLASSNAME'];
}//end while $ClassArray
$stustr="select SID,STUNAME,CLASSID from STUDENTS";
$studata = $db2handle->query( $stustr);
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//生成StuArray數(shù)組，下標(biāo)Index以SID命名，對(duì)應(yīng)的值為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 );
//從數(shù)據(jù)庫(kù)中獲取滿足條件的學(xué)生學(xué)號(hào)
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//讀取學(xué)生的學(xué)號(hào)，并從StuArray中讀取學(xué)生的姓名，從ClassArray中讀取班級(jí)名稱
echo "StudentName=".$StuArray[ $score['SID'] ]['STUNAME']."/t ";
echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."/n";
}//end while for getting each student's ID. Done
改進(jìn)后方法的時(shí)間復(fù)雜度仍為 T(n)=O(1)。和方法 1 相比，方法 3 不必?fù)?dān)心因某一個(gè)表中的記錄增加而引起的數(shù)據(jù)庫(kù)查詢代價(jià)的成倍增加。和方法 2 相比，時(shí)間復(fù)雜度降低的同時(shí)，也沒(méi)有影響算法空間復(fù)雜度。可謂一舉兩得。
雖然此優(yōu)化方法簡(jiǎn)單易用，但并不是說(shuō)它是萬(wàn)能的。使用時(shí)需要考慮“度”的問(wèn)題。假設(shè) STUDENTS 表的數(shù)據(jù)量很大，那么生成 StuArray的時(shí)候?qū)ο到y(tǒng)內(nèi)存的消耗就增加，這樣算法的空間復(fù)雜度就會(huì)受到影響。另外，當(dāng)數(shù)據(jù)量足夠大時(shí)，影響算法執(zhí)行時(shí)間的主要因素就發(fā)生了變化，需要重新選擇原操作。針對(duì) STUDENTS 表記錄數(shù)大，CLASSES表記錄少且穩(wěn)定的情景，可以考慮用嵌套查詢和數(shù)組相結(jié)合的方式，對(duì)算法進(jìn)行優(yōu)化。這里給出方法 4，以供參考。
[ 方法 4 ]從CLASSES 表中獲取 CLASSID 和 CLASSNAME 的對(duì)應(yīng)關(guān)系存放到 ClassArray 一維數(shù)組中。從 SCORES表中查詢滿足條件的學(xué)生學(xué)號(hào)，作為查詢 STUDENTS 表的查詢條件，獲取學(xué)生的 STUNAME 和 CLASSID。之后從ClassArray 中讀取班級(jí)的名稱。php 算法描述如下：
清單 4. 方法 4
復(fù)制代碼 代碼如下:
$ClassArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//生成ClassArray數(shù)組，下標(biāo)Index以CLASSID命名，對(duì)應(yīng)的值為CLASSNAME
$ClassArray[$class['CLASSID']] = $class['CLASSNAME'];
}//end while $ClassArray
$stustr = "select STUNAME,CLASSID from STUDENTS where SID in ".
"(select distinct SID from SCORES where COURSE='M' and SCORE>=90)";
$studata = $db2handle->query( $stustr);
//從數(shù)據(jù)庫(kù)中獲取滿足條件的學(xué)生姓名和班級(jí)編號(hào)
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//讀取學(xué)生的姓名，并從ClassArray中讀取班級(jí)名稱
echo "StudentName=".$stu ['STUNAME']."/t ";
echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."/n";
}//end while for getting each student's Info. Done
總結(jié)
方法 3 和方法 4中引用了數(shù)組這個(gè)小技巧，巧妙地降低了算法的時(shí)間復(fù)雜度。在實(shí)際應(yīng)用程序中，算法邏輯要復(fù)雜得多，對(duì)算法的優(yōu)化需要綜合考慮多方面的因素。需要提出的是，本文所述的方法不僅適用于 php應(yīng)用程序。如果編程語(yǔ)言的數(shù)組支持以字符串作為下標(biāo)，就可以考慮采用本文提出的方法：巧用數(shù)組的下標(biāo)來(lái)降低算法的時(shí)間復(fù)雜度。對(duì)于不支持字符串做數(shù)組下標(biāo)的編程語(yǔ)言，可以考慮使用建立哈希表來(lái)達(dá)到同樣的效果。
php技術(shù)：PHP 巧用數(shù)組降低程序的時(shí)間復(fù)雜度，轉(zhuǎn)載需保留來(lái)源！
鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。
