Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:85540
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.218.54 as permitted sender)
MIME-Version: 1.0
Date: Sun, 29 Mar 2015 23:24:21 -0700
Message-ID: <CAJCMAP7kZqNcrN-KdRPk=bUQqM4_jNpbd=D4NV9zeuRjpAoSUA@mail.gmail.com>
To: internals@lists.php.net
Content-Type: multipart/alternative; boundary=001a113cd16e62b7b205127b8892
Subject: Potential binary search optimization or feature
From: medinsky94@gmail.com (Danylo Medinsky)

--001a113cd16e62b7b205127b8892
Content-Type: text/plain; charset=UTF-8

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.

--001a113cd16e62b7b205127b8892--