PHPでは配列を巧みに用いてプログラムの時間的複雑さを低減する
まず、次の説明は、技術牛の潘良虎の空間から転載されたもので、文章が上手だと感じて、自分のコレクションに回って、みんなに分かち合いました.
コンテンツの概要
本稿では,PHPのプログラミングにおいて,配列を巧みに用いて多層サイクルによる時間的複雑さを低減する方法について述べた.特に、プログラムがデータベースと何度も対話する必要がある場合、この方法でコードを最適化すると、予想外の効果が得られます.
通常、開発者はプログラムを書くとき、すでに設計された演算ロジックや構想された演算ロジックを、プログラミング言語で直接翻訳することが多い.プログラムが無事にコンパイルできて嬉しいです.このときプログラムの実行時間がまだ受け入れられると,コードを書く達成感に浸り,この過程でコードの最適化を無視することが多い.プログラムの実行速度が影響を受けた場合にのみ、最適化のことを振り返って考えます.本稿では,PHPのプログラミングにおいて,配列を巧みに用いて多層サイクルによる時間的複雑さを低減する方法について紹介する.特に、プログラムがデータベースと何度も対話する必要がある場合、この方法でコードを最適化すると、予想外の効果が得られます.
アルゴリズムの時間的複雑さとは
時間の複雑さは、開発者がアプリケーションアルゴリズムの優劣を測定する主な要因です.客観的に言えば,アルゴリズムの優劣は時間的複雑さに関係するだけでなく,空間的複雑さにも密接に関連している.デバイスのハードウェア構成が向上するにつれて、中小規模アプリケーションにとって、アルゴリズムの空間的複雑さに対する要求も緩和されています.でも、今のWeb 2.0時代には、アプリケーションの時間的複雑さがより求められていました.
アルゴリズムの時間的複雑さとは何ですか.要約すると、アルゴリズムからアルゴリズムを表す元の操作を選択し、元の操作が繰り返し実行される回数をアルゴリズムの時間メトリックとする.時間の複雑さに影響する要因は2つある.1つは元の操作の実行時間であり、2つは元の操作が制御構造による実行回数である.アルゴリズムの時間的複雑さを低減するには,元の操作の実行回数を低減することが容易な方法であり,主な方法でもある.本稿で述べた方法は,PHPの配列を巧みに用いることで,元の操作の実行回数を低減し,アルゴリズム時間の複雑さを低減するニーズを達成し,皆さんと共有することである.
アルゴリズムの時間メトリックはT(n)=O(f(n))と表記され、アルゴリズムにおける基本動作の繰り返し実行回数が問題規模nのある関数f(n)であることを示す.すなわち、問題規模nが大きくなるにつれて、アルゴリズム実行時間の増加率とf(n)の増加率は同じである.多くの場合,実行回数とその文を含む頻度が同じであるため,最も深いループ内の文を元の操作としてアルゴリズムの時間的複雑さを議論する.一般的に,1つの問題に対して基本操作を選択してアルゴリズムの時間的複雑さを議論するだけでよい.複数の基本操作を同時に考慮する必要がある場合もある.
Web開発では、通常、1つの機能の実行時間または応答時間は、サーバの応答能力、処理能力だけでなく、データベースへのリンク時間やデータへのアクセス時間などのサードパーティツールのインタラクティブな時間にも関連しています.したがって,元の操作を選択するには,アプリケーションの各方面の要因を総合的に考慮し,プログラム実行時間に最大の影響を及ぼす操作を元の操作としてアルゴリズムの時間複雑度を測定する必要がある.すなわち,プログラマがコードを記述する際に,重要な操作の実行時間を基本的に認識する必要がある.
一般的なプログラムでの時間複雑度分析
まず、Webプログラムの開発言語がPHPであると仮定し、バックグラウンドにDB 2データベースを採用し、PHPはPEAR::DBデータ抽象層を通じてデータベースへのアクセスを実現する.
例:
データベースには学生表STUDENTS(表1参照)、クラス表CLASES(表2参照)、学生成績表SCORES(表3参照)があり、今回の試験で数学の成績が90点を超える学生の名前とクラスをWebページに表示する必要がある.
表1.STUDENTS Table
列名
説明
SID
学号
STUNAME
名前
GENDER
性別
AGE
年齢
CLASSID
クラス番号
…
…
表2.CLASSES Table
列名
説明
CLASSID
クラス番号
CLASSNAME
クラス名
…
…
表3.SCORES Table
列名
説明
SID
学生番号
COURSE
コース
SCORE
成績
…
…
個人のプログラミング習慣によって、この問題を解決するには、通常2つの方法(データベースへのアクセス操作はPEAR::DBで表される)があり、方法1、2を参照してください.
[方法1]:STUDENTS,CLASSES,SCORESの3つのテーブルに対して共同クエリーを行い,条件を満たす学生情報とクラス情報を一度に取得する.PHPアルゴリズムは以下のように記述される.
[方法2]:SCORESテーブルから条件を満たす学生学号を見つけ、STUDENTSテーブルから学生の名前とクラスコードを検索し、最後にCLASSESテーブルからクラス名を取得する.PHPアルゴリズムは以下のように記述される.
このようなアルゴリズムの記述に対して、皆さんはかつて知ったような感じがすると信じています.これも多くのプログラマーが広く使用しているアルゴリズムです.思考中のアルゴリズムロジックを直接コードに訳すことに慣れているため、アルゴリズムの優劣を吟味する時間と工夫がないことが多い.ここでは,この2つのアルゴリズムの時間的複雑さを解析する.
Webサーバがデータを読み込んで表示する時間が比較的小さいため、一般的に10 msの桁数であるが、DB 2データベースからデータをクエリーして取得する時間の桁数は100 msの桁数であり、クエリーデータ量の増加に伴って増加する.したがって、クエリ・データベースの動作は、STUDENTSテーブルおよびSCORESテーブルのデータ量を問題規模nとして、時間的複雑さを測る元の動作とすることができる(通常、CLASSSESテーブルのデータ量は小さく、比較的安定している).
メソッド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情報とCLASSSNAMEを取得します.これにより、いずれのテーブルのデータも増加し、マトリクステーブルの記録が倍増します.
配列によるアルゴリズムの最適化
主な考え方:必要なデータに比較的簡単でデータ量が安定している場合、PHP配列(Array)のインデックス(Index)を利用して文字列(String)の特徴とすることができ、巧みにデータを配列に一時的に格納することができる.これにより、下付き(Index)で必要な値をすばやく取得することができ、データベースへのクエリー回数を低減し、アルゴリズムの時間的複雑さを低減することができる.
[方法3]:CLASSESテーブルからCLASSIDとCLASSSNAMEの対応関係を取得してClassArray 1次元配列に格納し、STUDENTSテーブルからSIDとSTUNAMEおよびCLASSIDの対応関係を取得してStuArray 2次元配列に格納する.その後、SCORESテーブルから条件を満たす学生学号を見つけ、StuArray配列から学生の名前とクラス番号を読み出し、ClassArrayからクラス名を読み出す.PHPアルゴリズムは以下のように記述される.
改良された方法の時間的複雑さはT(n)=O(1)のままであった.メソッド1と比較して、メソッド3は、あるテーブルのレコードの増加によるデータベース・クエリーのコストの倍増を心配する必要はありません.方法2と比較して,時間的複雑度が低下するとともに,アルゴリズム空間的複雑度にも影響を及ぼさない.一挙両得といえる.
この最適化方法は簡単で使いやすいが,万能とは限らない.使用するときは「度」の問題を考慮する必要があります.STUDENTSテーブルのデータ量が大きいと仮定すると,StuArrayを生成する際にシステムメモリの消費量が増加し,アルゴリズムの空間的複雑さが影響を受ける.また,データ量が十分大きいとアルゴリズム実行時間に影響する要因が変化し,元の操作を再選択する必要がある.STUDENTSテーブルのレコード数が大きく,CLASSESテーブルのレコードが少なく安定しているシナリオに対して,ネストクエリと配列を組み合わせた方法でアルゴリズムを最適化することが考えられる.ここでは、参照のために方法4を示す.
[方法4]:CLASSESテーブルからCLASSIDとCLASSSNAMEの対応関係を取得し、ClassArray次元配列に格納します.SCORESテーブルから条件を満たす学生学号を照会し、STUDENTSテーブルを照会する照会条件として、学生のSTUNAMEとCLASSIDを取得する.その後クラス名をClassArrayから読み出します.PHPアルゴリズムは以下のように記述される.
まとめ
方法3と方法4では配列という小さなテクニックを引用し,アルゴリズムの時間的複雑さを巧みに低減した.実際のアプリケーションでは、アルゴリズムロジックはずっと複雑で、アルゴリズムの最適化には多方面の要素を総合的に考慮する必要があります.本明細書に記載の方法は、PHPアプリケーションにのみ適用されるものではない.プログラミング言語の配列が文字列を下付き文字としてサポートする場合,本論文で提案した方法:配列の下付き文字を巧みに用いてアルゴリズムの時間的複雑さを低減することが考えられる.文字列の配列下付きをサポートしないプログラミング言語では,ハッシュテーブルの作成を用いて同様の効果を達成することが考えられる.
コンテンツの概要
本稿では,PHPのプログラミングにおいて,配列を巧みに用いて多層サイクルによる時間的複雑さを低減する方法について述べた.特に、プログラムがデータベースと何度も対話する必要がある場合、この方法でコードを最適化すると、予想外の効果が得られます.
通常、開発者はプログラムを書くとき、すでに設計された演算ロジックや構想された演算ロジックを、プログラミング言語で直接翻訳することが多い.プログラムが無事にコンパイルできて嬉しいです.このときプログラムの実行時間がまだ受け入れられると,コードを書く達成感に浸り,この過程でコードの最適化を無視することが多い.プログラムの実行速度が影響を受けた場合にのみ、最適化のことを振り返って考えます.本稿では,PHPのプログラミングにおいて,配列を巧みに用いて多層サイクルによる時間的複雑さを低減する方法について紹介する.特に、プログラムがデータベースと何度も対話する必要がある場合、この方法でコードを最適化すると、予想外の効果が得られます.
アルゴリズムの時間的複雑さとは
時間の複雑さは、開発者がアプリケーションアルゴリズムの優劣を測定する主な要因です.客観的に言えば,アルゴリズムの優劣は時間的複雑さに関係するだけでなく,空間的複雑さにも密接に関連している.デバイスのハードウェア構成が向上するにつれて、中小規模アプリケーションにとって、アルゴリズムの空間的複雑さに対する要求も緩和されています.でも、今のWeb 2.0時代には、アプリケーションの時間的複雑さがより求められていました.
アルゴリズムの時間的複雑さとは何ですか.要約すると、アルゴリズムからアルゴリズムを表す元の操作を選択し、元の操作が繰り返し実行される回数をアルゴリズムの時間メトリックとする.時間の複雑さに影響する要因は2つある.1つは元の操作の実行時間であり、2つは元の操作が制御構造による実行回数である.アルゴリズムの時間的複雑さを低減するには,元の操作の実行回数を低減することが容易な方法であり,主な方法でもある.本稿で述べた方法は,PHPの配列を巧みに用いることで,元の操作の実行回数を低減し,アルゴリズム時間の複雑さを低減するニーズを達成し,皆さんと共有することである.
アルゴリズムの時間メトリックはT(n)=O(f(n))と表記され、アルゴリズムにおける基本動作の繰り返し実行回数が問題規模nのある関数f(n)であることを示す.すなわち、問題規模nが大きくなるにつれて、アルゴリズム実行時間の増加率とf(n)の増加率は同じである.多くの場合,実行回数とその文を含む頻度が同じであるため,最も深いループ内の文を元の操作としてアルゴリズムの時間的複雑さを議論する.一般的に,1つの問題に対して基本操作を選択してアルゴリズムの時間的複雑さを議論するだけでよい.複数の基本操作を同時に考慮する必要がある場合もある.
Web開発では、通常、1つの機能の実行時間または応答時間は、サーバの応答能力、処理能力だけでなく、データベースへのリンク時間やデータへのアクセス時間などのサードパーティツールのインタラクティブな時間にも関連しています.したがって,元の操作を選択するには,アプリケーションの各方面の要因を総合的に考慮し,プログラム実行時間に最大の影響を及ぼす操作を元の操作としてアルゴリズムの時間複雑度を測定する必要がある.すなわち,プログラマがコードを記述する際に,重要な操作の実行時間を基本的に認識する必要がある.
一般的なプログラムでの時間複雑度分析
まず、Webプログラムの開発言語がPHPであると仮定し、バックグラウンドにDB 2データベースを採用し、PHPはPEAR::DBデータ抽象層を通じてデータベースへのアクセスを実現する.
例:
データベースには学生表STUDENTS(表1参照)、クラス表CLASES(表2参照)、学生成績表SCORES(表3参照)があり、今回の試験で数学の成績が90点を超える学生の名前とクラスをWebページに表示する必要がある.
表1.STUDENTS Table
列名
説明
SID
学号
STUNAME
名前
GENDER
性別
AGE
年齢
CLASSID
クラス番号
…
…
表2.CLASSES Table
列名
説明
CLASSID
クラス番号
CLASSNAME
クラス名
…
…
表3.SCORES Table
列名
説明
SID
学生番号
COURSE
コース
SCORE
成績
…
…
個人のプログラミング習慣によって、この問題を解決するには、通常2つの方法(データベースへのアクセス操作はPEAR::DBで表される)があり、方法1、2を参照してください.
[方法1]:STUDENTS,CLASSES,SCORESの3つのテーブルに対して共同クエリーを行い,条件を満たす学生情報とクラス情報を一度に取得する.PHPアルゴリズムは以下のように記述される.
$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 ); //
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//
echo "StudentName=".$row['STUNAME']."\t ClassName=".$row['CLASSNAME']."
";
}//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 = "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']."
";
}//end while for getting each student's ID. Doneこのようなアルゴリズムの記述に対して、皆さんはかつて知ったような感じがすると信じています.これも多くのプログラマーが広く使用しているアルゴリズムです.思考中のアルゴリズムロジックを直接コードに訳すことに慣れているため、アルゴリズムの優劣を吟味する時間と工夫がないことが多い.ここでは,この2つのアルゴリズムの時間的複雑さを解析する.
Webサーバがデータを読み込んで表示する時間が比較的小さいため、一般的に10 msの桁数であるが、DB 2データベースからデータをクエリーして取得する時間の桁数は100 msの桁数であり、クエリーデータ量の増加に伴って増加する.したがって、クエリ・データベースの動作は、STUDENTSテーブルおよびSCORESテーブルのデータ量を問題規模nとして、時間的複雑さを測る元の動作とすることができる(通常、CLASSSESテーブルのデータ量は小さく、比較的安定している).
メソッド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情報とCLASSSNAMEを取得します.これにより、いずれのテーブルのデータも増加し、マトリクステーブルの記録が倍増します.
配列によるアルゴリズムの最適化
主な考え方:必要なデータに比較的簡単でデータ量が安定している場合、PHP配列(Array)のインデックス(Index)を利用して文字列(String)の特徴とすることができ、巧みにデータを配列に一時的に格納することができる.これにより、下付き(Index)で必要な値をすばやく取得することができ、データベースへのクエリー回数を低減し、アルゴリズムの時間的複雑さを低減することができる.
[方法3]:CLASSESテーブルからCLASSIDとCLASSSNAMEの対応関係を取得してClassArray 1次元配列に格納し、STUDENTSテーブルからSIDとSTUNAMEおよびCLASSIDの対応関係を取得してStuArray 2次元配列に格納する.その後、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
$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 ， 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_FETCHMODE_ASSOC) ){
// ， StuArray ， ClassArray
echo "StudentName=".$StuArray[ $score['SID'] ]['STUNAME']."\t ";
echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."
";
}//end while for getting each student's ID. Done改良された方法の時間的複雑さはT(n)=O(1)のままであった.メソッド1と比較して、メソッド3は、あるテーブルのレコードの増加によるデータベース・クエリーのコストの倍増を心配する必要はありません.方法2と比較して,時間的複雑度が低下するとともに,アルゴリズム空間的複雑度にも影響を及ぼさない.一挙両得といえる.
この最適化方法は簡単で使いやすいが,万能とは限らない.使用するときは「度」の問題を考慮する必要があります.STUDENTSテーブルのデータ量が大きいと仮定すると,StuArrayを生成する際にシステムメモリの消費量が増加し,アルゴリズムの空間的複雑さが影響を受ける.また,データ量が十分大きいとアルゴリズム実行時間に影響する要因が変化し,元の操作を再選択する必要がある.STUDENTSテーブルのレコード数が大きく,CLASSESテーブルのレコードが少なく安定しているシナリオに対して,ネストクエリと配列を組み合わせた方法でアルゴリズムを最適化することが考えられる.ここでは、参照のために方法4を示す.
[方法4]:CLASSESテーブルからCLASSIDとCLASSSNAMEの対応関係を取得し、ClassArray次元配列に格納します.SCORESテーブルから条件を満たす学生学号を照会し、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 ， Index CLASSID ， 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);
//
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
// ， ClassArray
echo "StudentName=".$stu ['STUNAME']."\t ";
echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."
";
}//end while for getting each student's Info. Doneまとめ
方法3と方法4では配列という小さなテクニックを引用し,アルゴリズムの時間的複雑さを巧みに低減した.実際のアプリケーションでは、アルゴリズムロジックはずっと複雑で、アルゴリズムの最適化には多方面の要素を総合的に考慮する必要があります.本明細書に記載の方法は、PHPアプリケーションにのみ適用されるものではない.プログラミング言語の配列が文字列を下付き文字としてサポートする場合,本論文で提案した方法:配列の下付き文字を巧みに用いてアルゴリズムの時間的複雑さを低減することが考えられる.文字列の配列下付きをサポートしないプログラミング言語では,ハッシュテーブルの作成を用いて同様の効果を達成することが考えられる.