[discussion] add array_usearch()

Hi Chris,

Consider the following examples for finding a value in an array:

array_search($value, $array, true);

current(array_keys($array, $value, true));

key(array_filter($array, function($item) use ($value) {
return $item === $value;
}));

Perhaps I've overlooked one way, but that's already three ways of doing
something similar; the difference lies in the memory behaviour, the first
being O(1) whereas the other two are O(n).

I'm not sure where you got this statement from. array_search() is
still O(n) in the worst case (when the needle is not found), which is
the best you can hope for with such an operation. It's true that the
other two are always O(n) whereas array_search() could return
sooner than a complete iteration if the needle is found before the
last element.

I was talking about memory growth, not runtime :)

My initial reaction to this is one of "ye gods, not another array_*
function", but I wouldn't be against altering the existing
array_search() so that the third parameter is a bitmask of flags, one
of which could indicate that the search should be case insensitive.
This could be done in a BC-compliant manner if the flag that indicates
strict comparisons has a value of 1.

I'm not wildly enthusiastic about another magic flags parameter, but it's
an acceptable compromise for me. The slight advantage there is that
in_array() would be bestowed upon the ability to take a callback function
as well. Something like:

if (in_array('is_numeric', $array, SEARCH_NEEDLE_IS_CALLBACK)) { ... }

Thanks, Chris

--

--

Tjerk

On Sun, Feb 9, 2014 at 2:22 AM, Rowan Collins rowan.collins@gmail.comwrote:

Consider the following examples for finding a value in an array:

array_search($value, $array, true);

current(array_keys($array, $value, true));

key(array_filter($array, function($item) use ($value) {
return $item === $value;
}));

Perhaps I've overlooked one way, but that's already three ways of doing
something similar; the difference lies in the memory behaviour, the first
being O(1) whereas the other two are O(n).

I was pondering this, and it occurred to me it could actually be cast as
an application of array_reduce(), except that that function doesn't
currently provide array keys to the callback function. Assuming a third
parameter was passed to the callback containing the current key, you could
define it thus:

function array_usearch($array, $fn) {
return array_reduce($array, function(&$result, $value, $key) use ( $fn
) {
if ( is_null($result) && $fn($value, $key) ) {
$result = $key;
}
});
}

(The invert flag would make it a little more verbose, but this would be
enough for parity with array_filter() anyway.)

This would presumably have the same memory profile as a dedicated
implementation (no array needs to be initialised, only the single return
value), and the same worst-case time performance, but without the ability
to short-cut once a match has been found.

Incidentally, in your proposal, you mentioned this:

[2] the array key is passed as the 2nd argument by using

ARRAY_USEARCH_USE_KEY

Is there a particular reason not to pass an extra parameter to
callbacks, even if it's unused?

Yeah, internal functions don't like extra parameters, e.g.:

is_numeric('123', 4);

Warning: is_numeric() expects exactly 1 parameter, 2 given in php shell
code on line 1

This would get in the way when you want to express "give the array key of
the first numeric element".

In the case of an existing function like array_filter(), I can see that
there is a small risk of a BC break if a function was reused as the
callback that could optionally take an additional parameter, and relied on
that parameter not being passed in, but that seems like a bit of an edge
case anyway, and doesn't apply to a brand new function.

Of couse, the proposed function can trivially be implemented with a
foreach loop as well, even including a short-cut once a match has been
found:

function array_usearch( $array, $fn ) {
foreach ( $array as $k => $v ) {
if ( $fn($k, $v) ) {
return $k;
}
}
return false;
}

Right; I would personally prefer this over the rather intricate use of
array_reduce() ;-) that said, array_search() and in_array() can also
be easily implemented in this fashion.

http://codepad.viper-7.com/YM8LSs

Again, I've omitted the ability to invert the matching, but there are
plenty of efficient ways of adding that.

Regards,

--
Rowan Collins
[IMSoP]

--

--

Tjerk