8
$\begingroup$

Here I define (NormCoordinates).

NormCoordinates[coordinates_]:=Norm/@coordinates;
NormCoordinates[{{2.2,4.4},{5.5,6.6},{-6.7,1.3},{-2.7,-0.3}}]

(* {4.91935, 8.59127, 6.82495, 2.71662} *)

As in the example above, I plan to only use it on elements with the Head Real. I notice (Norm) can't be compiled. Can anyone implement this using Compile and lower level functions in a way the runs much faster on a large list?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ No time right now to survey different methods, but I have a feeling compilation won't gain you that much in this case. If it's just the 2-norm you want, you can get an improvement of 50% or so from listableNorm = Function[coords, Sqrt@Total[Internal`Square[coords], {2}]];. $\endgroup$
    – Oleksandr R.
    Aug 18, 2012 at 23:06
  • 4
    $\begingroup$ Norm[] is in this list, though. $\endgroup$
    – J. M.'s persistent exhaustion ♦
    Aug 19, 2012 at 1:42
  • $\begingroup$ Silly me, I checked the list of compileable functions and didn't see it. I also didn't know about Internal`Square. $\endgroup$
    – Ted Ersek
    Aug 19, 2012 at 11:13
  • 2
    $\begingroup$ If you write it as listableNorm2 = Function[coords, Sqrt@Total[coords coords, {2}]] it's not significantly slower than using Internal`Square (tested using LocationEquivalenceTest with 100 timings of 10^6 vectors), but you don't have to use an undocumented function, which generally is scary. $\endgroup$
    – Sjoerd C. de Vries
    Aug 19, 2012 at 11:56

1 Answer 1

Reset to default
4
$\begingroup$

I'm not sure what you mean by large lists since any solution is reasonable fast on a list which I think is pretty large. Please find the 2 solutions mentioned by Olek and Sjoerd and a compiled one below

normTed[coordinates_] := Norm /@ coordinates;
normSjoerd = Function[coords, Sqrt@Total[coords coords, {2}]];
normOlek = Function[coords, Sqrt@Total[Internal`Square[coords], {2}]];
normPatrick = Compile[{{v, _Real, 1}}, Sqrt[v.v], CompilationTarget -> "C", 
  RuntimeAttributes -> {Listable}, Parallelization -> True];

data = RandomReal[{0, 1}, {10^8, 2}];
First[AbsoluteTiming[#[data]]] & /@ {normTed, normSjoerd, normOlek, normPatrick}

(*
   {9.800536, 5.647508, 5.384156, 4.350411}    
*)

As you can see from top to bottom: Readability drops, performance rises. Whether the 5 seconds are really worth the effort is questionable. Maybe you can update your question with information about your real data.

Btw, on my machine the compiled version of Sqrt[v.v] is a glimpse faster (.102s) than the compiled version with Norm[v]. Therefore, I did not use Norm but it is of course compilable as J.M. pointed out.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I guess the bottom line is that fundamental functions like Total, Sqrt are already heavily optimized that compiling does little good. WReach had a nice post on Stack Overflow arguing against pointless microbenchmarking and micro optimizations... I can't seem to find it now though, but the essence of it is similar to what you said. $\endgroup$
    – rm -rf ♦
    Aug 20, 2012 at 15:26
  • 3
    $\begingroup$ Sometimes, you can gain more temporal efficiency by using v.v (and not computing the Sqrt) and then comparing to the ^2 of what ever you are comparing too. $\endgroup$
    – user21
    Aug 20, 2012 at 15:41
  • $\begingroup$ @ruebenko Yes, good point. I didn't mention it here, since the question was to calc the Euclidean norm but if one wants to compare lengths, distances, whatever it is alway good to think about whether the sqrt is really necessary. $\endgroup$
    – halirutan ♦
    Aug 20, 2012 at 15:53
  • $\begingroup$ The other thing I had thought of was to try ispc with LibraryLink (Mike Croucher gives an example for MATLAB here). I have no time to do that answer for a month or so--do you fancy giving it a try? $\endgroup$
    – Oleksandr R.
    Aug 21, 2012 at 23:57

Your Answer

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

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