Services & ResourcesWolfram ForumsMathGroup Archive

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

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. } }

• References:
  • Re: fastest way to do pair-sum / make pair-list
    • From: "Mark Harder" <harderm@ucs.orst.edu>