Edit report at https://bugs.php.net/bug.php?id=80346&edit=1
ID: 80346
Comment by: gilperon at gmail dot com
Reported by: gilperon at gmail dot com
Summary: Function array_intersect_ukeyrequires consistent
comparison function
Status: Open
Type: Documentation Problem
Package: Arrays related
Operating System: ALL
PHP Version: 7.4.12
Block user comment: N
Private report: N
New Comment:
requinix@php.net
Thank you for your explanations. I just think that for some strange reason this
array_intersect_ukey function is much much much slower than
array_intersect_key (without callback). It should be a little bit slower, but not by a
lot. I will create a new test script and post so you can check what I am saying.
And I still firmly believe that makes no sense calling the callback function when the algorithm of
array_intersect_ukey is in the sort phase, also, if this cant be changed,
it would be nice to the user to know if it is in the sort phase and not in the
intersect phase so I could use a much more complex function in the
intersect phase (which is my case, I have a very complex intersection code which makes
no sense being run in the sort phase because just makes everything much slower than it already is).
Regarding writing a function on my own to do what I want, no matter what I come up, it is always at
least 10x slower than native PHP functions. PHP is doing some really good magic because even using
Golang to benchmark same script, PHP still is faster when working with arrays!
Previous Comments:
------------------------------------------------------------------------
[2020-11-10 02:34:14] requinix@php.net
> Thank you guys, but I think that most users will assume that the callback
> function will only be called when the comparson between the keys are effectively
> being done.
The docs already say that the function has to return negative/zero/positive - not simply
same/different - and following those instructions will make the process work regardless of whether
it did a O(n log n) sort-and-check or the naive O(n^2) intersection.
> So is there a way to tell PHP not to sort the arrays and leave them untouched and just
> do the intersect, as it should?
No, you'll get the best case of O(n log n) for the sort then O(n) for the intersection.
At least I assume that's the best case. I don't remember what algorithm PHP uses now -
used to be quicksort but I think it changed.
If you need to sort the arrays for other reasons, write out a userland implementation of an
intersection and profile the result. It could be that the "slow" user code beats out the
"fast" sorts.
(The implementation: two concurrent iterators on both arrays, running beginning to end, where each
one advances or not based on a comparison of their respective current items.)
> is there a way to me to check, inside the callback function, if the keys being
> compared are in the "sort" phase or in the "intersect" phase?
Not really. Does it matter? I can't imagine why...
------------------------------------------------------------------------
[2020-11-10 02:08:38] gilperon at gmail dot com
Thank you guys, but I think that most users will assume that the callback function will only be
called when the comparson between the keys are effectively being done. I think most people will
never assume that the callback will be called during the "sort" phase, which by the way,
there is no single line saying that array_intersect (or similars) will sort the arrays previously.
Also, I am running a very CPU intensive algorithm and I am trying to optimize every bit and because
of the way my algorithm works, it already sorts the data before calling array_intersect. So is there
a way to tell PHP not to sort the arrays and leave them untouched and just do the intersect, as it
should?
I think that it's not obvious to users to know that array_intersect (or similars)
will sort the arrays before actually doing what it's meant to do. If so, it should be called
array_sort_intersect or at least allow a FLAG to be set if the user already sorted the
arrays by himself.
Anyway, is there a way to me to check, inside the callback function, if the keys being compared are
in the "sort" phase or in the "intersect" phase?
------------------------------------------------------------------------
[2020-11-10 01:57:36] requinix@php.net
Indeed, this is user error: as with every other array sorting function (and the intersect/diff
functions *do* perform sorting - for efficiency), the callback needs to be consistent in its
comparisons. It must return less than/equal to/greater than, and doing something else will likely
result in "garbage in, garbage out" behavior.
This matter is going to be common to all sorting, intersection, diff, etc. functions. If the docs
are amended then I suggest some ©pasta; for each affected page.
PS: Returning $key2 - $key1 is technically backwards, but the final sort order doesn't really
matter since this function only cares about equality between elements.
------------------------------------------------------------------------
[2020-11-10 01:32:41] danack@php.net
Changing the code:
echo "DIFFERENT\n";
return 1;
to:
echo "DIFFERENT\n";
return $key2 - $key1;
Makes your code work.
It looks like this code may be sorting the arrays first, and sorting algorithms need to be stable:
https://www.geeksforgeeks.org/stability-in-sorting-algorithms/
That's an educated guess. If it is that, it's a docs problem as stability probably should
be mentioned.
------------------------------------------------------------------------
[2020-11-10 01:21:38] gilperon at gmail dot com
Description:
------------
Run the test script. It has 2 arrays in such a way that only the key 4 appears on both.
Using array_intersect_ukey does not return 4, instead it returns
array(0) {}. Using array_intersect_key works perfectly. I also realized
there is a bug in the implementation of this function, because if you run the test script it will
show you this:
|4|6|DIFFERENT
|8|6|DIFFERENT
|4|8|DIFFERENT
|3|4|DIFFERENT
|5|4|DIFFERENT
|3|5|DIFFERENT
|6|4|DIFFERENT
|6|5|DIFFERENT
|6|3|DIFFERENT
It shouldnt be comparing 8 with 6 because these keys only appear on the 1st array and these keys
shouldnt be compared at all. You can clearly see that this function, instead of comparing each key
of the first array with each key of the second array, it's comparing the keys from the first
array WITH ITSELF and then comparing the keys of the second array ITSELF (line |3|5|) and only then
comparing the keys of both arrays together (but for some reason it misses the |4|4|).
I know that in my simple use case I should be using array_intersect_key but I really
need array_intersect_ukey to work properly because I have a much more complex use case
for it.
Test script:
---------------
<?php
$array1 = array(4 => true, 6 => true, 8 => true);
$array2 = array(3 => true, 4 => true, 5 => true);
var_dump(array_intersect_ukey(
$array1,
$array2,
function ($key1, $key2) {
echo "|" . $key1 . "|" . $key2 . "|";
if ($key1 === $key2) {
echo "EQUAL\n";
return 0;
}
else{
echo "DIFFERENT\n";
return 1;
}
}
));
?>
Expected result:
----------------
It should only show the element 4, which is present in both arrays.
Actual result:
--------------
Nothing is returned from the intersection.
------------------------------------------------------------------------
--
Edit this bug report at https://bugs.php.net/bug.php?id=80346&edit=1