3
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ "Are there any improvements I can make? ". Yes. Don't program Mathematica as if it were Matlab. Use DistanceMatrix, vectorize it, etc. $\endgroup$ – ciao Mar 3 at 21:00
  • 1
    $\begingroup$ Even in MATLAB this were bad programming style. Typically, one is taught to use vectorization there as well. Due to the use of For/for and the to the successive AppendTo (cat in MATLAB). $\endgroup$ – Henrik Schumacher Mar 3 at 21:05
10
$\begingroup$

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}]];
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 100% it is bad style, but it still was done in under 5 seconds in matlab with 500k points, so I was shocked. Thanks for the help! $\endgroup$ – Gregory Mar 3 at 21:07
  • $\begingroup$ With 500k? Impossible. That would make a $500k \times 500k$ matrix or an $(500k)^2$ vector. I doubt that your MATLAB code is equivalent to this on. $\endgroup$ – Henrik Schumacher Mar 3 at 21:08
  • $\begingroup$ 1000 random points -> ~ 500,000 distinct pairs iterated. Took a few seconds. $\endgroup$ – Gregory Mar 3 at 21:10
  • 1
    $\begingroup$ Ah, I see. That makes sense. The major point here is AppendTo, because it involves a copy operation of the full array. So your loop is actually of complexity $O(n^3)$. $\endgroup$ – Henrik Schumacher Mar 3 at 21:10
8
$\begingroup$
(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:

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please explain some of the syntax in greater detail if you have time. $\endgroup$ – Gregory Mar 3 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.