Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:85544
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.212.181 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <CAJCMAP7kZqNcrN-KdRPk=bUQqM4_jNpbd=D4NV9zeuRjpAoSUA@mail.gmail.com>
References: <CAJCMAP7kZqNcrN-KdRPk=bUQqM4_jNpbd=D4NV9zeuRjpAoSUA@mail.gmail.com>
Date: Mon, 30 Mar 2015 11:12:45 +0200
Message-ID: <CAF+90c_5NxLk_YufmSA0=XWcao1-R_bRdtCA3k7q+-pQqd33MQ@mail.gmail.com>
To: Danylo Medinsky <medinsky94@gmail.com>
Cc: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a1135e4629546fb05127de256
Subject: Re: [PHP-DEV] Potential binary search optimization or feature
From: nikita.ppv@gmail.com (Nikita Popov)

--001a1135e4629546fb05127de256
Content-Type: text/plain; charset=UTF-8

On Mon, Mar 30, 2015 at 8:24 AM, Danylo Medinsky <medinsky94@gmail.com>
wrote:

> Recently, as part of school course on optimization, I have identified a
> potential optimization or feature for PHP. After looking through the
> array.c file(located in etc/standard in the PHP source code), I noticed
> that both the in_array and array_search are using the linear search C
> function php_search_array. The potential issue I see is that even though
> the linear search algorithm does not drastically effect performance when
> searching a relatively small array, it may slow performance down when
> iterating through a very large array(couple of million indexes).
>
> To back this fact up I preformed some benchmarks using a PHP script that
> measures the time it takes to preform a linear search and binary search.
> The benchmark was in favor of the binary search as it found its target many
> times quicker compared to the linear search.
>
> After researching more about different PHP search functions, I was not able
> to find one that uses a binary search algorithm. Based on these factors I
> believe that a binary search implementation into PHP will prove useful in
> certain situations and would like to implement that feature.
>
> At the moment I am debating between adding a separate binary search based
> function into array.c or modifying the current array_search_array function
> to utilize a binary search algorithm. Since the requirement for a binary
> search is that the array being searched is sorted, I thought is would be a
> good idea to have a Boolean parameter in the binary search function to
> specify if the input array should be sorted or not. something among the
> lines of "function binary_search(string target, array arrayToSearch, bool
> sort)". Doing this, the function can preform a sort if required to, thus
> not needing to sort a array that is already sorted.
>
> Before I can begin the implementation and create a pull request, I would
> like to know the PHP's community feedback on my potential contribution and
> if this is a wise feature to change or implement.
>


If you need to find an element in an array you should make the lookup key
based. I.e. you save elements as $array[$value] = true and then check
isset($array[$value]). This operation is O(1), as opposed to O(log n) for
binary search and O(n) for linear search.

Using binary search in PHP only makes sense if the elements in the array
cannot be used as keys - where the only reasonable use case I see are
objects, which at least currently do not support comparison operator
overloading, so a binary search implementation would have to accept a
comparator function.

Also the concept of adding a $sort parameter to a binsearch function
doesn't make much sense to me. Sorting the array is more expensive than
doing a linear search.

Nikita

--001a1135e4629546fb05127de256--