尝试下自己设计求差集的函数

前面我们了解了什么是数组的差集，并且试用了PHP自带的求差集函数 array_diff()。我们当然不会就此止步，我们需要更深入地探讨，才能挖掘到宝石。接下来，如果不用PHP自带的函数，让你自己实现一个求差集函数，你会怎么设计呢？
一般思路嘛，就是用两重循环……外层循环遍历 array1，内层循环遍历 array2，如果发现相等的，循环跳出；如果不相等的，就保存到数组里面。最后返回差集数组，我写下来吧……

function array_different($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;
}

那我来写个测试程序吧，来对比一下你写的函数与PHP自带的函数的效率。假设两个数组分别有 5000 个元素，那么两个函数的效率有多大差异呢？

$array_1 = array();
$array_2 = array();
for($i = 0; $i <= 5000; $i++)
{
    $array_1[$i] = mt_rand(0, 100);
    $array_2[$i] = mt_rand(0, 100);
}
/*
foreach( $array_1 as $key => $val )
{
    echo $val.',';
}
echo '<br />';
foreach( $array_2 as $key => $val )
{
    echo $val.',';
}
echo '<br />';
*/
runtime(); //计时开始 
$arr_diff = array_diff($array_1, $array_2);
echo runtime(1); //计时结束并输出计时结果
echo '<br />';
foreach( $arr_diff as $key => $val )
{
    echo $val.',';
}
runtime(); //计时开始 
$arr_diff2 = array_different($array_1, $array_2);
echo runtime(2); //计时结束并输出计时结果  
foreach( $arr_diff2 as $key => $val )
{
    echo $val.',';
}
function array_different($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 runtime($mode = 0) { 
    static $t; 
    if(!$mode) { 
        $t = microtime(); 
        return; 
    } 
    $t1 = microtime(); 
    list($m0,$s0) = explode(" ",$t);
    list($m1,$s1) = explode(" ",$t1);
    return sprintf("%.3f ms",($s1+$m1-$s0-$m0)*1000); 
}

程序运行结果：

56.119 ms        // PHP自带的 array_diff($array_1, $array_2);
2345.672 ms        // 自定义函数 array_different($array_1, $array_2)

竟然差了50倍左右的效率啊……我写的这个函数效率真是惨不忍睹。等等我改下函数，应该有更好的方法……比如遍历array1，然后判断array1里的每个元素是否在array2中，如果在，就把这个元素在array1中删除：

function array_different($array_1, $array_2)
{
    foreach ($array_1 as $key => $val) {
        if (in_array($val, $array_2, true)) {
            unset($array_1[$key]);
        }
    }
    return $array_1;
}

这次效率就高很多了，就比原生的慢3倍左右，从50倍进步到3倍了。其实还有一种方法，甚至还能超越原生的效率。我们用 array_flip() 函数将 array2 的数组键值调换，那么思路就简单了：如果键值调换后的$array2[$k]存在，那么把这个 array1 中第 key 个元素直接删掉即可。

function array_different($array_1, $array_2)
{
    $array_2 = array_flip($array_2);//将数组键值调换
    foreach ($array_1 as $key => $val) {
        if (isset($array_2[$val])) {
            unset($array_1[$key]);
        }
    }
    return $array_1;
}

运行测试程序：

48.881 ms        // PHP自带的 array_diff($array_1, $array_2);
3.443 ms        // 自定义函数 array_different($array_1, $array_2)

看，比原生的还快 10 多倍呢。为什么能那么神奇？
我明白了，因为数组的键是用 HASH 组织的，查找是相当的快，效率达O(1)。而前面我写的函数里，value 只是由 key 组织存放，本身没有索引，每次查找都是遍历。没好好利用数组是哈希表的特性，效率就差异那么大了。后面我们再挖据点东西。

参考：http://www.nowamagic.net/academy/detail/1204405

尝试下自己设计求差集的函数

微信号：腾讯云折扣返现

技术讨论QQ群： 863102326

作者: catherine

搜索

标签