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