automake
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: A new, novel, and faster Binary Search algorithm


From: Paul Smith
Subject: Re: A new, novel, and faster Binary Search algorithm
Date: Fri, 15 Mar 2019 13:40:13 -0400

On 3/15/19 6:16 AM, Gregorius van den Hoven wrote:
> > My apologies. The algorithm is licensed under GPL 3 so it
> > seemed relevant to the GNU community to me. Do you have a
> > suggestion for a more appropriate mailing list?

I don't see any need for the somewhat harsh response you received
initially.  Any effort spent on base algorithms is appreciated; even
the benchmarking work is a valuable contribution.

Just to orient you, Gegorius, it could well be that your efforts are of
interest to the GNU community; however the automake project in
particular develops a tool which uses the shell and a macro language to
convert Makefile templates into standard Makefiles: this project will
not have much need for the work you've done (directly).


On Fri, 2019-03-15 at 08:44 -0500, Eric Blake wrote:
> 
> Perhaps GNU coreutils (address@hidden), as the owner of the
> sort(1) utility, which would be the most likely program to pick up
> the use of this code?  Or to glibc, to see if it is worth improving
> qsort() by using the ideas in your algorithm?

Coreutils: https://www.gnu.org/software/coreutils/
GNU libc:  https://www.gnu.org/software/libc/libc.html

Those are good suggestions.  I might also suggest contacting the Gnulib
folks who maintain a suite of common library functions that many GNU
tools use: https://www.gnu.org/software/gnulib/

Although it's off-topic for this list, one thing you might consider in
your benchmarking before publishing further is being more clear about
the relative number of key checks per algorithm.  Binary searches on
integers are likely not the most common type for qsort() and other
general-purpose binary searches: searching on strings is likely much
more common.  There the cost of the key checks dwarfs the rest of the
costs so algorithms with the fewest key checks will perform better.

Thanks for your work and interest in the GNU project!




reply via email to

[Prev in Thread] Current Thread [Next in Thread]