【データ構造】 PHPが実装するルックアップテーブル

データ|データ構造

【基本アルゴリズム】

配列があり、配列内の特定の値の位置を見つける必要があるとします。

//二分探索
function bin_sch($array, $low, $high, $k){
if ($low <= $high){
$mid = intval(($low+ $high)/2);
if ($array[$mid] == $k){
return $mid;
}elseif ($k < $array[$mid]){
return bin_sch($array, $ Low, $ MID -1, $ k);
} else {
Return bin_sch ($ array, $ middle+1, $ high, $ k); // 逐次検索
関数 seq_sch($array, $n, $ k){
$array[$n] = $k;
for($i=0; $i<$n; $i++){
if( $array[$i]==$k){

}

?>



テストコード:
array.txt ファイルには 2,3,4,5 と同様の 100 万個のデータが含まれており、速度は逐次検索と二分探索によって決定されます。




//二分探索
set_time_limit(0);

$file = file_get_contents("./array.txt");

$array =explode( ",", $file);

$st = time();

$n = count($array); , $n-1, $k);
$t = $et-$st; echo ". $t ."/s";

上記の出力: 処理時間: 0/s

//逐次検索
set_time_limit(0);
$array = array();
$file = file_get_contents("./array.txt") ;
$array =explode(",", $file);

$st = time();

$n = count($array); n , $k);
$et = $et-$st;

echo ". $t ."/s";結果: 処理時間: 9/秒

上記から誰がより効率的であるかが簡単にわかります。

【アルゴリズム改善】

//二分探索(再帰消去)

function bin_sch($array, $n, $k){

$low = 0;

$high = $n-1;

while($low <= $high){
$mid = intval(($high-$low)/2);
if ($array[$mid] == $k)
return $mid; ($k < }

// 逐次検索(改良版)

function seq_sch($array, $n, $k){

$array[$n] = $k;
for($i=0; ; $ i++){
if($array[ $i]==$k){
}
}

?>

上記 2 つの関数にどのような変更が加えられたかわかりますか?効率はどれくらい向上しましたか?