Edit report at https://bugs.php.net/bug.php?id=70763&edit=1
ID: 70763
Updated by: requinix@php.net
Reported by: jonjohnson1 at yandex dot com
Summary: Bug in array_udiff()?
-Status: Open
+Status: Not a bug
Type: Bug
Package: *General Issues
Operating System: Windows
PHP Version: 5.6.14
Block user comment: N
Private report: N
New Comment:
Thanks for the userland implementation, @inefedor.
The inconsistent/wrong results are because the comparison function is not valid: as the
documentation says, it must return <0, 0, or >0 according to how the two arguments compare.
Always returning 0/1 or 0/-1 or true/false will cause problems.
"Why return integers?" Because array_udiff() performs a sort on the two arrays before
comparing items. "Why sort? Wouldn't it be better to just compare items in the two
arrays?" Actually no. It's a matter of efficiency:
Consider two arrays of 100 random values. By simply comparing each item with each other item the
function would perform on average 50 (half the size of the array) comparisons for each element for
100*50=5000 comparisons total. Scaling up the size of the arrays shows that this method is O(n^2)
complexity.
https://www.google.com/search?q=algorithm+complexity+and+big+o+notation
By presorting the two arrays, more steps are required but less work is done. Sorting is O(n log n)
which is faster than O(n^2). That's done twice. Then the function compares pairs of elements
from the two arrays. Since it knows that previous elements are "less than" or "equal
to" the current, and that future elements are "equal to" or "greater than",
it only needs to make O(n) comparisons. All together the three phases of the algorithm total up to
O(n log n) complexity and thus it is generally faster.
A quick test shows that sorting an array of 100 distinct random values takes about 650 comparisons.
With our two arrays that's 1300 comparisons. It looks like a worst case for the third phase is
two comparisons per element so that's 2*100=200. In total that's around 1500 comparisons -
far fewer than 5000.
Demonstration: https://3v4l.org/fN5Zt
Phase 1 is sorting the first array. You can see it comparing only pairs of elements from the first
array.
Phase 2 is sorting the second array. Again, only comparing pairs from the second array.
Phase 3 is the comparison work. It moves two "pointers" through the first and second
arrays, comparing as it goes. Based on the result it will advance one of the pointers and perform
another comparison. Eventually it runs out of elements in the first array and stops.
tldr: fix your comparison function.
Previous Comments:
------------------------------------------------------------------------
[2016-05-16 19:24:44] inefedor at gmail dot com
Here's how array_udiff works under the hood: https://3v4l.org/P5JdW
It produces wrong result for you because the comparison function is incorrect. It should return -1
(or any integer less than zero) if $left is less than $right, 1 (or any integer greater than zero)
if $left is greater than $right, and 0 if they are equal.
------------------------------------------------------------------------
[2016-05-16 18:15:02] panguzol at gmail dot com
Sorry, I made mistake in last example. It should be
```
echo '#5 ';
$r = array_udiff($a, $b, function($x, $y) {
return (int)!($x === $y);
});
var_dump($r);
```
Actual result:
```
#5 array(5) { [0]=> int(1) [1]=> int(2) [2]=> int(3) [3]=> int(4) [4]=> int(5) }
```
------------------------------------------------------------------------
[2016-05-16 18:05:33] panguzol at gmail dot com
Test code
```
<?php
$a = [1,2,3,4,5];
$b = [2,3,5];
echo '#1 ';
$r = array_udiff($a, $b, function($x, $y) {
return $x === $y ? 0 : -1;
});
var_dump($r);
echo '<br />';
echo '#2 ';
$r = array_udiff($a, $b, function($x, $y) {
return $x === $y ? 0 : 1;
});
var_dump($r);
echo '<br />';
echo '#3 ';
$r = array_udiff($a, $b, function($x, $y) {
return $x - $y;
});
var_dump($r);
echo '<br />';
echo '#4 ';
$r = array_udiff($a, $b, function($x, $y) {
return $y - $x;
});
var_dump($r);
echo '<br />';
echo '#5 ';
$r = array_udiff($a, $b, function($x, $y) {
return (int)!$x === $y;
});
var_dump($r);
?>
```
Expected output:
```
#1 array(2) { [0]=> int(1) [3]=> int(4) }
#2 array(2) { [0]=> int(1) [3]=> int(4) }
#3 array(2) { [0]=> int(1) [3]=> int(4) }
#4 array(2) { [0]=> int(1) [3]=> int(4) }
#5 array(2) { [0]=> int(1) [3]=> int(4) }
```
Actual output
```
#1 array(2) { [0]=> int(1) [3]=> int(4) }
#2 array(5) { [0]=> int(1) [1]=> int(2) [2]=> int(3) [3]=> int(4) [4]=> int(5) }
#3 array(2) { [0]=> int(1) [3]=> int(4) }
#4 array(2) { [0]=> int(1) [3]=> int(4) }
#5 array(0) { }
```
As we can see in cases #2 and #5 we got wrong result.
PS: Why comparison function must return integer not boolean? It shouldn't make difference
whether other element is bigger or smaller, just is it equal or not.
------------------------------------------------------------------------
[2015-10-21 21:16:04] jonjohnson1 at yandex dot com
Description:
------------
function value_compare_func($a, $b){
if ($a === 'n_3') {
return 0;
}
return 1;
}
$array1 = array("n_1", "n_2", "n_3", "n_4" );
$array2 = array("green");
$result = array_udiff($array1, $array2, "value_compare_func");
print_r($result);
The expected output is:
Array([0] => 'n_1', [1] => 'n_2' , [3] => 'n_4' )
But PHP outputs:
Array([1] => 'n_2' , [3] => 'n_4' )
Where is n_1?
Test script:
---------------
$array1 = array("n_1", "n_2", "n_3", "n_4" );
$array2 = array("green");
$result = array_udiff($array1, $array2, "value_compare_func");
print_r($result);
Expected result:
----------------
Array([0] => 'n_1', [1] => 'n_2' , [3] => 'n_4' )
Actual result:
--------------
Array([1] => 'n_2' , [3] => 'n_4' )
------------------------------------------------------------------------
--
Edit this bug report at https://bugs.php.net/bug.php?id=70763&edit=1