Попытка понять поведение array_uintersect

Question

Продолжим. Почему array_uintersect не compare values первого массива после sorting? По моему скромному мнению array_udiff и array_uintersect должны иметь схожие алгоритмы, но их нет. Зачем?

$compare = function($a, $b) use(&$iteration_count) 
    { 
    echo("$a : $b\n"); 
    $iteration_count++; 
    return strcmp($a, $b); 
    }; 

$a = array('a', 'b', 'c'); 
$b = array('x', 'y', 'z'); 

$iteration_count = 0; 
echo "array_udiff:" . json_encode(array_udiff($a, $b, $compare)) . "\n"; 
echo "iterations: $iteration_count\n\n"; 

$iteration_count = 0; 
echo "array_uintersect:" . json_encode(array_uintersect($a, $b, $compare)) . "\n"; 
echo "iterations: $iteration_count\n\n"; 

Выход

b : a 
c : b 
y : x 
z : y 
a : x 
a : b 
b : x 
b : c 
c : x 
array_udiff:["a","b","c"] 
iterations: 9 

b : a 
c : b 
y : x 
z : y 
a : x // comparison started 
b : x // but there is no comparison to skip values 
c : x 
array_uintersect:[] 
iterations: 7 

Answer 1

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

Когда элемент не найден в одном из других массивов, реализация может сделать две вещи:

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

В случае PHP последний выбран. Это имеет небольшое преимущество, поскольку оно может пропускать значения, превышающие текущий элемент, но меньше, чем последний проверенный элемент других массивов. Например:

$a = ['a.a0', 'a.a1', 'b.a2', 'c.a3']; 
$b = ['a.c0', 'd.c1']; 

function cmp_val($a, $b) 
{ 
    echo "$a <=> $b\n"; 
    return strcmp($a[0], $b[0]); 
} 

print_r(array_uintersect($a, $b, 'cmp_val')); 

Выход:

... 
-- intersect starts 
a.a0 <=> a.c0 
a.a0 <=> a.a1 <-- match 
a.a1 <=> b.a2 
b.a2 <=> d.c1 <-- no match 
c.a3 <=> d.c1 

Как вы можете видеть, он использует стратегию сравнения в первом массиве, если значение имеет место во всех других массивах, так же, как разница делает; и другая стратегия используется, если значение отсутствует в любом из других массивов.

Answer 2

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

Это может быть медленнее на 3 элементах массивов, но будет уменьшаться для больших размеров.

Answer 3

В то же время я был прав и не прав. Эти функции имеют схожие алгоритмы.

$compare = function($a, $b) use(&$iteration_count) 
    { 
    echo("$a : $b\n"); 
    $iteration_count++; 
    return strcmp($a[0], $b[0]); 
    }; 

$a = array('a1', 'b1', 'c1'); 
$b = array('a2', 'b2', 'c2'); 

$iteration_count = 0; 
echo "array_uintersect:" . json_encode(array_uintersect($a, $b, $compare)) . "\n"; 
echo "iterations: $iteration_count\n\n"; 

Выход

b1 : a1 
c1 : b1 
b2 : a2 
c2 : b2 
a1 : a2 // comparison started 
a1 : b1 // it trying to skip values after it have been matched 
b1 : b2 
b1 : c1 
c1 : c2 
array_uintersect:["a1","b1","c1"] 
iterations: 9