Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72412
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.212.178 as permitted sender)
Message-ID: <52F675F6.6060800@gmail.com>
Date: Sat, 08 Feb 2014 18:22:46 +0000
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0
MIME-Version: 1.0
To: internals@lists.php.net
References: <CAHMUw2EkBEFnb_Qs1y6xS8AEr6dO48wSAqSWr55W3fRMuumT5Q@mail.gmail.com>	<CADq_CxrU-nkc-EnBM1T_JQdGfAEAfV8emfKgArsuEZk=LtVBTQ@mail.gmail.com> <CAHMUw2G6zeMAcQHDvZL5dWp7jrDQEMQrrCnowYUrCf2fxbo0Ow@mail.gmail.com>
In-Reply-To: <CAHMUw2G6zeMAcQHDvZL5dWp7jrDQEMQrrCnowYUrCf2fxbo0Ow@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] [discussion] add array_usearch()
From: rowan.collins@gmail.com (Rowan Collins)

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]