Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #2782

Re: Binary Search

Show key headers only | View raw

"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.
 

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Binary Search Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-04-02 22:00 +1300
  Re: Binary Search Leif Roar Moldskred <leifm@dimnakorr.com> - 2011-04-02 05:07 -0500
    Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 07:59 -0700
      Re: Binary Search Leif Roar Moldskred <leifm@dimnakorr.com> - 2011-04-02 10:37 -0500
        Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 08:57 -0700
          Re: Binary Search Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-04-03 12:40 +1200
  Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 07:58 -0700
    Re: Binary Search Lew <noone@lewscanon.com> - 2011-04-02 11:11 -0400
      Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 08:58 -0700
    Re: Binary Search Tom Anderson <twic@urchin.earth.li> - 2011-04-03 00:11 +0100
      Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 16:52 -0700
        Re: Binary Search Tom Anderson <twic@urchin.earth.li> - 2011-04-03 18:50 +0100
          Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-03 12:01 -0700
            Re: Binary Search Tom Anderson <twic@urchin.earth.li> - 2011-04-03 22:39 +0100
              Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-03 16:37 -0700
                Re: Binary Search Lew <noone@lewscanon.com> - 2011-04-06 15:24 -0400
                OT "sic"? (was Re: Binary Search) blmblm@myrealbox.com <blmblm@myrealbox.com> - 2011-04-11 13:53 +0000
                Re: OT "sic"? (was Re: Binary Search) Lew <lew@lewscanon.com> - 2011-04-11 11:45 -0700
                Re: OT "sic"? (was Re: Binary Search) Leif Roar Moldskred <leifm@dimnakorr.com> - 2011-04-11 14:11 -0500
                Re: OT "sic"? (was Re: Binary Search) Lew <lew@lewscanon.com> - 2011-04-11 13:48 -0700
                Re: OT "sic"? (was Re: Binary Search) Tom Anderson <twic@urchin.earth.li> - 2011-04-11 22:16 +0100
                Re: OT "sic"? (was Re: Binary Search) Lew <noone@lewscanon.com> - 2011-04-11 17:54 -0400
                Re: OT "sic"? (was Re: Binary Search) Tom Anderson <twic@urchin.earth.li> - 2011-04-11 23:35 +0100
                Re: OT "sic"? (was Re: Binary Search) Leif Roar Moldskred <leifm@dimnakorr.com> - 2011-04-11 21:41 -0500
                Re: OT "sic"? (was Re: Binary Search) blmblm@myrealbox.com <blmblm@myrealbox.com> - 2011-04-14 10:11 +0000
                Re: OT "sic"? (was Re: Binary Search) Jerry Gerrone <scuzwalla@gmail.com> - 2011-04-14 20:12 -0700
      Re: Binary Search Ken Wesson <kwesson@gmail.com> - 2011-04-05 16:01 +0100

csiph-web