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$
2
  • 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
    Commented Mar 3, 2020 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$ Commented Mar 3, 2020 at 21:05

2 Answers 2

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}]];
$\endgroup$
4
  • 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
    Commented Mar 3, 2020 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$ Commented Mar 3, 2020 at 21:08
  • $\begingroup$ 1000 random points -> ~ 500,000 distinct pairs iterated. Took a few seconds. $\endgroup$
    – Gregory
    Commented Mar 3, 2020 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$ Commented Mar 3, 2020 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

$\endgroup$
1
  • $\begingroup$ Can you please explain some of the syntax in greater detail if you have time. $\endgroup$
    – Gregory
    Commented Mar 3, 2020 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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