Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:85813
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.218.52 as permitted sender)
MIME-Version: 1.0
Sender: yohgaki@gmail.com
In-Reply-To: <CAJCMAP71C5kr5CNrprAkTc+7_y6WQ521pXdTGyk-=GgaFaEusA@mail.gmail.com>
References: <CAJCMAP7kZqNcrN-KdRPk=bUQqM4_jNpbd=D4NV9zeuRjpAoSUA@mail.gmail.com>
 <CAJCMAP71C5kr5CNrprAkTc+7_y6WQ521pXdTGyk-=GgaFaEusA@mail.gmail.com>
Date: Wed, 15 Apr 2015 04:41:44 +0900
Message-ID: <CAGa2bXa82jc8EG1U8Rn1mjVf5o8-bZMB3DjoEvC+aHJwNUmGaQ@mail.gmail.com>
To: Danylo Medinsky <medinsky94@gmail.com>
Cc: "internals@lists.php.net" <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a113df3b60b90200513b46e17
Subject: Re: [PHP-DEV] Re: Potential binary search optimization or feature
From: yohgaki@ohgaki.net (Yasuo Ohgaki)

--001a113df3b60b90200513b46e17
Content-Type: text/plain; charset=UTF-8

Hi Danylo,

On Wed, Apr 15, 2015 at 3:23 AM, Danylo Medinsky <medinsky94@gmail.com>
wrote:

> Thanks for the feedback and apologies for the late response.
>
> Since my posting and your responses, I began implementing the binary search
> into array.c. After a couple days of coding and research, I managed to
> produce this code.
>
>     HashTable *arr_hash;
>     arr_hash = Z_ARRVAL_P(array);
>     int low=0;
>     int high=zend_hash_num_elements(arr_hash);
>     int mid;
>     zval res;
>     while(low&lt;=high){
>             mid=(low+high)/2;
>             ZVAL_DEREF(entry);
>             entry = zend_hash_index_find(arr_hash, mid);
>             compare_function(&amp;res,entry,value);
>             //php_printf("%ld\n", Z_LVAL(res));
>          if(Z_LVAL(res) &gt; 0){
>             high=mid-1;
>          }else if(Z_LVAL(res) &lt; 0){
>             low=mid+1;
>          }else{
>             RETURN_TRUE;
>          }
>     }
>     RETURN_FALSE;
>
>
> After benchmarking this code, I managed to conclude that this binary search
> algorithm preforms vastly quicker then the php_search_array function. Based
> on these results I believe that this algorithm would be a good optimization
> or feature to add to PHP. Based on the feedback I have received from you
> guys, I am holding off the sort flag in the binary search function
> parameters until I can determine how much performance will be compromised
> from the sorting.
>
> At the moment I am trying to figure out if my function would be considered
> a minor or major chance since if it is a major/large change, I will require
> a RFC in order to submit a pull request.
>
> If anybody has any additional feedback or recommendations, feel free to
> reply to this post.
>

Since array has state, making it a class makes sense.
It would be better if it implemented as array class. You can keep
sorted state if you use class.

Natural place would be SplArray, but the implementation is overly
complex...

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

--001a113df3b60b90200513b46e17--