MathGroup Archive 2000

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

Search the Archive

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

  • To: mathgroup at smc.vnet.net
  • Subject: [mg23223] fastest way to do pair-sum / make pair-list
  • From: Wagner Truppel <wtruppel at uci.edu>
  • Date: Tue, 25 Apr 2000 01:40:28 -0400 (EDT)
  • References: <200004240512.BAA15307@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Below's my solution, with some running times obtained on a 300 MHz Mac.

The rationale behind it is very simple. Take the example of a list of 
4 elements, m = {a1, a2, a3, a4}. The difference m - RotateLeft[m] is 
equal to
{a1 - a2, a2 - a3, a3 - a4, a4 - a1}. By computing all but one of 
these "rotated differences" we obtain all pairwise differences, each 
appearing twice (with opposite signs). The excluded difference is 
that which results in {0, 0, 0, 0}.

Squaring affects each element individually, flattening removes the 
internal list structure, Apply[] sums all the elements, but we need 
to divide by 2.0 because each difference squared appears twice in the 
sum. Compiling is the final touch to gain on speed.

Wagner Truppel
wtruppel at uci.edu

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

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

{ 50, {0. Second, 183.897 } }


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

{ 100, {0.0333333 Second, 901.846 } }


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

{ 200, {0.15 Second, 3459.08 } }


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

{ 500, {0.85 Second, 20902. } }


  • Prev by Date: Re: how to rank a list of elements?
  • Next by Date: Re: fastest way to do pair-sum / make pair-list
  • Previous by thread: Re: fastest way to do pair-sum / make pair-list
  • Next by thread: Re: fastest way to do pair-sum / make pair-list