Re: [discussion] add array_usearch()

From: Date: Sat, 08 Feb 2014 18:22:46 +0000
Subject: Re: [discussion] add array_usearch()
References: 1 2 3  Groups: php.internals 
Request: Send a blank email to [email protected] to get a copy of this message
On 06/02/2014 19:55, Tjerk Meesters wrote:
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? 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;
} 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]

Thread (11 messages)

« previous php.internals (#72412) next »