Как работает array_diff?

Ответ 1

ОБНОВЛЕНИЕ

• см. ниже для более быстрого/лучшего кода.

• поведение array_diff намного лучше в php 5.3.4, но все же ~ 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

что невероятно!

Ответ 2

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()

Задержка производительности array_diff() очевидна даже при 100 записях на массив.

Примечание.. Это решение подразумевает, что элементы в первом массиве уникальны (или они станут уникальными). Это типично для хэш-решения.

Примечание.. Решение не сохраняет индексы. Назначьте исходный индекс $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(): array_diff() потребовалось в три раза дольше для практически одной и той же задачи, если дважды использовать в script.

Ответ 3

Лучшее решение, чтобы знать, как это работает, чтобы взглянуть на его исходный код;-)
(Ну, это одна из возможностей открытого исходного кода - и если вы видите какую-то возможную оптимизацию, вы можете отправить патч;-))

Для array_diff он должен быть в ext/standard - это означает, что для PHP 5.3 он должен быть там: branches/PHP_5_3/ext/standard

И тогда файл array.c выглядит как правдоподобная цель; функция php_array_diff, строка 3381, кажется, соответствует array_diff.

(Удачи, пройдя через код: довольно долго...)

Ответ 4

Как это было поднято (см. ответ @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-код немного медленнее.

Ответ 5

Кажется, вы можете ускорить его еще больше, используя другой массив вместо того, чтобы отключать. Хотя, это использует больше памяти, что может быть проблемой, связанной с прецедентом (я не тестировал фактические различия в распределении памяти).

<?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/

Ответ 6

От PHP: "Возвращает массив, содержащий все записи из массива1, которые не присутствуют ни в одном из других массивов".

Итак, вы просто проверяете array1 на все arrayN, и любые значения в массиве1, которые не отображаются ни в одном из этих массивов, будут возвращены в новый массив.

Вам не обязательно даже перебирать все значения массива. Только для всех дополнительных массивов, проведите их значения и проверьте, имеет ли каждое значение in_array($array1, $value).