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

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

Re: Binary Search

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

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.

tom

-- 
A program is only as good as its worst piece of code. -- Joshua Cranmer

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