Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Binary Search

Reply
Thread Tools

Binary Search

 
 
Roedy Green
Guest
Posts: n/a
 
      03-24-2011
Is there some reason Java has no built-in Collection that keeps a
sorted linear list and searches by binary search? You need something
light weight and fast for small sets. Would such a beast just not fit
into any of the interfaces?

--
Roedy Green Canadian Mind Products
http://mindprod.com
If you think it’s expensive to hire a professional to do the job, wait until you hire an amateur.
~ Red Adair

 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      03-24-2011
On 3/24/2011 5:08 AM, Roedy Green wrote:
> Is there some reason Java has no built-in Collection that keeps a
> sorted linear list and searches by binary search? You need something
> light weight and fast for small sets. Would such a beast just not fit
> into any of the interfaces?


TreeSet has the capabilities you want, I think. I'm not sure
what your threshold for "light weight" is, but if you're interested
in "small sets" binary search offers few benefits.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
 
 
 
Roedy Green
Guest
Posts: n/a
 
      03-24-2011
On Thu, 24 Mar 2011 04:38:06 -0500, Leif Roar Moldskred
<(E-Mail Removed)> 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.
--
Roedy Green Canadian Mind Products
http://mindprod.com
If you think it’s expensive to hire a professional to do the job, wait until you hire an amateur.
~ Red Adair

 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      03-24-2011
On 03/24/2011 10:38 AM, Roedy Green wrote:
> On Thu, 24 Mar 2011 04:38:06 -0500, Leif Roar Moldskred
> <(E-Mail Removed)> 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.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      03-24-2011
On 03/24/2011 05:08 AM, Roedy Green wrote:
> Is there some reason Java has no built-in Collection that keeps a
> sorted linear list and searches by binary search? You need something
> light weight and fast for small sets. Would such a beast just not fit
> into any of the interfaces?


For small sets, binary search provides negligible benefit over any other.
Big-O analysis applies only for sufficiently large n. Below the cutoff,
performance of your treasured algorithm could be much worse than the linear
alternative.

All right, it cannot be much worse, because THE SET IS SMALL!

--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedi.../c/cf/Friz.jpg
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      03-24-2011
On Thu, 24 Mar 2011 09:58:40 -0500, Leif Roar Moldskred
<(E-Mail Removed)> wrote, quoted or indirectly quoted someone who
said :

>For that small sets the difference in performance between a custom-made
>"BinarySearchableList" and TreeSet will either be insignificant to the
>overall program performance or so critical that you'll want to use
>arrays instead of lists anyway.


It will matter if you have sufficiently large numbers of these sets.
You will spend more RAM on overhead than data.

The problem is, Map and SortedMap don't "map" well onto binary search.
binary search to work properly requires embedded keys. Maps require
them separate.
--
Roedy Green Canadian Mind Products
http://mindprod.com
If you think it’s expensive to hire a professional to do the job, wait until you hire an amateur.
~ Red Adair

 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      03-24-2011
On Thu, 24 Mar 2011 08:02:05 -0700, Peter Duniho
<(E-Mail Removed)> wrote, quoted or indirectly quoted
someone who said :

>Maintaining a list in sorted order is expensive if the list is stored as
>a simple linear list (whether linked or, even worse, array-based).


The pattern I often work with is the elements are known at compile
time or when the program first starts, and from then on are
effectively read-only.

I thought you might replace the entire array on every add, and sort
on the first lookup. This as slow to build, but has a simple sorted
array of the exact size for lookup.
--
Roedy Green Canadian Mind Products
http://mindprod.com
If you think it’s expensive to hire a professional to do the job, wait until you hire an amateur.
~ Red Adair

 
Reply With Quote
 
markspace
Guest
Posts: n/a
 
      03-25-2011
On 3/24/2011 4:44 PM, Roedy Green wrote:

>
> The pattern I often work with is the elements are known at compile
> time or when the program first starts, and from then on are
> effectively read-only.


For data known at compile time, it seems like Arrays.sort() and
Arrays.binarySearch() might be the way to go.
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      03-25-2011
On Thu, 24 Mar 2011 18:59:03 -0500, Leif Roar Moldskred
<(E-Mail Removed)> wrote, quoted or indirectly quoted someone who
said :

>In which case you'll want to use arrays instead, anyway.


Then we lose encapsulation.
--
Roedy Green Canadian Mind Products
http://mindprod.com
If you think it’s expensive to hire a professional to do the job, wait until you hire an amateur.
~ Red Adair

 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      03-25-2011
On 3/24/2011 8:37 PM, Roedy Green wrote:
> On Thu, 24 Mar 2011 18:59:03 -0500, Leif Roar Moldskred
> <(E-Mail Removed)> wrote, quoted or indirectly quoted someone who
> said :
>
>> In which case you'll want to use arrays instead, anyway.

>
> Then we lose encapsulation.


If the searching of these sets is so frequent that the code
deserves this kind of micro-optimization, one of the first micro-
optimizations you should make is to jettison encapsulation and
many other shibboleths, too: You can't afford them.

Contrapositive corollary: If you believe you can afford them,
you should also believe you don't need that much optimization.

Semi-rhetorical (but only semi-) question: Why are you using
Java-with-all-its-overheads instead of assembly code? If your
answer is "I don't need speed *that* badly," my rejoinder is
"The defense rests."

--
Eric Sosman
(E-Mail Removed)d
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
binary search has a longer combinational delay than linear search sanborne VHDL 5 12-18-2009 10:27 PM
beginner with C : quick search or binary search help needed with forand while bpascal123@googlemail.com C Programming 9 07-03-2009 08:00 PM
Help understand probems - Binary Search and Sequenital Search Timmy C++ 5 07-09-2007 02:41 PM
Binary Search to search linearizer table? Andy C Programming 1 11-25-2003 04:40 AM



Advertisments