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

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

Re: Binary Search

Show key headers only | View raw

"Tom Anderson" <twic@urchin.earth.li> wrote in message 
news:alpine.DEB.2.00.1104031840110.11872@urchin.earth.li...
> On Sat, 2 Apr 2011, Mike Schilling wrote:
>
>> "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?
>>>
>>> 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.
 

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: OT "sic"? (was Re: Binary Search) Ken Wesson <kwesson@gmail.com> - 2011-04-26 22:53 +0100
      Re: Binary Search Ken Wesson <kwesson@gmail.com> - 2011-04-05 16:01 +0100

csiph-web