Edit report at https://bugs.php.net/bug.php?id=80346&edit=1
ID: 80346
Comment by: annephillip98 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:
Thanks for the step by step tutorial. Works like a charm!
https://www.nox.plus/
Previous Comments:
------------------------------------------------------------------------
[2020-11-17 14:11:03] cmb@php.net
> 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
Like I said, I consider this sorting phase to be an implementation
detail. It is just done this way, to be more efficient in the
general case.
> allow a parameter to be added to the function
> array_intersect_ukey named DONT_CALL_MY_CALLBACK_ON_SORT_PHASE
That could easily give erroneous results. The array has to be
sorted according to the compare function.
> here comes the actual intersect callback function, where the
> user can do lots of complicated math, stuff...
If you have really time consuming complex calculations, consider
to precompute respective values, and to just look these up in the
comparison function.
------------------------------------------------------------------------
[2020-11-10 14:14:43] gilperon at gmail dot com
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.
}
}
------------------------------------------------------------------------
[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...
------------------------------------------------------------------------
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