Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #2818
| From | "Mike Schilling" <mscottschilling@hotmail.com> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Binary Search |
| Date | 2011-04-03 16:37 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <inb0bd$gsn$1@dont-email.me> (permalink) |
| References | (9 earlier) <alpine.DEB.2.00.1104030007560.28036@urchin.earth.li> <in8crk$og2$1@dont-email.me> <alpine.DEB.2.00.1104031840110.11872@urchin.earth.li> <inahvd$qt$1@dont-email.me> <alpine.DEB.2.00.1104032234030.11872@urchin.earth.li> |
"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
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