Re: distance function
- To: mathgroup at smc.vnet.net
- Subject: [mg70037] Re: distance function
- From: Peter Pein <petsie at dordos.net>
- Date: Sun, 1 Oct 2006 04:08:22 -0400 (EDT)
- References: <efldsn$daa$1@smc.vnet.net>
Coleman, Mark schrieb: > > Out of curiosity, I tested these two approaches on a number of data sets > for which I make frequent use. For some reason Jens code is running > slower! I've been testing it out some lists of reals of size > n=500,1000,2500, and 5000. Is it possible that the time for the > conditional compares is exceeding the computational time of redundant > calculations? Could someone try this out? > > (note: I'm working on some code for identifying outliers in large data > sets. The efficient calculation of L-1 and L-2 distance matrices are > important.) > > Thanks > > Mark > > > -----Original Message----- > From: Murray Eisenberg [mailto:murray at math.umass.edu] To: mathgroup at smc.vnet.net > Subject: [mg70037] Re: distance function > > Yes, I KNOW that I'm computing the distances twice in my solution: > that's why I said it's an "extravagant" solution! > > Jens-Peer Kuska wrote: >> Hi Murray, >> >> at least you should compute the distances not twice because the matrix > >> is symmetric with zero diagonal ... >> >> d[{p_,p_}]:=0.0 >> d[{q_,p_}]/; OrderedQ[{q,p}]:=d[{q,p}]= Norm[p - q] >> d[{q_,p_}]:=d[{p,q}] >> >> Regards >> Jens >> >> >> Murray Eisenberg wrote: >>> If you don't mind an "extravagant" solution -- one that is >>> conceptually simple and short but is probably inefficient due to >>> redundant calculations -- then this works, I believe: >>> >>> d[{p_, q_}] := Norm[p - q] >>> allDistances[pts_] := Union[Flatten[Outer[d, pts, pts]]] >>> >>> >>> >>> dimmechan at yahoo.com wrote: >>>> In the book of Gaylord et al. (1996) there is one exercise which >>>> asks (see page 113) >>>> >>>> "Given a list of points in the plane, write a function that finds >>>> the set of all distances between the points." >>>> >>>> Although there is one solution, that solution makes use of the Table > >>>> and Length commands. >>>> >>>> Is it a way to define the same function using Higher-Order functions > >>>> like Outer, MapThread etc? >>>> >>>> Thanks in advance for any help. >>>> >>>> >> > Hi Mark, I think the most efficient proposal came from Bob Hanlon. I tested some alternatives and the fastest is d @@@S ubsets[pts, {2}] (2.98s for 1000 points) followed by d @@@ Flatten[MapIndexed[Drop[#1, #2[[1]]-1] &, Outer[List, Most@pts, Rest@pts, 1]], 1] with 3.31 s. Peter