Edit report at https://bugs.php.net/bug.php?id=80346&edit=1
ID: 80346
User updated 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:
cmb@php.net in my opinion as a PHP user/programmer for the last 10 years which uses a lot the
documentation, I think that we can have at least 2 alternatives:
1) make it clear in the documentation that the callback function will not only be
called when the intersection is being done/compared, but also in the sort phase (which,
to me, makes completely no sense, since the intent of the callback is exactly to make a custom
comparator between keys, not to make a custom "sorter");
2) allow a parameter to be added to the function array_intersect_ukey named
DONT_CALL_MY_CALLBACK_ON_SORT_PHASE which the user can set to true/false (again, to me makes
completely no sense calling the custom callback function in the sort phase, because it's not
intuitive and not expected by the user/programmer).
If you guys still decide to keep calling the callback function during the sort phase, I think there
should be a third parameter in the callback function function ($key1, $key2, $phase)
which tells the user whether it's in the sort or intersect phase, and the user can do something
like:
function ($key1, $key2, $phase) {
if ($phase === 'sort') {
return $key2 - $key1;
}
else if ($phase === 'intersect') {
//here comes the actual intersect callback function, where the user can do lots of
complicated math, stuff... and return TRUE or FALSE if the intersection was succesfull or not.
}
}
Previous Comments:
------------------------------------------------------------------------
[2020-11-10 13:21:05] cmb@php.net
> The docs already say that the function has to return
> negative/zero/positive [â¦]
Indeed. I consider the sorting an implementation detail, and as
such don't think we should document that; or should we?
What else would need to be documented in this regard?
FWIW, PHP 7 uses a hybrid quicksort (fewer than 16 elements
trigger insertion sort), and as such sorting has to be considered
unstable. PHP 8 still uses basically the same algorithm, but
guarantees stable order[1].
[1] <https://wiki.php.net/rfc/stable_sorting>
------------------------------------------------------------------------
[2020-11-10 12:39:42] gilperon at gmail dot com
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!
------------------------------------------------------------------------
[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.
------------------------------------------------------------------------
The remainder of the comments for this report are too long. To view
the rest of the comments, please view the bug report online at
https://bugs.php.net/bug.php?id=80346
--
Edit this bug report at https://bugs.php.net/bug.php?id=80346&edit=1