出于对算法对于系统的影响的好奇，决定实验性的在实际生产环境中研究一下算法对系统效率的影响。二分法最重要的是对有序数据的查询定位，例如手机号码就是一个很贴切的有序排列的数据例子。
如果数据量很小，例如只有10条有序数据，要查询其中的第9条数据，轮询查询需要查询9次确定结果，二分法查询次数为3次（分别是匹配第5、8、9条记录）即可确定结果。数据量越大，二分法所带来的效率就是程2的阶乘递增，可以大大提升服务器的运行效率、提升用户等待时间、节省服务器资源。
实验环境：LAMP
实验数据：国内手机号码归属地。手机号码前7位代表一个号段，生成从1300000到1590000之间的所有号段按从小到大排列，大约30万条数据。
传统查询：对于任意手机号码，截取前7位，从数据库中第一条记录开始循环向下匹配，如果对照，则返回查询结果。
| 代码如下 | 复制代码 |
| flock($fp,LOCK_SH); $note = fread($fp,filesize('./data.php')); //读取数据 fclose($fp); $note = explode("n",$note); array_pop($note); array_shift($note); $num = count($note); $_data = ''; //循环查询开始 for($i=1;$i<$num;$i++){ $row = explode(" ",$note[$i]); if($m == $row[0]){ $_data = $row; break; } } |
|
实测结果：最快0.03512秒、最慢0.63043秒、平均查询用时约为0.4秒。
二分法查询：对于任意手机号码，截取前7位。首先匹配数据库中最中间的第100000条数据，根据二分法原则，若匹配结果比中间值大，重新选择第二次匹配第100000到200000的中间值----第150000条数据。以此类推，直到查询到最后一位正确的值返回结果。那么每次的查询次数小于或等于17次。
| 代码如下 | 复制代码 |
|
flock($fp,LOCK_SH); $note = fread($fp,filesize('./data.php')); //读取数据 fclose($fp); $note = explode("n",$note); array_pop($note); array_shift($note); $num = count($note); //统计数据库总记录数 $_data = ''; $low = 0; //二分法两端点变量 $hight = $num; while($m < 1599999){ $num = ceil(($hight + $low)/2); $row = explode(" ",$note[$num]); if ($m == $row[0]){ return $_data = $row; break; }else{ $m >= $row[0] ? $low = $num : $hight = $num; } } |
|
实测结果：每次查询都在0.034—0.035之间。
结论：本试验可以看出，二分法数据查询效率比传统效率快10倍以上。本实验数据只有30万条，在普通的应用性数据查询时，数据量越大，越能显示出二分法的优越性(理论上讲，上千万的数据查询次数不超过30次便可准确定位)，在更大量的数据的时候，查询效率或许能真的给人直观的反应。
时间： 2024-11-04 00:34:09