Chinaunix

标题: 【原创】深思 PHP 数组遍历的差异（array_diff 的实现） [打印本页]

作者: AMD-K6 时间: 2007-12-21 12:48
标题: 【原创】深思 PHP 数组遍历的差异（array_diff 的实现）
原文链接： http://www.gracecode.com/Archive/Display/421

还是部门无聊的考题，不过这次考的是 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 函数需要循环判断是否在函数内；而函数三则仅仅判断这个数组是否存在该键就可以了。

加上数组键和值不同的组织索引方式，效率比想象的还高那就非常可以理解了。

附，下载链接和脚本：http://www.gracecode.com/Archive/Display/421

[ 本帖最后由 AMD-K6 于 2007-12-21 12:50 编辑 ]

作者: james.liu 时间: 2007-12-21 13:41
看下googlechina的blog，，关于布尔的计算这块，，，用布尔做差集和合集会很快。尤其是大量数据

作者: powerpolly 时间: 2007-12-21 15:08
明显地，isset比in_array开销小:wink:

作者: myaxl2008 时间: 2007-12-24 14:04

LZ...
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例子如下:

<?php
$array1 = array("a" => "green", "red", "blue", "red");
$array2 = array("b" => "green", "yellow", "red");
$result = array_diff($array1, $array2);
print_r($result);
?>
在 $array1 中多次出现的值一样处理，输出结果为：
Array
(
[1] => blue
)

复制代码

LZ所写的情况和此函数好像不太一样,如果两数组的Key不一样,值不一样的话,所谓的比原array_diff快是没法对比的吧.应该和array_diff_key对比下性能.

平时对性能研究很少,分析的有问题请路过飘过的大侠们指点一二.

[ 本帖最后由 myaxl2008 于 2007-12-24 14:05 编辑 ]

作者: goshawk 时间: 2007-12-24 20:12

作者: Aryang 时间: 2007-12-25 11:08
能不能把两种方法差别的数据列出来？

作者: courage121 时间: 2007-12-25 19:28
差距很大，当两个数组都是5000的时候应该还能显示出结果，但是如果两个数组都是10000的话页面应该执行到一半就显示不出来了

作者: ydlhero 时间: 2007-12-26 14:07
不错的对比,平时很少去做对比

作者: myaxl2008 时间: 2007-12-26 14:40

功能都不一样如何做对比.......

作者: wnpers 时间: 2007-12-26 15:43
标题: 恩
学习

[ 本帖最后由 wnpers 于 2007-12-26 15:51 编辑 ]

作者: zhanglp888 时间: 2008-01-03 15:07
array_flip 如果同一个值出现了多次，则最后一个键名将作为它的值，所有其它的都丢失了。

作者: zhanglp888 时间: 2008-01-03 15:09
所以用array_flip将会丢失数据

作者: songlv 时间: 2008-03-05 11:54
其实 array_flip() 也很慢的而且比in_array()要慢得多, 和但是 array_flip()是在循环外面的之执行一遍而 in_array()要执行 5000多次所以可以看出结果

作者: zeraw 时间: 2008-03-05 13:13
array_flip() 丢失数据的话，那这样比较还是不行的

作者: chinatzbcn 时间: 2008-03-27 10:27
针对本题可以这么搞的啊，效率很高，但是如果第二个数组的value里有重复的值,LZ不就挂了啊。

作者: chinatzbcn 时间: 2008-03-27 10:30
抱歉，刚没看清楚，我错了。

作者: bollwarm 时间: 2008-03-28 15:27
标题: 回复 #1 AMD-K6 的帖子
把兄台的程序修改了一下，列出几组数据

1）
for($i = 0, $ary_1 = array(); $i < 5000; $i++) {
$ary_1[] = $i;
}

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

--------------------------------------------------------
函数 array_diff 运行0.338655948639 秒
函数 array_diff2 运行0.0425670146942 秒
函数 array_diff3 运行0.0321950912476 秒
函数 array_diff4 运行0.0265200138092 秒
-----------------------------------------------------------
2）

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

for($i = 0, $ary_2 = array(); $i < 5000; $i++) {
$ary_1[] = $i+5000;
}
--------------------------------------------------------------------
函数 array_diff 运行0.263401985168 秒
函数 array_diff2 运行0.0434989929199 秒
函数 array_diff3 运行0.0338242053986 秒
函数 array_diff4 运行0.0271499156952 秒

----------------------------------------------------------------------
3）

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

for($i = 0, $ary_2 = array(); $i < 5000; $i++) {
$ary_1[] = $i+2500;
}

--------------------------------------------------------------------

函数 array_diff 运行0.25840306282 秒
函数 array_diff2 运行0.0452589988708 秒
函数 array_diff3 运行0.0320010185242 秒
函数 array_diff4 运行0.0261788368225 秒

---------------------------------------------------
4）
for($i = 0, $ary_1 = array(); $i < 5000; $i++) {
$ary_1[] = rand();
$ary_1[] = $i;
}

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

}
--------------------------------------------------------------
函数 array_diff 运行0.287934064865 秒
函数 array_diff2 运行13.2373249531 秒
函数 array_diff3 运行0.944373130798 秒
函数 array_diff4 运行0.0226550102234 秒

作者: dhgdmw 时间: 2008-07-13 19:49
不错，学习

作者: 艾斯尼勒 时间: 2008-07-14 11:11
恩？题目是让找差集，array_flip去掉重复的元素应该不是问题吧？

作者: dong4138 时间: 2008-07-14 11:49
不要用foreach循环， for循环和数组迭代器会更快

作者: linux_name 时间: 2010-12-01 13:02
很好的思路啊！谢谢LZ 分享！

作者: bs 时间: 2010-12-06 18:19
从某种角度说,它们之间的时间复杂度没什么区别,数组翻转也是遍历,且空间复杂度要多出一倍

作者: 星辉流动 时间: 2012-01-06 19:36
:wink:

作者: Frank_mc 时间: 2012-01-08 10:40
空间换时间，不错

作者: liuxingyuyuni 时间: 2012-01-08 18:11
哈哈！第三种实现方法很招人喜欢！~~

不错，顶你。

作者: pitonas 时间: 2012-01-17 23:02
PHP 竟然可以这样写

作者: qloog 时间: 2012-01-18 11:36
不错的对比，同时加深对数组函数的理解！

作者: sychangchun 时间: 2012-01-23 22:59
学习啊。很好

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)