MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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





  • Prev by Date: RE: Multiple surface plots
  • Next by Date: Re: NDSolve and derivative error
  • Previous by thread: Re: Errors in Copying and Pasting Heads of Expressions
  • Next by thread: Re: Re: Interpoint distances---timing comparisons