2
$\begingroup$

I need to compute a fast DistanceMatrix (euclidean distance) of a large vector. Let say

x = Table[Sin[t],{t,1,10000}]

But pre defined function

Distancematrix[x]

takes on my machine way too long, I was trying to make some faster code but unsuccesfully f.e.

DISMAT[dat_] := (
          Clear[N1, DD];
          N1 = Length[dat];
          DD = ConstantArray[0, {N1, N1}];
          For[k1 = 1, k1 < N1 + 1, k1++,
           For[k2 = K = k1 + 1, k2 < N1 + 1, k2++,
            DD[[k1, k2]] = ( dat[[k1]] - dat[[k2]])^2
            ]
           ];
          DD = (DD + Transpose[DD])
          ) 

Which is actually rewrited code from Matlab which runs much much faster than in mathematica and can compute DistanceMatrix of x in cca 3 sec. this code in Mathematica takes like 10 min.

Or

distmatrix2 = 
Compile[{{point, _Real, 1}, {tr, _Real, 2}}, Total@Abs[point - tr], 
CompilationTarget -> "C", RuntimeOptions -> "Speed", 
RuntimeAttributes -> {Listable}, Parallelization -> True]

which also takes like 10 min. Thanks for any suggestions.

$\endgroup$
  • 4
    $\begingroup$ Try x = Table[Sin[t],{t,1.,10000}], with the approximate real 1. in place of the exact integer 1. $\endgroup$ – Michael E2 Mar 23 '18 at 0:48
  • $\begingroup$ Firstly, as @MichaelE2 has mentioned, you need to know that, Wolfram tries to keep things exact, which means it tries to return exact result if you feed it with exact number. This is very the opposite of languages such as MATLAB. To generate the vector, here I offer you an alternative x = Array[Sin, 10000, 1.];. $\endgroup$ – Αλέξανδρος Ζεγγ Mar 23 '18 at 6:49
  • 1
    $\begingroup$ Secondly, with the x generated above, on my machine, disMat = DistanceMatrix[x]; only takes half a second. If you must write your own one, avoid explicit loops, not to mention nested ones. A function which might help is Outer. $\endgroup$ – Αλέξανδρος Ζεγγ Mar 23 '18 at 6:53
  • $\begingroup$ Note that the complexity of computing the full distance matrix is quadratic in the number of elements of x. Often, one only needs distances for few pairs of points, e.g., those which have distance below a given threshold. In this cases Nearest (which employs a BSP tree) reduces the complexity significantly; see, e.g., here and here. $\endgroup$ – Henrik Schumacher Mar 23 '18 at 9:40
  • $\begingroup$ Possible duplicate: mathematica.stackexchange.com/questions/21861/… $\endgroup$ – Michael E2 Mar 23 '18 at 11:11

Your Answer

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

Browse other questions tagged or ask your own question.