Improve speed with a double for loop

Question

I am trying to calculate the Euclidean distance of pairs of points $(x_i,y_i)$ with $x$ and $y$ given as separate lists.

sqdiff = {};
For[i = 1, i < Length[x] - 1, i++,
 {
  For[j = i + 1, j < Length[x], j++,
   {
    AppendTo[sqdiff, (x[[i]] - x[[j]])^2 + (y[[i]] - y[[j]])^2];
    }
   ]
  }
 ]

Even for 800 points, this loops takes orders of magnitudes longer than an identical loop written in MATLAB. Are there any improvements I can make? Thanks.

Answer 1

Even in MATLAB, this would not be good programming style because successive concatenation is awfully slow. (And for is slow, too.) Better use Table:

n = 800;
x = RandomReal[{-1, 1}, n];
y = RandomReal[{-1, 1}, n];

Table[
 With[{xi = x[[i]], yi = y[[i]]},
  Table[
   (xi - x[[j]])^2 + (yi - y[[j]])^2
   , {j, 1, n}]
  ],
 {i, 1, n}
 ]

Better:

Table[
  Sqrt[(x[[i]] - x)^2 + (y[[i]] - y)^2],
  {i, 1, n}
  ];

Even better: Use DistanceMatrix:

DistanceMatrix[Transpose[{x, y}]];

Answer 2

(Subtract @@@ Subsets[Most@x, {2}])^2 + (Subtract @@@Subsets[Most@y, {2}])^2

will produce precisely the output of your OP with appropriate performance. Since your output is a small subset of all-points distances, it should also outperform things like DistanceMatrix.

A comparison of OP and this up to 300 length for timing: