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

UPDATE

• see below更快/更好的代码。

• array_diff在PHP 5.3.4中的行为好得多，但仍比Leo的函数慢10倍。

• 也值得注意的是，这些函数并不严格等同于array_diff，因为它们没有维护数组密钥，即my_array_diff(x,y) == array_values(array_diff(x,y))。

/UPDATE

更好的解决方案是使用hash maps

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 2

最好的解决办法知道它是如何工作它来看看它的源代码;-)
（嗯，这是开源的力量之一 - 如果你看到一些可能的优化，你可以提交一个补丁;-)）

对于和array_diff，应当在ext/standard - 这意味着，对于PHP 5.3，应该还有：branches/PHP_5_3/ext/standard

然后，array.c文件看起来像是一个合理的目标;函数行3381的php_array_diff似乎对应于array_diff。

（去祝你好运通过代码：这是相当长的...）

Answer 3

从PHP：“返回包含所有在array1中不存在任何其他阵列的条目数组“。

所以，你只需要检查阵列1对所有arrayN任何值阵列1没有出现在任何这些阵列将在一个新的数组返回。

您不一定需要遍历所有array1的值。只是为了所有附加数组，循环它们的值并检查每个值是否为in_array($array1, $value)。

Answer 4

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 5

由于这已被提出（见@ BurninLeo的答案），这样的事情呢？

function binary_array_diff($a, $b) { 
    $result = $a; 
    asort($a); 
    asort($b); 
    list($bKey, $bVal) = each($b); 
    foreach ($a as $aKey => $aVal) { 
     while ($aVal > $bVal) { 
      list($bKey, $bVal) = each($b); 
     } 
     if ($aVal === $bVal) { 
      unset($result[$aKey]); 
     } 
    } 
    return $result; 
} 

执行一些测试后，结果似乎可以接受的：

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

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

$ts = microtime(true); 
for ($n = 0; $n < 10; ++$n) { 
    array_diff($a, $b); 
} 
printf("PHP => %.4f\n", microtime(true) - $ts); 

$ts = microtime(true); 
for ($n = 0; $n < 10; ++$n) { 
    binary_array_diff($a, $b); 
} 
printf("binary => %.4f\n", microtime(true) - $ts); 

$binaryResult = binary_array_diff($a, $b); 
$phpResult = array_diff($a, $b); 
if ($binaryResult == $phpResult && array_keys($binaryResult) == array_keys($phpResult)) { 
    echo "returned arrays are the same\n"; 
} 

输出：

PHP => 1.3018 
binary => 1.3601 
returned arrays are the same 

当然，PHP代码不能执行如C代码一样好，因此没有不知道PHP代码有点慢。

Answer 6

看来你可以通过使用另一个数组而不是取消设置来加快速度。虽然，这使用更多的内存，这可能是一个问题，取决于用例（我没有测试内存分配的实际差异）。

<?php 
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; 
} 
function leo_array_diff($a, $b) { 
    $map = $out = array(); 
    foreach($a as $val) $map[$val] = 1; 
    foreach($b as $val) unset($map[$val]); 
    return array_keys($map); 
} 
function flip_array_diff_key($b, $a) { 
    $at = array_flip($a); 
    $bt = array_flip($b); 
    $d = array_diff_key($bt, $at); 
    return array_keys($d); 
} 
function flip_isset_diff($b, $a) { 
    $at = array_flip($a); 
    $d = array(); 
    foreach ($b as $i) 
    if (!isset($at[$i])) 
     $d[] = $i; 
    return $d; 
} 
function large_array_diff($b, $a) { 
    $at = array(); 
    foreach ($a as $i) 
    $at[$i] = 1; 
    $d = array(); 
    foreach ($b as $i) 
    if (!isset($at[$i])) 
     $d[] = $i; 
    return $d; 
} 

$functions = array("flip_array_diff_key", "flip_isset_diff", "large_array_diff", "leo_array_diff", "my_array_diff", "array_diff"); 
#$functions = array_reverse($functions); 
$l = range(1, 1000000); 
$l2 = range(1, 1000000, 2); 

foreach ($functions as $function) { 
    $ts = microtime(true); 
    for ($i = 0; $i < 10; $i++) { 
    $f = $function($l, $l2); 
    } 
    $te = microtime(true); 
    $timing[$function] = $te - $ts; 
} 
asort($timing); 
print_r($timing); 

我时序为（PHP 5.3.27-1〜dotdeb.0）：

[flip_isset_diff] => 3.7415699958801 
[flip_array_diff_key] => 4.2989008426666 
[large_array_diff] => 4.7882599830627 
[flip_flip_isset_diff] => 5.0816700458527 
[leo_array_diff] => 11.086831092834 
[my_array_diff] => 14.563184976578 
[array_diff] => 99.379411935806 

这三个新的职能在http://shiplu.mokadd.im/topics/performance-optimization/