Skip to content
Advertisement

Why does array_uintersect() compare elements between array1 & array2, array1 & array1, and array2 & array2?

Test script

$i = 0;
array_uintersect(['foo', 'bar'], ['baz', 'qux'], function($a, $b) use (&$i) {
    print_r([$a, $b, $i++]);
});

Actual Result

Array
(
    [0] => bar
    [1] => foo
    [2] => 0
)
Array
(
    [0] => qux
    [1] => baz
    [2] => 1
)
Array
(
    [0] => bar
    [1] => qux
    [2] => 2
)
Array
(
    [0] => bar
    [1] => foo
    [2] => 3
)

Expected Result

Array
(
    [0] => foo
    [1] => baz
    [2] => 0
)
Array
(
    [0] => bar
    [1] => qux
    [2] => 1
)

In other words, what I am expecting to be passed to the callback is the current element of the left array, and the current element of the right array.

Furthermore, I would expect the same logic to apply if I were to pass an additional array to array_uintersect – one more argument being passed to the callback ($c, for example).

Can someone explain this behaviour?

Advertisement

Answer

What’s not mentioned in the array_uintersect docs is that, internally, PHP sorts all the arrays first, left to right. Only after the arrays are sorted does PHP walk them (again, left to right) to find the intersection.

The third argument (the comparison function) is passed to the internal sort algorithm, not the intersecting algorithm. Thus, the debugging output seen is the sorting algorithm figuring out the ordering.

The zend_sort implementation generally uses a bisecting quick sort implementation. For arrays of the size in your example, PHP uses insertion sort. For large arrays, PHP uses a 3 or 5 point pivot so as to improve worst-case complexity.

Since you’re not explicitly returning any value from the comparison function, PHP defaults to returning null (0), and since PHP is using insertion sort, you’re seeing O(n*n) behavior as the sort walks all the combinations.

User contributions licensed under: CC BY-SA
9 People found this is helpful
Advertisement