Optimisation of std::binary_search of the <algorithm> header
jay pokarna
jay.pokarna10@gmail.com
Mon May 29 11:11:00 GMT 2017
Respected Sir,
Could you give me the contact of the standard
committee which handles changes to the c++ standard.
Regards,
Jay Pokarna
On Mon, May 29, 2017 at 2:17 PM, Tim Shen <timshen@google.com> wrote:
> On Mon, May 29, 2017 at 1:05 AM, jay pokarna <jay.pokarna10@gmail.com> wrote:
>>>> The technique that I have used is square root decomposition . I think
>>>> that it will be better than the one that is implemented.
>>>
>>> And here's the problem: you *think* it will be better. Just thinking
>>> is not enough. You need to *prove* it with benchmarks that show that
>>> your technique is in fact faster than the current one.
>
> Agreed.
>
> Jay, specifically, your algorithm has the roughly the same running time:
>
> T(n) = log (sqrt(n) + 1) + log sqrt(n)
> > 2 log (n ^ 0.5)
> = 2 * 0.5 * log n
> = log n
>
> It's unclear to me whether it's better than the normal binary search
> or not. Detailed and representative benchmarks may convince more
> people.
>
>
> --
> Regards,
> Tim Shen
--
Regards,
Jay Pokarna
CS Sophomore
Wordpress | Linkedin
Birla Institute of Technology and Science, Pilani
Pilani Campus
Rajasthan - 333031.
More information about the Gcc-patches
mailing list