PHP での配列の賢明な使用により、プログラム時間の複雑さが軽減されます。

時間計算量は、開発者がアプリケーション アルゴリズムの利点を測定するために使用する主な要素です。客観的に言えば、アルゴリズムの品質は時間計算量だけでなく、空間計算量とも密接に関係しています。デバイスのハードウェア構成が継続的に改善されているため、アルゴリズムのスペースの複雑さの要件は、中小規模のアプリケーションでは大幅に緩和されています。しかし、今日の Web2.0 時代では、アプリケーションの時間の複雑さに対する要件がさらに高まっています。

アルゴリズムの時間計算量はどれくらいですか?要約すると、アルゴリズムを表現できるアルゴリズムの中からオリジナルの演算を選択し、そのオリジナルの演算が繰り返された回数をアルゴリズムの時間計測値として使用することを指します。時間計算量に影響を与える要因は 2 つあります。1 つは元の操作の実行時間、もう 1 つは制御構造によって引き起こされる元の操作の実行数です。アルゴリズムの時間の複雑さを軽減するには、元の操作の実行数を減らすのが簡単で主な方法です。この記事で説明する方法は、PHP 配列を巧みに使用することで元の操作の実行回数を減らし、それによってアルゴリズムの時間の複雑さを軽減し、それを全員で共有するというニーズを実現します。

アルゴリズムの時間測定は T(n)=O(f(n)) として記録されます。これは、アルゴリズムの基本操作が繰り返される回数が問題サイズの関数 f(n) であることを意味しますつまり、スケール n が増加するにつれて、アルゴリズムの実行時間の増加率は f(n) の増加率と同じになります。ほとんどの場合、最も深いループのステートメントを元の操作として使用して、アルゴリズムの時間計算量を議論します。これは、ステートメントが実行される回数は、それを含むステートメントの頻度と同じであるためです。一般に、問題については、アルゴリズムの時間計算量を議論するために基本的な演算を選択するだけで済みます。場合によっては、複数の基本操作を同時に考慮する必要があります。

Web 開発では、通常、関数の実行時間または応答時間は、サーバーの応答能力と処理能力に関係するだけでなく、データベースへのリンク時間やサードパーティ ツールの対話時間も関係します。データへのアクセス時間。したがって、元の演算を選択する際には、アプリケーションのあらゆる側面を総合的に考慮し、プログラムの実行時間に最も大きな影響を与える演算を元の演算として使用し、アルゴリズムの時間計算量を測定する必要があります。言い換えれば、プログラマーはコードを記述する際に重要な操作の実行時間について基本的に理解しておく必要があります。

まず、Web プログラムの開発言語が PHP であり、PHP が PEAR::DB データ抽象化を通じてデータベースへのアクセスを実装していると仮定します。層。

データベースには、学生テーブル STUDENTS (表 1 を参照)、クラス テーブル CLASSES (表 2 を参照)、および学生成績テーブル SCORES (表 3 を参照) が含まれています。このテストは90点を超えています。クラスメートの名前とクラス。

表 1. STUDENTS テーブル

列名 説明

SID 学生番号

STUNAME 名前

GENDER 性別

AGE 年齢

CLASSID クラス番号

…

表 2. CLASSES テーブル

列名説明

CLASSID クラス番号

CLASSNAME クラス名

…

表 3. SCORES テーブル

列名 説明

SID 学生番号

COURSE 科目

SCORE スコア

…

個人的なプログラミングに基づいています習慣に応じて、この問題を解決するには通常 2 つの方法があります (データベースへのアクセス操作は PEAR::DB で表現されます)。方法 1 と 2 を参照してください。

【方法1】STUDENTS、CLASSES、SCORESの3つのテーブルに対して結合クエリを実行し、条件を満たす生徒情報とクラス情報を一度に取得します。 PHP アルゴリズムは次のように説明されます。

$querystr = "students as S、CLASSES as C、SCORES as R ".

" から、STUNAME として個別の S.STUNAME、CLASSNAME として C.CLASSNAME を選択します。ここで、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";
}//Done


【方法2】SCORESテーブルから条件を満たす生徒番号を見つけ、次にその生徒の名前をSCORESテーブルから見つけます。 STUDENTS テーブルとクラス コード、そして最後に CLASSES テーブル内のクラスの名前を取得します。 PHP アルゴリズムは次のように説明されます:

$scorestr = "scores where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//条件を満たす学生 ID 番号を取得します。データベース
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//学生の学生 ID を読み取り、STUDENTS テーブルで学生の名前とクラス番号を見つけます
$studentstr = "select STUNAME,CLASSID from STUDENTS ここでSID='".$score['SID']."'";
$studata =$db2handle->query( $studentstr);
$stu=$studata->fetchRow(DB_FETCHMODE_ASSOC);
// 生徒の表示Name
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);
// 生徒のデータを表示class
echo "CLASSNAME=".$class['CLASSNAME']."/n";
}//end while は各生徒の ID を取得します。 Done

このようなアルゴリズムの説明については、誰もがよく知っていると思います。という感じです。これは、ほとんどのプログラマーによって広く使用されているアルゴリズムでもあります。私は自分の思考におけるアルゴリズムのロジックを直接コードに変換することに慣れてしまっているため、アルゴリズムの長所と短所を検討する時間と思考が足りないことがよくあります。ここでは、これら 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 配列を使用します(配列) 添字 (インデックス) には文字列 (文字列) を指定でき、データを配列に一時的に格納することができます。このようにして、インデックスを通じて必要な値を迅速に取得できるため、データベースへのクエリの数が減り、アルゴリズムの時間の複雑さが軽減されます。

【方法3】CLASSESテーブルからCLASSIDとCLASSNAMEの対応関係を取得し、ClassArrayの1次元配列に格納する STUDENTSテーブルからSIDとSTUNAME、CLASSIDの対応関係を取得し、StuArrayの2次元配列に格納する。 -次元配列。次に、SCORES テーブルから条件を満たす学生 ID 番号を見つけ、StuArray 配列から学生の名前とクラス番号を読み取り、ClassArray からクラスの名前を読み取ります。 PHP アルゴリズムは次のように説明されます:

$ClassArray = Array();
$StuArray = Array();
$classstr = "クラスからクラスID、クラス名を選択";
$classdata = $db2handle->query( $classstr);
while( $class=$ classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//ClassArray 配列を生成します。添字インデックスは CLASSID に基づいて名前が付けられ、対応する値は CLASSNAME です
$ClassArray[$class['CLASSID']] = $class['CLASSNAME' ];
}//end while $ClassArray
$stustr="学生から SID、STUNAME、CLASSID を選択";
$studata = $db2handle->query( $stustr);
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 = "SCORES から別の SID を選択where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//データベースから条件を満たす学籍番号を取得します
while( $score=$scoredata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//学生の学生番号を読み取り、StuArray から学生の名前を読み取り、ClassArray からクラス名を読み取ります
echo "StudentName=".$StuArray[ $score['SID'] ][ 'STUNAME']. "/t ";
echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."/n";
}//end while for各生徒の 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 アルゴリズムは次のように説明されます。

$ClassArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class= $classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//ClassArray 配列を生成します。添字インデックスは CLASSID に基づいて名前が付けられ、対応する値は CLASSNAME
$ClassArray[$class['CLASSID']] = $class ['CLASSNAME'];
}//end while $ClassArray
$stustr = "「.
」の SID から STUNAME、CLASSID を選択します (COURSE='M' および SCORE>=90 の SCORES から別の SID を選択します) ";
$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 アプリケーションだけに適しているわけではないことに注意してください。プログラミング言語の配列が添字として文字列の使用をサポートしている場合は、この記事で提案されている方法の使用を検討できます。配列の添字を巧みに使用して、アルゴリズムの時間の複雑さを軽減します。配列の添字として文字列をサポートしないプログラミング言語の場合は、ハッシュ テーブルを使用して同じ効果を実現することを検討できます。