MathGroup Archive 2000

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

Search the Archive

Re: fastest way to do pair-sum / make pair-list

  • To: mathgroup at smc.vnet.net
  • Subject: [mg23241] Re: fastest way to do pair-sum / make pair-list
  • From: "Allan Hayes" <hay at haystack.demon.co.uk>
  • Date: Sat, 29 Apr 2000 22:04:49 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

Wagner, Wijnand,
After reading Wagner's posting I went back to the solution that I had posted
earlier. I had avoided the double counting in Wagner's solution but the
code did not seem to compile and is slower. The code ssd3, below, is an
inessential compression of the earlier code. Then, for ssd4, I used Join
instead of Flatten and found a considerable speed up - often faster than
Wagner's code, which surprised me.

I give some comparisons below. Windows 98 on my Tecra750 is giving erratic
timings. I would be interested to see timings on other systems and also some
explanations and suggestions for improvements.

ssd3[data_] := (#.#) &[{1, -1}.(Flatten[
              NestList[#, #[data], Length[data] - 2], 1] & /@ {Drop[#, -1]
&,
            Drop[#, 1] &})]


ssd4[data_] := (#.#) &[{1, -1}.(Apply[Join,
              NestList[#, #[data], Length[data] - 2]] & /@ {Drop[#, -1] &,
            Drop[#, 1] &})]


(Wagner Truppel)
SumOfPairwiseSquaredDifferences =
    Compile[{{m, _Real, 1}},
      Module[{t = m}, Apply[Plus, Flatten[Table[t = RotateLeft[t];
                (m - t)^2, {Length[m] - 1}]]]/2.0]];

Timings, order: SumOfPairwiseSquaredDifferences ,ssd3, ssd4.

n = 50;
m = Table[Random[], {n}];
{n, Timing[SumOfPairwiseSquaredDifferences[m]],
  Timing[ssd3[m]],
  Timing[ssd4[m]]}

{50, {0. Second, 206.798}, {0.05 Second, 206.798}, {0. Second, 206.798}}

n = 100;
m = Table[Random[], {n}];
{n, Timing[SumOfPairwiseSquaredDifferences[m]],
  Timing[ssd3[m]],
  Timing[ssd4[m]]}

{100, {0.05 Second, 789.895}, {0.11 Second, 789.895}, {0.06 Second,
789.895}}

n = 200;
m = Table[Random[], {n}];
{n, Timing[SumOfPairwiseSquaredDifferences[m]],
  Timing[ssd3[m]],
  Timing[ssd4[m]]}

{200, {0.44 Second, 3132.64}, {0.44 Second, 3132.64}, {0.27 Second,
3132.64}}

n = 500;
m = Table[Random[], {n}];
{n, Timing[SumOfPairwiseSquaredDifferences[m]],
  Timing[ssd3[m]],
  Timing[ssd4[m]]}

{500, {5.55 Second, 19985.2}, {3.85 Second, 19985.2}, {1.97 Second,
19985.2}}

n = 1000;
m = Table[Random[], {n}];
{n, Timing[SumOfPairwiseSquaredDifferences[m]],
  Timing[ssd3[m]],
  Timing[ssd4[m]]}

{1000, {14.94 Second, 83545.7}, {18.61 Second, 83545.7}, {12.75 Second,
    83545.7}}


--
Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565





  • Prev by Date: Re: Re: Plotting bounded domains
  • Next by Date: more on vector unions
  • Previous by thread: Re: fastest way to do pair-sum / make pair-list
  • Next by thread: minimization of a function operating on a vector or reals