Re: Re: Interpoint distances---timing comparisons
- To: mathgroup at smc.vnet.net
- Subject: [mg41451] Re: [mg41422] Re: Interpoint distances---timing comparisons
- From: Bobby Treat <drmajorbob+MathGroup3528 at mailblocks.com>
- Date: Tue, 20 May 2003 03:28:10 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
On my computer at least, some of these solutions are faster than Carl's:
<< Experimental`
treat1[t_] := Flatten@Reap[Nest[(Sow@Sqrt@(
Plus @@ ((
Transpose[Rest[#]] - First[#])^2)); Rest@#) &, t, Length[t] - 1];]
treat2[t_] := Sqrt@Flatten@Reap[Nest[(Sow@(Plus @@ ((Transpose[Rest[#]]
-
First[#])^2)); Rest@#) &, t, Length[t] - 1];]
It seems to me that we wouldn't want to Flatten, in which case it is
treat3[t_] := Sqrt@Flatten[Reap[Nest[
(Sow@(Plus @@ ((Transpose[Rest[#]] - First[#])^2)); Rest@#) &,
t,
Length[t] - 1];], 1]
treat4[t_] := Sqrt@Flatten[Reap@Fold[(
Sow@(Plus @@ ((
Transpose[#1] - #2)^2)); Rest@#1) &, Rest@t, Drop[t, -1]], 1]
len = 1024;
t = Table[{Random[], Random[]}, {len}];
Timing[d3sqrt[t];]
Timing[treat1@t;]
Timing[treat2@t;]
Timing[treat3@t;]
Timing[treat4@t;]
{0.406 Second,Null}
{0.36 Second,Null}
{0.469 Second,Null}
{0.312 Second,Null}
{0.313 Second,Null}
(another trial:)
{0.359 Second,Null}
{0.375 Second,Null}
{0.454 Second,Null}
{0.296 Second,Null}
{0.313 Second,Null}
treat2@t == d3sqrt@t == treat1@t == Flatten@treat4@t
treat3@t == treat4@t
True
True
Bobby
-----Original Message-----
From: DIAMOND Mark R. <dot at dot.dot>
To: mathgroup at smc.vnet.net
Subject: [mg41451] [mg41422] Re: Interpoint distances---timing comparisons
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