忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
123下一页
最近访问板块 发新帖
查看: 18944 | 回复: 27

【原创】深思 PHP 数组遍历的差异(array_diff 的实现) [复制链接]

论坛徽章:
0
发表于 2007-12-21 12:48 |显示全部楼层
原文链接: 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 编辑 ]

论坛徽章:
0
发表于 2007-12-21 13:41 |显示全部楼层
看下googlechina的blog,,关于布尔的计算这块,,,用布尔做差集和合集会很快。尤其是大量数据

论坛徽章:
0
发表于 2007-12-21 15:08 |显示全部楼层
明显地,isset比in_array开销小:wink:

论坛徽章:
0
发表于 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例子如下:

  1. <?php
  2. $array1 = array("a" => "green", "red", "blue", "red");
  3. $array2 = array("b" => "green", "yellow", "red");
  4. $result = array_diff($array1, $array2);

  5. print_r($result);
  6. ?>

  7. 在 $array1 中多次出现的值一样处理,输出结果为:

  8. Array
  9. (
  10.     [1] => blue
  11. )
复制代码

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

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

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

论坛徽章:
0
发表于 2007-12-24 20:12 |显示全部楼层

论坛徽章:
0
发表于 2007-12-25 11:08 |显示全部楼层
能不能把两种方法差别的数据列出来?

论坛徽章:
0
发表于 2007-12-25 19:28 |显示全部楼层
差距很大,当两个数组都是5000的时候应该还能显示出结果,但是如果两个数组都是10000的话页面应该执行到一半就显示不出来了

论坛徽章:
0
发表于 2007-12-26 14:07 |显示全部楼层
不错的对比,平时很少 去做对比

论坛徽章:
0
发表于 2007-12-26 14:40 |显示全部楼层
功能都不一样如何做对比.......

论坛徽章:
0
发表于 2007-12-26 15:43 |显示全部楼层

学习

[ 本帖最后由 wnpers 于 2007-12-26 15:51 编辑 ]
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP