Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Binary Search

Reply
Thread Tools

Binary Search

 
 
Lawrence D'Oliveiro
Guest
Posts: n/a
 
      04-03-2011
In message <in7h0u$apu$(E-Mail Removed)>, Mike Schilling wrote:

> "Leif Roar Moldskred" <(E-Mail Removed)> wrote in message
> news(E-Mail Removed)...
>
>> Mike Schilling <(E-Mail Removed)> wrote:
>>>
>>> For a SortedMap, specify a Comparator that knows.

>>
>> Eh? How is that going to give you a key?

>
> It's going to give you an ordering for the binary search.


The Python folks discovered this the hard way: providing a comparator
callback is slow. It’s better to provide a key-accessor callback, and let
the sort algorithm do the comparison.
 
Reply With Quote
 
 
 
 
Tom Anderson
Guest
Posts: n/a
 
      04-03-2011
On Sat, 2 Apr 2011, Mike Schilling wrote:

> "Tom Anderson" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) rth.li...
>> On Sat, 2 Apr 2011, Mike Schilling wrote:
>>
>>> "Lawrence D'Oliveiro" <(E-Mail Removed)_zealand> wrote in message
>>> news:in6oj8$5b5$(E-Mail Removed)...
>>>> In message <imp8c9$nkf$(E-Mail Removed)>, Mike Schilling wrote:
>>>>
>>>>> "Lawrence D'Oliveiro" <(E-Mail Removed)_zealand> wrote in
>>>>> message
>>>>> news:imouja$56s$(E-Mail Removed)...
>>>>>
>>>>>> In message <(E-Mail Removed)>, Roedy Green
>>>>>> wrote:
>>>>>>
>>>>>>> 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.
>>>>>>
>>>>>> Sounds like the Java Map classes are not well designed.
>>>>>
>>>>> Or that someone doesn't understand them. Embedded keys can be made
>>>>> to work perfectly well with SortedMaps simply by making both
>>>>> arguments to put() the same, and providing a comparator that can
>>>>> locate the key in the object.
>>>>
>>>> So why isn’t there a single-argument overload of the put method to
>>>> save you the trouble?

>>
>> Mind you, with an embedded key, i'm not sure how you'd do lookups even
>> with a map. To retrieve some object, wouldn't you need to have it to
>> hand in the first place, to be able to pass in its embedded key? Or
>> would you also support lookup by freestanding key?

>
> You can look it up with an object that's equal to (as opposed to
> identical to) the one embedded in the value. But you knew that.


Yes, and i tried not to think about it, because it's smelly. How do you
obtain these objects? Do you make them purely to use as key-holders? Does
that mean you're going to have half-filled-out instances of your value
class floating about the place? Does that mean you have to provide a
constructor that allows such instances to be created, so abandoning the
invariants that you could otherwise enforce through your constructors?

Or do you need to do something like:

public interface KeyHolder {
public String getKey();
}

public class Value implements KeyHolder {
private final String key;
// other fields
public String getKey() {
return key;
}
// other methods
}

public class Example implements KeyHolder { // so called for "query by example"
private final String key;
public Example(String key) {
this.key = key;
}
public String getKey() {
return key;
}
}

Map<KeyHolder, Value> objects = new TreeMap<KeyHolder, Value>(new Comparator<KeyHolder, KeyHolder>(){
public int compare(KeyHolder a, KeyHolder b) {
return a.getKey().compareTo(b.getKey());
}
});
Value v = ...;
String k = v.getKey();
objects.put(v, v);
Value u = objects.get(new Example(k));
assert u == v;

?

It can certainly be done, but all things considered, i lean towards
extracting the key before hitting the map. The map could perhaps be
wrapped in a simple wrapper:

public class ValueStore {
private Map<String, Value> map = new HashMap<String, Value>();
public void put(Value v) {
map.put(v.getKey(), v);
}
public Value get(String key) {
return map.get(key);
}
}

So that calling code is not troubled with the details.

tom

--
The Vikings' commitment to metal is absolute, and it is this unshakeable
resolve to bring their metal to the people that will possibly make
Vikings of Steel the most important band ever. -- Mr Gig
 
Reply With Quote
 
 
 
 
Mike Schilling
Guest
Posts: n/a
 
      04-03-2011


"Tom Anderson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) rth.li...
> On Sat, 2 Apr 2011, Mike Schilling wrote:
>
>> "Tom Anderson" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed) rth.li...
>>> On Sat, 2 Apr 2011, Mike Schilling wrote:
>>>
>>>> "Lawrence D'Oliveiro" <(E-Mail Removed)_zealand> wrote in
>>>> message
>>>> news:in6oj8$5b5$(E-Mail Removed)...
>>>>> In message <imp8c9$nkf$(E-Mail Removed)>, Mike Schilling wrote:
>>>>>
>>>>>> "Lawrence D'Oliveiro" <(E-Mail Removed)_zealand> wrote in
>>>>>> message
>>>>>> news:imouja$56s$(E-Mail Removed)...
>>>>>>
>>>>>>> In message <(E-Mail Removed)>, Roedy Green
>>>>>>> wrote:
>>>>>>>
>>>>>>>> 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.
>>>>>>>
>>>>>>> Sounds like the Java Map classes are not well designed.
>>>>>>
>>>>>> Or that someone doesn't understand them. Embedded keys can be made
>>>>>> to work perfectly well with SortedMaps simply by making both
>>>>>> arguments to put() the same, and providing a comparator that can
>>>>>> locate the key in the object.
>>>>>
>>>>> So why isn’t there a single-argument overload of the put method to
>>>>> save you the trouble?
>>>
>>> Mind you, with an embedded key, i'm not sure how you'd do lookups even
>>> with a map. To retrieve some object, wouldn't you need to have it to
>>> hand in the first place, to be able to pass in its embedded key? Or
>>> would you also support lookup by freestanding key?

>>
>> You can look it up with an object that's equal to (as opposed to
>> identical to) the one embedded in the value. But you knew that.

>
> Yes, and i tried not to think about it, because it's smelly. How do you
> obtain these objects?


Simple use case that I've done several times:

I'm going to parse a file. For each keyword, I create an object that
describes how it should be processed; one of its fields is the string
representation of the keyword. I put it in a map using that field as the
key (map.put (kw.getName(), kw). Where do I get the String I'll use to look
it up? From reading the file.


 
Reply With Quote
 
Tom Anderson
Guest
Posts: n/a
 
      04-03-2011
On Sun, 3 Apr 2011, Mike Schilling wrote:

> "Tom Anderson" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) rth.li...
>> On Sat, 2 Apr 2011, Mike Schilling wrote:
>>
>>> "Tom Anderson" <(E-Mail Removed)> wrote in message
>>> news:(E-Mail Removed) rth.li...
>>>> On Sat, 2 Apr 2011, Mike Schilling wrote:
>>>>
>>>>> "Lawrence D'Oliveiro" <(E-Mail Removed)_zealand> wrote in
>>>>> message
>>>>> news:in6oj8$5b5$(E-Mail Removed)...
>>>>>> In message <imp8c9$nkf$(E-Mail Removed)>, Mike Schilling wrote:
>>>>>>
>>>>>>> "Lawrence D'Oliveiro" <(E-Mail Removed)_zealand> wrote in
>>>>>>> message
>>>>>>> news:imouja$56s$(E-Mail Removed)...
>>>>>>>
>>>>>>>> In message <(E-Mail Removed)>, Roedy Green
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>>> 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.
>>>>>>>>
>>>>>>>> Sounds like the Java Map classes are not well designed.
>>>>>>>
>>>>>>> Or that someone doesn't understand them. Embedded keys can be made
>>>>>>> to work perfectly well with SortedMaps simply by making both
>>>>>>> arguments to put() the same, and providing a comparator that can
>>>>>>> locate the key in the object.
>>>>>>
>>>>>> So why isn’t there a single-argument overload of the put method to
>>>>>> save you the trouble?
>>>>
>>>> Mind you, with an embedded key, i'm not sure how you'd do lookups even
>>>> with a map. To retrieve some object, wouldn't you need to have it to
>>>> hand in the first place, to be able to pass in its embedded key? Or
>>>> would you also support lookup by freestanding key?
>>>
>>> You can look it up with an object that's equal to (as opposed to
>>> identical to) the one embedded in the value. But you knew that.

>>
>> Yes, and i tried not to think about it, because it's smelly. How do you
>> obtain these objects?

>
> Simple use case that I've done several times:
>
> I'm going to parse a file. For each keyword, I create an object that
> describes how it should be processed; one of its fields is the string
> representation of the keyword. I put it in a map using that field as
> the key (map.put (kw.getName(), kw). Where do I get the String I'll use
> to look it up? From reading the file.


Okay, crossed wires. If some type T has an embedded key K (ie there's some
method m such that you can say T t; K k = t.m(), then you have two
options. One, you can do what you describe there, and what i was also
talking about in my last post (with all the curly brackets), where you
have a Map<K, T>. Two, you can do what you described in your original
reply to Lawrence, and have a Map<T, T>, with a Comparator that says
compare(T a, T b) {return a.m().compareTo(b.m());}. Option two involves
using instances of T as keys. It's those instances which i was asking how
you obtain.

But perhaps the answer is that we use option one.

tom

--
A program is only as good as its worst piece of code. -- Joshua Cranmer
 
Reply With Quote
 
Mike Schilling
Guest
Posts: n/a
 
      04-03-2011


"Tom Anderson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) rth.li...
> On Sun, 3 Apr 2011, Mike Schilling wrote:
>
>> "Tom Anderson" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed) rth.li...
>>> On Sat, 2 Apr 2011, Mike Schilling wrote:
>>>
>>>> "Tom Anderson" <(E-Mail Removed)> wrote in message
>>>> news:(E-Mail Removed) rth.li...
>>>>> On Sat, 2 Apr 2011, Mike Schilling wrote:
>>>>>
>>>>>> "Lawrence D'Oliveiro" <(E-Mail Removed)_zealand> wrote in
>>>>>> message
>>>>>> news:in6oj8$5b5$(E-Mail Removed)...
>>>>>>> In message <imp8c9$nkf$(E-Mail Removed)>, Mike Schilling wrote:
>>>>>>>
>>>>>>>> "Lawrence D'Oliveiro" <(E-Mail Removed)_zealand> wrote in
>>>>>>>> message
>>>>>>>> news:imouja$56s$(E-Mail Removed)...
>>>>>>>>
>>>>>>>>> In message <(E-Mail Removed)>, Roedy
>>>>>>>>> Green
>>>>>>>>> wrote:
>>>>>>>>>
>>>>>>>>>> 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.
>>>>>>>>>
>>>>>>>>> Sounds like the Java Map classes are not well designed.
>>>>>>>>
>>>>>>>> Or that someone doesn't understand them. Embedded keys can be made
>>>>>>>> to work perfectly well with SortedMaps simply by making both
>>>>>>>> arguments to put() the same, and providing a comparator that can
>>>>>>>> locate the key in the object.
>>>>>>>
>>>>>>> So why isn’t there a single-argument overload of the put method to
>>>>>>> save you the trouble?
>>>>>
>>>>> Mind you, with an embedded key, i'm not sure how you'd do lookups even
>>>>> with a map. To retrieve some object, wouldn't you need to have it to
>>>>> hand in the first place, to be able to pass in its embedded key? Or
>>>>> would you also support lookup by freestanding key?
>>>>
>>>> You can look it up with an object that's equal to (as opposed to
>>>> identical to) the one embedded in the value. But you knew that.
>>>
>>> Yes, and i tried not to think about it, because it's smelly. How do you
>>> obtain these objects?

>>
>> Simple use case that I've done several times:
>>
>> I'm going to parse a file. For each keyword, I create an object that
>> describes how it should be processed; one of its fields is the string
>> representation of the keyword. I put it in a map using that field as
>> the key (map.put (kw.getName(), kw). Where do I get the String I'll use
>> to look it up? From reading the file.

>
> Okay, crossed wires. If some type T has an embedded key K (ie there's some
> method m such that you can say T t; K k = t.m(), then you have two
> options. One, you can do what you describe there, and what i was also
> talking about in my last post (with all the curly brackets), where you
> have a Map<K, T>. Two, you can do what you described in your original
> reply to Lawrence, and have a Map<T, T>, with a Comparator that says
> compare(T a, T b) {return a.m().compareTo(b.m());}. Option two involves
> using instances of T as keys. It's those instances which i was asking how
> you obtain.
>
> But perhaps the answer is that we use option one.


Fair point. This was simpler before generics, when the Comparator could
accept either K's or T's

 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      04-06-2011
Mike Schilling wrote:
> Fair point. This was simpler before generics, when the Comparator could accept
> either K's [sic] or T's [sic]


Without further consideration I won't yet claim this is one of those times,
but sometimes simpler is not better.

The generics notion, with which I agree but others might not, is that the
complexity of generics buys you locked-down type assertions.

In the simpler way, you compare Ts and Ks willy-nilly, without really saying
so. Sure it works, but it's hidden.

With generics, you have to show the type relationship explicitly. This seems
consistent with Java's policy of dragging out every possible elucidation of
your algorithm, data structures and type structures at compile time without
regard for index-finger RMI. This is supposed to be good, both documenting
and enforcing the type analysis.

But the downside is that rigorous, explicit, very-carefully-thought-out and
thorough analysis is hard work. Work that professionals do anyway. Tough
programmers, tough on bugs. Hoo-rah!

--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedi.../c/cf/Friz.jpg
 
Reply With Quote
 
blmblm@myrealbox.com
Guest
Posts: n/a
 
      04-11-2011
In article <inielt$uok$(E-Mail Removed)>, Lew <(E-Mail Removed)> wrote:
> Mike Schilling wrote:
> > Fair point. This was simpler before generics, when the Comparator could accept
> > either K's [sic] or T's [sic]


"[sic]"?

My understanding is that while it's less common than it used to be
to form the plurals of multiletter acronyms[*] with apostrophes
(e.g., "CDs" rather than "CD's"), apostrophes are still advised
for forming plurals of single letters, to avoid ambiguity in the
case of A and I (and possibly some others I'm not thinking of).

Can you cite any authoritative recommendation for leaving out
the apostrophes here?
[*] Or initialisms, for the pedantic?

[ snip ]

> In the simpler way, you compare Ts and Ks willy-nilly, without really saying
> so. Sure it works, but it's hidden.


[ snip ]

--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.
 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      04-11-2011
On Apr 11, 9:53*am, (E-Mail Removed) <(E-Mail Removed)> wrote:
> In article <inielt$(E-Mail Removed)>, Lew *<(E-Mail Removed)>wrote:
> > Mike Schilling wrote:
> > > Fair point. This was simpler before generics, when the Comparator could accept
> > > either K's [sic] or T's [sic]

>
> "[sic]"? *
>
> My understanding is that while it's less common than it used to be
> to form the plurals of multiletter acronyms[*] with apostrophes
> (e.g., "CDs" rather than "CD's"), apostrophes are still advised
> for forming plurals of single letters, to avoid ambiguity in the
> case of A and I (and possibly some others I'm not thinking of).
>


But not "K" or "T".

> Can you cite any authoritative recommendation for leaving out
> the apostrophes here?
>
>[*] Or initialisms, for the pedantic?
>
> [ snip ]
>
> > In the simpler way, you compare Ts and Ks willy-nilly, without really saying
> > so. *Sure it works, but it's hidden.

>
> [ snip ]
>


<http://ethnicity.rutgers.edu/~jlynch/Writing/p.html#plural>
"Resist the urge to put an apostrophe before the s in a plural,
whether in common or proper nouns. The term for this vulgar error is
the greengrocer's apostrophe, ..."

<http://ethnicity.rutgers.edu/~jlynch/Writing/a.html#apostrophe>
"My preference: don't use apostrophes to make abbreviations plural
not They took their SAT's, but They took their SATs. The only
exception is when having no apostrophe might be confusing: Two As is
ambiguous (it might be read as the word as); make it Two A's."

Refer to his citations and C.V. for transitive authority.

--
Lew
Plppppttththtth!
 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      04-11-2011
Leif Roar Moldskred wrote:
> Lew wrote:
>> But not "K" or "T".


> That's a matter of style: some style guides recommend the use of an
> apostrophe to mark plurals of individual letters, some do not.
> See "Eat, Shoots & Leaves -- The zero tolerance approach to
> punctuation" by Lynne Truss for a funny but in-depth discussion of
> the uses of apostrophes.
>


Yes, it is a matter of style. Duh. That's why I cited a *style*
guide. There's a direct correlation there.

Yes, styles vary. The question was for *an* authority to support the
style I follow. As you say, some support what I suggest and some do
not. I follow the ones that do.

I don't follow every style, nor can one, given that they don't always
agree.

Personally I find the "greengrocer's comma" to distract and diminish
from the communication, so the style guide I follow concords with that
assessment.

YMMV.

--
Lew
 
Reply With Quote
 
Tom Anderson
Guest
Posts: n/a
 
      04-11-2011
On Mon, 11 Apr 2011, Lew wrote:

> Leif Roar Moldskred wrote:
>> Lew wrote:
>>> But not "K" or "T".

>>
>> That's a matter of style: some style guides recommend the use of an
>> apostrophe to mark plurals of individual letters, some do not. See
>> "Eat, Shoots & Leaves -- The zero tolerance approach to punctuation" by
>> Lynne Truss for a funny but in-depth discussion of the uses of
>> apostrophes.

>
> Yes, it is a matter of style. Duh. That's why I cited a *style*
> guide. There's a direct correlation there.
>
> Yes, styles vary.


In which case the use of 'sic' is dubious. You are not marking something
that is wrong, you are marking something that you wouldn't write that way
yourself. If you start doing that consistently, i think you will soon find
that your square bracket keys have worn out.

To be honest, the use of sic in quoted text in a mail or news post at all
is dubious. sic is used to indicate that there has been no error in
transcription; when it is a machine doing the transcription, it is
redundant.

tom

--
Taking care of business
 
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