Re: Binary Search
On 3/24/2011 8:26 AM, Joshua Cranmer wrote:
On 03/24/2011 10:38 AM, Roedy Green wrote:
On Thu, 24 Mar 2011 04:38:06 -0500, Leif Roar Moldskred
<leifm@dimnakorr.com> wrote, quoted or indirectly quoted someone who
said :
Why not just use a TreeSet?
Because it is a hammer for removing fleas. I'm thinking of sets of
less than 20 elements. For small sets, I think you could get better
performance and certainly better RAM usage with something specialised
for small sets. I will probably invent something, where I can have a
little set attached to each of many objects then I can have a bakeoff
with a TreeSet to see where the break point is.
On the order of 20 elements, a simple unsorted array is good enough
performance for anything you want to do, unless that code is really hot,
in which case you probably need to roll your own specific data-structure
for the task at hand.
Specifically, if n is less than 20 then n/(log_2(n)) is less than 5.
Clearly constant factors matter.
Branch prediction can be important for this. A linear search has a
single path that dominates, with one branch per search going the other
way. A binary search does multiple branches whose direction depends on
the comparison between the probe key and the split element.
I agree that this should be kept simple unless it is very hot.
If it is very hot, the choice of structure will depend on things like
how frequently it is updated, the proportion of searches that miss or
that hit in specific areas of the array, and the predictability of the
branch pattern. I would want to measure in context, rather than
depending on a freestanding bakeoff.
Patricia