欢迎来到福编程网,本站提供各种互联网专业知识!

深思 PHP 数组遍历的差异(array_diff 的实现)

发布时间:2008-03-23 作者: 来源:转载
还是部门无聊的考题,不过这次考的是PHP的能力。题目如下:给你两个分别有5000个元素的数组,计算他们的差集--说白了也就是用PHP和你认为最好的算法实现array_diff的算法。初次接到这个题目,我发现这非常的简单,于是按照以往的经验“随便”写了一个:
functionarray_diff($array_1,$array_2){
$diff=array();

foreach($array_1as$k=>$v1){
$flag=false;
foreach($array_2as$v2){
if($flag=($v1==$v2)){
break;
}
}

if(!$flag){
$diff[$k]=$v1;
}
}

return$diff;
}虽然实现是可以的,但是发现这个函数的效率是惨不忍睹。于是我又重新考虑了下,并优化了算法,第二个函数看起来是这个样子的:

functionarray_diff($array_1,$array_2){
foreach($array_1as$key=>$item){
if(in_array($item,$array_2,true)){
unset($array_1[$key]);
}
}

return$array_1;
}嗯,这次几乎可以和原array_diff函数的速度媲美了。但是还有没有更优化的办法呢?由ChinaUnix上的一篇文章(不好意思,作弊了),我发现PHP竟然可以这样写:

functionarray_diff($array_1,$array_2){
$array_2=array_flip($array_2);
foreach($array_1as$key=>$item){
if(isset($array_2[$item])){
unset($array_1[$key]);
}
}

return$array_1;
}这个函数的效率非常的惊人,甚至比原array_diff函数的速度都要快。究其原因,我找到了解释:

因为键是进行HASH组织的,查找很快;
而Value只是由Key组织存放,本身没有索引,每次查找都是遍历。总结
这虽然是PHP语言的一个小窍门,但在遍历和对比数组的值上,如果需要对比值将其与键反转的确比通常的值对值的比较效率要高得多。

比如,上面的函数二需要调用in_array函数需要循环判断是否在函数内;而函数三则仅仅判断这个数组是否存在该键就可以了。加上数组键和值不同的组织索引方式,效率比想象的还高那就非常可以理解了。

附代码
复制代码 代码如下:
functionmicrotime_float(){
list($usec,$sec)=explode("",microtime());
return((float)$usec+(float)$sec);
}

functionarray_diff2($array_1,$array_2){
$diff=array();

foreach($array_1as$k=>$v1){
$flag=false;
foreach($array_2as$v2){
if($flag=($v1==$v2)){
break;
}
}

if(!$flag){
$diff[$k]=$v1;
}
}

return$diff;
}


functionarray_diff3($array_1,$array_2){
foreach($array_1as$key=>$item){
if(in_array($item,$array_2,true)){
unset($array_1[$key]);
}
}

return$array_1;
}


functionarray_diff4($array_1,$array_2){
$array_2=array_flip($array_2);
foreach($array_1as$key=>$item){
if(isset($array_2[$item])){
unset($array_1[$key]);
}
}

return$array_1;
}

//////////////////////////////

for($i=0,$ary_1=array();$i<5000;$i++){
$ary_1[]=rand(100,999);
}

for($i=0,$ary_2=array();$i<5000;$i++){
$ary_2[]=rand(100,999);
}

header("Content-type:text/plain;charset=utf-8");

$time_start=microtime_float();
array_diff($ary_1,$ary_2);
echo"函数array_diff运行".(microtime_float()-$time_start)."秒n";

$time_start=microtime_float();
array_diff2($ary_1,$ary_2);
echo"函数array_diff2运行".(microtime_float()-$time_start)."秒n";

$time_start=microtime_float();
array_diff3($ary_1,$ary_2);
echo"函数array_diff3运行".(microtime_float()-$time_start)."秒n";

$time_start=microtime_float();
array_diff4($ary_1,$ary_2);
echo"函数array_diff4运行".(microtime_float()-$time_start)."秒n";
?>


相关推荐