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/