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

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

Re: Binary Search

Show all headers | View raw

On Sun, 03 Apr 2011 00:11:01 +0100, Tom Anderson wrote:

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

Clojure is a JVM language that fixes this. Its sets can be called as 
functions, and return the matching item in the set:

user=> (def q (Integer. 253))
#'user/q
user=> (def r (Integer. 253))
#'user/r
user=> (def s #{q 17 42})
#'user/s
user=> (def t (s r))
#'user/t
user=> (identical? t r)
false
user=> (identical? t q)
true

The identical? function is Java's == operator "in disguise". The set's 
return value was the object q put into it rather than the .equals but not 
== object r used to retrieve q.

The Clojure set classes can of course be invoked from Java.

user=> (identical? q (.get s r))
true

That's actually a Java method invocation. In Java,

someSet.get(keyholder)

would return the corresponding object in the set, given that someSet was 
a clojure.lang.IPersistentSet, say a clojure.lang.HashSet, rather than 
one of the stock java.util set classes (which don't have this get method).

So, you can use these set classes even if you for some odd reason can't 
stomach Lisp syntax, while somehow nonetheless tolerating Java's baroque 
verbosity. :)

Back to comp.lang.java.programmer | Previous | Next — Previous 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