注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

牧笔临风

己有能,勿自私!

 
 
 

日志

 
 
 
 

array_diff 的优化实现  

2012-02-21 21:15:33|  分类: php |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

还是部门无聊的考题,不过这次考的是 PHP 的能力。题目如下: 给你两个分别有 5000 个元素的数组,计算他们的差集 -- 说白了也就是用 PHP 和你认为最好的算法实现 array_diff 的算法。初次接到这个题目,我发现这非常的简单,于是按照以往的经验“随便”写了一个:

function array_diff($array_1, $array_2) { 
$diff = array(); 

foreach ($array_1 as $k => $v1) { 
$flag = false; 
foreach ($array_2 as $v2) { 
if ($flag = ($v1 == $v2)) { 
break; 

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

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

function array_diff($array_1, $array_2) { 
foreach ($array_1 as $key => $item) { 
if (in_array($item, $array_2, true)) { 
unset($array_1[$key]); 

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

function array_diff($array_1, $array_2) { 
$array_2 = array_flip($array_2); 
foreach ($array_1 as $key => $item) { 
if (isset($array_2[$item])) { 
unset($array_1[$key]); 

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

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

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

附代码
复制代码 代码如下:

<?php 
function microtime_float() { 
list($usec, $sec) = explode(" ", microtime()); 
return ((float)$usec + (float)$sec); 

function array_diff2($array_1, $array_2) { 
$diff = array(); 

foreach ($array_1 as $k => $v1) { 
$flag = false; 
foreach ($array_2 as $v2) { 
if ($flag = ($v1 == $v2)) { 
break; 

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

return $diff; 


function array_diff3($array_1, $array_2) { 
foreach ($array_1 as $key => $item) { 
if (in_array($item, $array_2, true)) { 
unset($array_1[$key]); 

return $array_1; 


function array_diff4($array_1, $array_2) { 
$array_2 = array_flip($array_2); 
foreach ($array_1 as $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"; 
?>
  评论这张
 
阅读(211)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017