PHP は配列を巧みに使用してプログラムの複雑さを軽減します_PHP チュートリアル
- WBOYオリジナル
- 2016-07-21 15:42:011018ブラウズ
著者について
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)) として記録されます。これは、アルゴリズムの基本操作が繰り返される回数が問題サイズ n の関数 f(n) であることを意味します。つまり、問題サイズが n の場合、n が増加するにつれて、アルゴリズムの実行時間の増加率は f(n) の増加率と同じになります。ほとんどの場合、最も深いループのステートメントを元の操作として使用して、アルゴリズムの時間計算量を議論します。これは、ステートメントが実行される回数は、それを含むステートメントの頻度と同じであるためです。一般に、問題については、アルゴリズムの時間計算量を議論するために基本的な演算を選択するだけで済みます。場合によっては、複数の基本操作を同時に考慮する必要があります。
Web 開発では、通常、関数の実行時間または応答時間はサーバーの応答能力と処理能力に関係するだけでなく、データベースへのリンク時間などのサードパーティ ツールの対話時間も関係します。データにアクセスする時間。したがって、元の演算を選択する際には、アプリケーションのあらゆる側面を総合的に考慮し、プログラムの実行時間に最も大きな影響を与える演算を元の演算として使用し、アルゴリズムの時間計算量を測定する必要があります。言い換えれば、プログラマーはコードを記述する際に重要な操作の実行時間について基本的に理解しておく必要があります。
一般的なプログラムの時間計算量分析
まず、Web プログラムの開発言語が PHP であり、PHP がバックグラウンドでデータベースへのアクセスを実装していると仮定します。 PEAR::DB データ抽象化レイヤー。
例
データベースには、学生テーブル STUDENTS (表 1 を参照)、クラス テーブル CLASSES (表 2 を参照)、および学生成績テーブル SCORES (表 3 を参照) が含まれています。数学のスコアが を超えた学生を Web ページに表示する必要があります。この試験ではクラスメイトの名前とクラスが 90 点です。
表 1. STUDENTS テーブル
列名
説明
SID
学生番号
STUNAME
名前
GENDER
性別
AGE
年齢
CLASSID
クラス番号
…
表 2. CLASSES テーブル
列名
説明
CLASSID
クラス番号
CLASSNAME
クラス名
…
表 3. SCORES テーブル
名前
説明
SID
学生番号
COURSE
Subject
SCORE
Score
…
個人のプログラミング習慣に応じて、解決するにはこの問題には通常 2 つの方法があります (データベースへのアクセス操作は PEAR::DB で表現されます)。方法 1 と方法 2 を参照してください。
【方法1】STUDENTS、CLASSES、SCORESの3つのテーブルに対して結合クエリを実行し、条件を満たす生徒情報とクラス情報を一度に取得します。 PHP アルゴリズムは次のように説明されます。
リスト 1. 方法 1
$querystr = "select unique 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 ); //データベースからデータを取得します
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//Readデータを表示します
echo " StudentName=".$row['STUNAME']."t ClassName=".$row['CLASSNAME']."n";
【方法2】SCORESテーブルから条件を満たす学生の学籍番号を見つけ、次にSTUDENTSテーブルから学生の名前とクラスコードを見つけ、最後にCLASSESテーブルからクラス名を取得します。 PHP アルゴリズムは次のように説明されます。
リスト 2. 方法 2
$scorestr = "select unique SID from SCORES where COURSE='Math' and SCORE> ;=90";
$scoredata = $db2handle->query( $scorestr );
//条件を満たす学籍番号をデータベースから取得します
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//学生の学生 ID を読み取り、STUDENTS テーブルで学生の名前とクラス番号を見つけます
$studentstr = "select STUNAME,CLASSID from STUDENTS where 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 の時間計算量が低いことがわかります。
それでは、方法 1 の問題は何でしょうか?主な理由は、方法 1 ではデータベースの負荷が増加すること、つまり、元の操作の実行時間が問題のサイズ n に大きく影響されることです。 STUDENTS、CLASSES、SCORES のレコード数がそれぞれ X、Y、Z であるとします。次に、結合クエリ操作を実行するときに、レコード番号が次の行列になります。このように、テーブル内のデータが増加すると、マトリックス テーブル内のレコード数が指数関数的に増加します。
アルゴリズムを最適化するために配列を使用する
主なアイデア: 必要なデータが比較的単純で、データ量が安定している場合は、PHP 配列 (Array) の添字 (Index) を文字列 (String) にできる機能を使用します。 . データを一時的に配列に上手に保存します。このようにして、インデックスを通じて必要な値を迅速に取得できるため、データベースへのクエリの数が減り、アルゴリズムの時間の複雑さが軽減されます。
【方法3】 CLASSESテーブルからCLASSIDとCLASSNAMEの対応関係を取得し、ClassArrayの1次元配列に格納する STUDENTSテーブルからSIDとSTUNAME、CLASSIDの対応関係を取得し、StuArrayの2次元配列に格納する。次元配列。次に、SCORES テーブルから条件を満たす学生 ID 番号を見つけ、StuArray 配列から学生の名前とクラス番号を読み取り、ClassArray からクラスの名前を読み取ります。 PHP アルゴリズムは次のように説明されています:
リスト 3. 方法 3
$ClassArray = Array();
$classstr = "クラスから CLASSID,CLASSNAME を選択"
$classdata = $db2handle->query( $classstr); =$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//ClassArray 配列を生成します。添字インデックスは CLASSID に基づいて名前が付けられ、対応する値は CLASSNAME です
$ClassArray[$class['CLASSID']] = $class[ 'CLASSNAME' ];
}//end while $ClassArray
$stustr="学生から SID,STUNAME,CLASSID を選択";
$studata = $db2handle->query( $stu=$); stackata -> ;fetchRow(DB_FETCHMODE_ASSOC) ){
//StuArray 配列を生成します。添字インデックスは SID に基づいて名前が付けられ、対応する値は STUNAME と CLASSID です
$StuArray[$stu ['SID']] ['STUNAME'] = $stu[' STUNAME'];
$StuArray[$stu ['SID']]['CLASSID'] = $stu['CLASSID']; // $StuArray
$ 中に終了corestr = "scores where COURSE ='Math' and SCORE>=90" から個別の SID を選択します。
$scoredata = $db2handle->query( $scorestr );
//条件を満たす学生 ID 番号を取得します。 Database
while( $score=$scoredata-> fetchRow(DB_FETCHMODE_ASSOC) ){
//学生の学生番号を読み取り、StuArray から学生の名前を読み取り、ClassArray からクラス名を読み取ります
echo "StudentName=".$StuArray [ $score['SID'] ]['STUNAME']."t ";
echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."n" ;
}//各生徒の ID を取得するための終了
改良された方法の時間計算量は依然として T(n)=O(1) です。方法 3 では、方法 1 と比較して、特定のテーブルのレコードの増加によるデータベース クエリのコストが 2 倍になることを心配する必要がありません。方法 2 と比較すると、時間計算量は減少しますが、アルゴリズムの空間計算量には影響しません。一石二鳥と言えるでしょう。
この最適化手法はシンプルで使いやすいですが、万能というわけではありません。使用する場合は「程度」の問題を考慮する必要があります。 STUDENTS テーブルのデータ量が多いと仮定すると、StuArray を生成するときにシステム メモリの消費量が増加し、アルゴリズムの空間の複雑さに影響します。さらに、データ量が十分に大きい場合、アルゴリズムの実行時間に影響を与える主な要因が変化するため、元の演算を再選択する必要があります。 STUDENTS テーブルに多数のレコードがあり、CLASSES テーブルに少数の安定したレコードがあるシナリオでは、ネストされたクエリと配列の組み合わせを使用してアルゴリズムを最適化することを検討できます。参考のために方法 4 をここに示します。
【方法4】 CLASSESテーブルからCLASSIDとCLASSNAMEの対応関係を取得し、一次元配列ClassArrayに格納します。 SCORES テーブルから条件を満たす学生 ID 番号をクエリし、それを STUDENTS テーブルにクエリするためのクエリ条件として使用して、学生の STUNAME と CLASSID を取得します。次に、ClassArray からクラスの名前を読み取ります。 PHP アルゴリズムは次のように説明されます。
リスト 4. メソッド 4
コードをコピーします。 コードは次のとおりです。
}//end while $ClassArray
$stustr = "stuname,CLASSID from STUDENTS ここでSID in ".
"(scores where COURSE='M' and 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 アプリケーションにのみ適用されるわけではないことに注意してください。プログラミング言語の配列が添字としての文字列の使用をサポートしている場合は、この記事で提案されている方法の使用を検討できます。つまり、配列の添字を巧みに使用して、アルゴリズムの時間の複雑さを軽減します。配列の添字として文字列をサポートしないプログラミング言語の場合は、ハッシュ テーブルを使用して同じ効果を実現することを検討できます。