著者について
IBM China System and Technology Center のソフトウェア エンジニアである Wang Dandan は、2006 年に IBM に入社して以来、Web システムの設計と開発に従事しており、PHP アプリケーションの設計と開発で 5 年の経験があります。
通常、開発者がプログラムを作成するときは、すでに設計または考案された操作ロジックを直接プログラミング言語に変換することがよくあります。プログラムが正常にコンパイルされ、合格することができて、非常に満足しています。この時点でプログラムの実行時間がまだ許容範囲内であれば、コードを書いたという達成感に浸り、プロセス中のコードの最適化を無視してしまうことがよくあります。プログラムの実行速度に影響がある場合にのみ、前に戻って最適化を検討します。この記事では主に、PHP プログラミングにおける多段ループによる時間の複雑さを軽減するために配列を上手に使う方法を紹介します。特にプログラムがデータベースと複数回対話する必要がある場合、この方法を使用してコードを最適化すると、予期しない結果が生じる可能性があります。
アルゴリズムの時間計算量とは何ですか?
時間計算量は、開発者がアプリケーション アルゴリズムの品質を測定するために使用する主な要素です。客観的に言えば、アルゴリズムの品質は時間計算量だけでなく、空間計算量とも密接に関係しています。デバイスのハードウェア構成が継続的に改善されているため、アルゴリズムのスペースの複雑さの要件は、中小規模のアプリケーションでは大幅に緩和されています。しかし、今日の Web2.0 時代では、アプリケーションの時間の複雑さに対する要件がさらに高まっています。
アルゴリズムの時間計算量はどれくらいですか?要約すると、アルゴリズムを表現できるアルゴリズムの中からオリジナルの演算を選択し、そのオリジナルの演算が繰り返された回数をアルゴリズムの時間計測値として使用することを指します。時間計算量に影響を与える要因は 2 つあります。1 つは元の操作の実行時間、もう 1 つは制御構造によって引き起こされる元の操作の実行数です。アルゴリズムの時間の複雑さを軽減するには、元の操作の実行数を減らすのが簡単で主な方法です。この記事で説明する方法は、PHP 配列を巧みに使用することで元の操作の実行回数を減らし、それによってアルゴリズムの時間の複雑さを軽減し、それを全員で共有するというニーズを実現します。
アルゴリズムの時間測定は T(n)=O(f(n)) として記録されます。これは、アルゴリズムの基本演算の繰り返し実行回数が問題の関数 f(n) であることを意味します。サイズ n、つまり、問題のサイズ n が増加するにつれて、アルゴリズムの実行時間の増加率は f(n) の増加率と同じになります。ほとんどの場合、最も深いループのステートメントを元の操作として使用して、アルゴリズムの時間計算量を議論します。これは、ステートメントが実行される回数は、それを含むステートメントの頻度と同じであるためです。一般に、問題については、アルゴリズムの時間計算量を議論するために基本的な演算を選択するだけで済みます。場合によっては、複数の基本操作を同時に考慮する必要があります。
Web 開発では、通常、関数の実行時間や応答時間はサーバーの応答能力や処理能力に関係するだけでなく、データベースへのリンク時間などのサードパーティ ツールの対話時間も関係します。そしてデータの保存にかかる時間。したがって、元の演算を選択する際には、アプリケーションのあらゆる側面を総合的に考慮し、プログラムの実行時間に最も大きな影響を与える演算を元の演算として使用し、アルゴリズムの時間計算量を測定する必要があります。言い換えれば、プログラマーはコードを記述する際に重要な操作の実行時間について基本的に理解しておく必要があります。
一般的なプログラムの時間計算量分析
まず、Web プログラムの開発言語が PHP であり、バックグラウンドで使用されているものとして例を見てみましょう。 DB2 データベース PHP データベースへのアクセスは、PEAR::DB データ抽象化レイヤーを通じて実現されます。
例
データベースには、学生テーブル STUDENTS (表 1 を参照)、クラス テーブル CLASSES (表 2 を参照)、および学生成績テーブル SCORES (表 3 を参照) があります。この試験の数学のスコアは次のとおりです。 90点以上を獲得した生徒の名前とクラスがWebページに表示されます。
表 1. STUDENTS テーブル
列名
説明
SID
学生番号
STUNAME
名前
GENDER
性別
AGE
年齢
CLASSID
クラス番号
…
表 2. CLASSES テーブル
列名
説明
CLASSID
クラス番号
CLASSNAME
クラス名
…
表 3. SCORES テーブル
列名
説明
SID
学生 ID
COURSE
分野
SCORE
スコア
…
個人のプログラミング習慣の違いに応じて、この問題を解決するには通常 2 つの方法があります (PEAR を使用してデータベースにアクセスします:: DB)、方法 1 および 2 を参照してください。
【方法1】STUDENTS、CLASSES、SCORESの3つのテーブルに対して結合クエリを実行し、条件を満たす生徒情報とクラス情報を一度に取得します。 PHP アルゴリズムは次のように説明されます。
リスト 1. メソッド 1
コードをコピー コードは次のとおりです:
$querystr = "STUNAME として個別の S.STUNAME、CLASSNAME として C.CLASSNAME を選択します。
"から STUDENTS として、CLASSES として、SCORES として R を選択します"。S.SID= R.SID および S. CLASSID=C.CLASSID および R.COURSE='Math' ".
"および R.SCORE>=90";
$result = $db2handle->query( $querystr ) ; //データベースからデータを取得します
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//データを読み取り、表示します
echo "StudentName=".$row['STUNAME ']."t ClassName=".$row['CLASSNAME']."n";
}//完了
;
【方法2】SCORESテーブルから条件を満たす生徒番号を見つけ、次にSTUDENTSテーブルから生徒の名前とクラスコードを見つけ、最後にCLASSESテーブルからクラス名を取得します。 PHP アルゴリズムは次のように説明されます。
リスト 2. メソッド 2
コードをコピー コードは次のとおりです:
$scorestr = "COURSE='Math' および SCORE>=90 の SCORES から別の SID を選択します";
$scoredata = $db2handle->query( $scorestr );データベースの条件を満たす学生 Student ID
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//学生の学生 ID を読み取り、STUDENTS テーブルで学生の名前とクラス番号を見つけます
$studentstr = "STUDENTS から STUNAME,CLASSID を選択します。ここで SID='".$score['SID']."'";
$studata =$db2handle->query( $studentstr); >$stu=$studata->fetchRow(DB_FETCHMODE_ASSOC);
//生徒の名前を表示します
echo "StudentName=".$stu['STUNAME']."t ";学生のクラス番号を確認し、CLASSES テーブルで学生のクラス名を見つけます。
$classstr = "select CLASSNAME from CLASSES where CLASSID='".$stu['CLASSID']."'"; classdata = $db2handle- >query( $classstr);
$class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
//生徒のクラスを表示します
echo "CLASSNAME=".$class[ 'CLASSNAME']. "n";
}//end while は各生徒の ID を取得します
このようなアルゴリズムの説明は、誰もが馴染みがあると思います。これは、ほとんどのプログラマーによって広く使用されているアルゴリズムでもあります。私は自分の思考におけるアルゴリズムのロジックを直接コードに変換することに慣れてしまっているため、アルゴリズムの長所と短所を検討する時間と思考が足りないことがよくあります。ここでは、これら 2 つのアルゴリズムの時間計算量を分析します。
Web サーバーがデータを読み取って表示するのにかかる時間は比較的短く、通常は 10 ミリ秒程度であるため、DB2 データベースへのクエリとデータの取得にかかる時間は 100 ミリ秒程度になります。クエリデータの量が増えると増加します。したがって、データベースへのクエリ操作を時間計算量を測定する本来の操作として使用し、問題サイズ n として STUDENTS テーブルと SCORES テーブルのデータ量を使用します (通常、CLASSES テーブルのデータ量は小さくて比較的安定しています）。
方法 1 では、問題サイズ n が増加するにつれて、データベースのアクセス数は定数 1 になります。したがって、時間計算量は T(n)=O(1) となります。方法 2 の場合、条件を満たす SCORES テーブルのレコードが m 個あると仮定すると、元の操作の実行回数は m 1 回になります。つまり、データサイズ n が増加するにつれて、元の演算の実行回数は直線的に増加します。時間計算量は T(n)=O(n) であることがわかります。方法 1 の時間計算量が低いことがわかります。
コードは次のとおりです。 コードは次のとおりです。 $ClassArray = Array(); $classdata = $db2handle->query( $classstr);
$ClassArray = Array();
$StuArray = Array();
$classstr = "クラスからクラス ID、クラス名を選択"; ( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//ClassArray 配列を生成します。添字インデックスは CLASSID に基づいて名前が付けられ、対応する値は CLASSNAME
$ClassArray [$class['CLASSID']] = $class['CLASSNAME'];
}//$ClassArray
$stustr="学生から SID、STUNAME、CLASSID を選択"; >$studata = $db2handle->query( $stusstr);
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//StuArray 配列を生成し、添字インデックスは SID に基づいて名前が付けられます、および対応する値 STUNAME および CLASSID の場合
$StuArray[$stu ['SID']]['STUNAME'] = $stu['STUNAME']
$StuArray[$stu ['SID']; ]['CLASSID' ] = $stu['CLASSID'];
}//end while $StuArray
$scorestr = "COURSE='Math' および SCORE>=90 の SCORES から別の SID を選択します";
$scoredata = $db2handle->query( $scorestr );
//データベースから条件を満たす学生ID番号を取得します
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ) ){
/ /学生の学生番号を読み取り、StuArray から学生の名前を読み取り、ClassArray からクラス名を読み取ります
echo "StudentName=".$StuArray[ $score['SID'] ][' STUNAME'] ."t ";
echo "CLASSNAME=".$ClassArray[ $score['SID'] ]['CLASSID'] ]."n";各生徒の ID を取得するための完了
改良された方法の時間計算量は依然として T(n)=O(1) です。方法 3 では、方法 1 と比較して、特定のテーブルのレコードの増加によるデータベース クエリのコストが 2 倍になることを心配する必要がありません。方法 2 と比較すると、時間計算量は減少しますが、アルゴリズムの空間計算量には影響しません。一石二鳥と言えるでしょう。
この最適化手法はシンプルで使いやすいですが、万能というわけではありません。使用する場合は「程度」の問題を考慮する必要があります。 STUDENTS テーブルのデータ量が多いと仮定すると、StuArray を生成するときにシステム メモリの消費量が増加し、アルゴリズムの空間の複雑さに影響します。さらに、データ量が十分に大きい場合、アルゴリズムの実行時間に影響を与える主な要因が変化するため、元の演算を再選択する必要があります。 STUDENTS テーブルに多数のレコードがあり、CLASSES テーブルに少数の安定したレコードがあるシナリオでは、ネストされたクエリと配列の組み合わせを使用してアルゴリズムを最適化することを検討できます。参考のために方法 4 をここに示します。
リスト 4. 方法 4
コードをコピーします
while( $class =$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//ClassArray 配列を生成します。添字インデックスは CLASSID に基づいて名前が付けられ、対応する値は CLASSNAME
$ClassArray[$ class['CLASSID']] = $class ['CLASSNAME'];
}//end while $ClassArray
$stustr = "STUNAME,CLASSID from STUDENTS where SID in "(select SCORES とは異なる SID (COURSE='M' および SCORE>=90)";
$studata = $db2handle->query( $stustr);
// 一致する生徒の名前とクラス番号を取得しますデータベースからの条件
while( $stu= $studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//生徒の名前を読み取り、ClassArray からクラス名を読み取ります
echo "StudentName=".$ stu ['STUNAME']."t " ;
echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."n"; //各生徒の情報を取得する間終了します。完了
概要
方法 3 と 4 では、配列の小さなトリックを使用して、アルゴリズムの時間の複雑さを巧みに軽減します。実際のアプリケーションでは、アルゴリズムのロジックはさらに複雑で、アルゴリズムの最適化には多くの要素を総合的に考慮する必要があります。この記事で説明する方法は PHP アプリケーションにのみ適用されるわけではないことに注意してください。プログラミング言語の配列が添字としての文字列の使用をサポートしている場合は、この記事で提案されている方法の使用を検討できます。つまり、配列の添字を巧みに使用して、アルゴリズムの時間の複雑さを軽減します。配列の添字として文字列をサポートしないプログラミング言語の場合は、ハッシュ テーブルを使用して同じ効果を実現することを検討できます。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
