【原创】深思 PHP 数组遍历的差异（array_diff 的实现）

AMD-K6

原文链接： 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

kk526

$array_2 = array_flip($array_2);

这个确实存在着问题
比如，多键对应一值时，flip后，会合一。

jame298

不太明白楼上的意思,求数组差集的时候是比较数组的值,合一了也是对array_2里多键对应一值合一,再比较的时候是拿array_1里的值去比,不管array_2里的数组怎么合一,在unset时只要发现array_2里有对应的值就被unset了,应该不会出现其它的问题吧...

kk526

对不起，我开始没有看明白。
你是对的。

yongjian

因为键是进行 HASH 组织的，查找很快；
而 Value 只是由 Key 组织存放，本身没有索引，每次查找都是遍历。

这个也不一定，要看实现。double hash算法可以对静态的数组实现O(1)的查询。flip算法危险，摧毁了原始数组。