Re: Interpoint distances---timing comparisons
- To: mathgroup at smc.vnet.net
- Subject: [mg41422] Re: Interpoint distances---timing comparisons
- From: "DIAMOND Mark R." <dot at dot.dot>
- Date: Mon, 19 May 2003 05:09:45 -0400 (EDT)
- Organization: The University of Western Australia
- References: <b9tdnj$7r0$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Well, here are the results I promised; comparisons between the various
improvements suggested to my original routine for calculating all interpoint
distances in a list of points in R^2.
The comparisons are on a 6x86 machine (Win 98) running at 133 MHz with 64Mb
RAM. As you will see, I only used 128 points because of the relative
slowness of the machine. The Kernel was restarted prior to timing each of
the different methods, thereby overcoming inconsistencies in the amount of
memory initially available to any routine.
We have the following initialization cell in the notebook
len = 256;
t = Table[{Random[], Random[]}, {len}];
I sha'n't repeat the routines from all the suggestions, but,
(1) my original with double counting and its cheat using Union runs in 50.15
Second
(2) Daniel Lichtblau's first routine runs in 15.16 Second
(3) Andrzej's initial improvement with compilation runs in 5.71 Second
(4) Daniel's second routine (needing more space) runs in 2.92 seconds;
(5) Andrzej's second improvement with the Complex number trick and
compilation runs in 1.92 Second
But ... Carl Woll wins hands down with
d3sqrt[t_] :=
Block[{c = {}},
Nest[(c = {c, Sqrt[Plus @@ ((Transpose[Rest[#]] - First[#])^2)]};
Rest[#]) &, t, Length[t] - 1];
Flatten[c]]
Timing[d3sqrt[t];]
{0.88 Second, Null}
I did not compare Bobby Treat's method because KSubsets (from
DiscreteMath`Combinatorica) is recursive and so presents problems for larger
data sets.
No doubt compiling Carl's routine will do even better, but I haven't tried
it yet.
Cheers,
Mark