array_diff如何工作？

Question

array_diff()工作怎么样？它显然不能如下工作:

function array_diff($arraya, $arrayb)
{
    $diffs = array();
    foreach ($arraya as $keya => $valuea)
    {
        $equaltag = 0;
        foreach ($arrayb as $valueb)     
        {
            if ($valuea == $valueb)
            {
                $equaltag =1;
                break;
            }
        }
        if ($equaltag == o)
        {
              $diffs[$keya]=$valuea;
        }

    }
    return $diffs;                          
}                                  //couldn't be worse than this

有谁知道更好的解决方案？

编辑@animuson:

function array_diff($arraya, $arrayb)
{
    foreach ($arraya as $keya => $valuea)
    {
        if (in_array($valuea, $arrayb))
        {
            unset($arraya[$keya]);
        }
    }
    return $arraya;
}

Answer 1

user187291建议通过哈希表在PHP中完成它简直太棒了!在从这个幻想的想法中获得的肾上腺素激增之后,我甚至找到了一种方法来加快它的速度(PHP 5.3.1):

function leo_array_diff($a, $b) {
    $map = array();
    foreach($a as $val) $map[$val] = 1;
    foreach($b as $val) unset($map[$val]);
    return array_keys($map);
}

基准来自user187291的帖子:

LEO=0.0322  leo_array_diff()
ME =0.1308  my_array_diff()
YOU=4.5051  your_array_diff()
PHP=45.7114 array_diff()

即使每个阵列有100个条目,array_diff()性能滞后也很明显.

注意:此解决方案意味着第一个数组中的元素是唯一的(或者它们将变为唯一的).这是散列解决方案的典型特征.

注意:解决方案不保留索引.将原始索引分配给$ map,最后使用array_flip()来保存键.

function array_diff_pk($a, $b) {
    $map = array_flip($a);
    foreach($b as $val) unset($map[$val]);
    return array_flip($map);
}

PS:我在寻找一些array_diff()paradoxon时发现了这一点:如果在脚本中使用了两次,则array_diff()花费的时间要长三倍才能实现相同的任务.

Answer 2

UPDATE

• 请参阅下面的更快/更好的代码.

• 在php 5.3.4中,array_diff行为要好得多,但仍比Leo的函数慢10倍.

• 还值得注意的是,这些函数并不严格等同,array_diff因为它们不维护数组键,即my_array_diff(x,y) == array_values(array_diff(x,y)).

/ UPDATE

更好的解决方案是使用哈希映射

function my_array_diff($a, $b) {
    $map = $out = array();
    foreach($a as $val) $map[$val] = 1;
    foreach($b as $val) if(isset($map[$val])) $map[$val] = 0;
    foreach($map as $val => $ok) if($ok) $out[] = $val;
    return $out;
}

$a = array('A', 'B', 'C', 'D');
$b = array('X', 'C', 'A', 'Y');

print_r(my_array_diff($a, $b)); // B, D

基准

function your_array_diff($arraya, $arrayb)
{
    foreach ($arraya as $keya => $valuea)
    {
        if (in_array($valuea, $arrayb))
        {
            unset($arraya[$keya]);
        }
    }
    return $arraya;
}

$a = range(1, 10000);
$b = range(5000, 15000);

shuffle($a);
shuffle($b);

$ts = microtime(true);
my_array_diff($a, $b);
printf("ME =%.4f\n", microtime(true) - $ts);

$ts = microtime(true);
your_array_diff($a, $b);
printf("YOU=%.4f\n", microtime(true) - $ts);

结果

ME =0.0137
YOU=3.6282

任何问题？;)

而且,只是为了好玩,

$ts = microtime(true);
array_diff($a, $b);
printf("PHP=%.4f\n", microtime(true) - $ts);

结果

ME =0.0140
YOU=3.6706
PHP=19.5980

这是令人难以置信的!

Answer 3

最好的解决方案,了解它是如何工作的,看看它的源代码;-)
(嗯,这是开源的力量之一 - 如果你看到一些可能的优化,你可以提交补丁;-) )

对于array_diff,它应该在ext/standard- 这意味着,对于PHP 5.3,它应该在那里:branches/PHP_5_3/ext/standard

然后,该array.c文件看起来像一个似是而非的目标; php_array_diff线3381 的功能似乎对应array_diff.

(通过代码祝你好运:它很长......)