Maison > php教程 > php手册 > 【数据结构】PHP实现查找表

【数据结构】PHP实现查找表

WBOY
Libérer: 2016-06-21 09:05:33
original
1175 Les gens l'ont consulté

数据|数据结构

【基本算法】

假设有一个数组,需要找出某个值在该数组中的位置。


//二分查找
function bin_sch($array, $low, $high, $k){
    if ($low         $mid = intval(($low+$high)/2);
        if ($array[$mid] == $k){
            return $mid;
        }elseif ($k             return bin_sch($array, $low, $mid-1, $k);
        }else{
            return bin_sch($array, $mid+1, $high, $k);
        }
    }
    return -1;
}

//顺序查找
function seq_sch($array, $n, $k){
    $array[$n] = $k;
    for($i=0; $i        if($array[$i]==$k){
            break;
        }
    }
    if ($i        return $i;
    }else{
        return -1;
    }
}

?>

测试代码:
array.txt 文件里面包含了一百万条类似 2,3,4,5 这样的数据,下面通过顺序查找和二分查找来确定速度。


//二分查找
set_time_limit(0);
$array = array();
$file = file_get_contents("./array.txt");

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

$st = time();
$k = 43; 
$n = count($array);
$r = bin_sch($array, 0, $n-1, $k);
$et = time();

$t = $et-$st;
echo "Process time: ". $t ."/s";
?>

以上输出: Process time: 0/s

//顺序查找
set_time_limit(0);
$array = array();
$file = file_get_contents("./array.txt");
$array = explode(",", $file);

$st = time();
$k = 43; 
$n = count($array);
$r = seq_sch($array, $n, $k); 
$et = time();

$t = $et-$st;
echo "Process time: ". $t ."/s";
?>

以上输出结果:Process time: 9/s


上面轻易就能够看出谁的效率高了。


【算法改进】


//二分查找(递归消除)
function bin_sch($array, $n, $k){
    $low = 0;
    $high = $n-1;
    while($low         $mid = intval(($high-$low)/2);
        if ($array[$mid] == $k)
            return $mid;
        elseif ($k             $high = $mid - 1;
        }else{
            $low = $mid + 1;
        }
    }
    return -1;
}

//顺序查找(改进版)
function seq_sch($array, $n, $k){
    $array[$n] = $k;
    for($i=0; ; $i++){
        if($array[$i]==$k){
            break;
        }
    }
    if ($i        return $i;
    }else{
        return -1;
    }
}
?>


能看出上面两个函数做了什么改变吗?效率提升了多少?

 



Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Recommandations populaires
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal