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

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

Re: Binary Search

Show key headers only | View raw

"Tom Anderson" <twic@urchin.earth.li> wrote in message 
news:alpine.DEB.2.00.1104032234030.11872@urchin.earth.li...
> On Sun, 3 Apr 2011, Mike Schilling wrote:
>
>> "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.
>
> 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 :-) 

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