PHP基於二分法的手機號碼歸屬查詢與傳統查詢效率比較

下面一起來看一個PHP基於二分法的手機號碼歸屬查詢與傳統查詢效率比較，希望文章對各位要求性能高的朋友會提供不錯的參考價值.

出於對算法對於系統的影響的好奇，決定實驗性的在實際生產環境中研究一下算法對系統效率的影響。二分法最重要的是對有序數據的查詢定位，例如手機號碼就是一個很貼切的有序排列的數據例子。
如果數據量很小，例如只有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次便可准確定位)，在更大量的數據的時候，查詢效率或許能真的給人直觀的反應。