Fast Distance Calculations
QUESTION: What is the fastest way to calculate a distance from a particular point to an array of multiple other points in IDL?
ANSWER: There was an interesting discussion of this topic in a recent IDL newsgroup article. The answer, of course, is that “it depends.” In fact, it depends on the machine you are running the calculation on, whether you do the calculation in floating or double precision values, what algorithm you use to do the calculation, and how many distance calculations you are doing. But, the surprising finding from the article is that it is sometimes faster to do the calculation with complex numbers.
Other surprising findings from the discussion are these.
- It is faster to use ABS to find the real part of a complex number than it is to use REAL_PART.
- You can save time in the calculations by "fluffing" the 1D index arrays into 2D arrays before performing the distance calculations.
- Matrix operations (with the # operator) are faster than the REBIN command when "fluffing" the 1D arrays.
- Replacing exponential code (e.g., x^2) with multiplication code (e.g., x*x) makes the code faster.
I have provided example code as a main-level IDL programs that explores the various methods discussed in the article using the techniques described above. A square array of various sizes (N) is used. You can see the speed dependency on the size of the array. Your mileage will vary from mine, no doubt, but here is the result of running the program on my Windows 64-bit machine.
---- N = 100 FLOAT Real distance calculation: 0.00015000 FLOAT Complex distance calculation: 0.00020000 DOUBLE Real distance calculation: 0.00008000 DOUBLE Complex distance calculation: 0.00019000 "Fluffing" distance calculation: 0.00007000 ---- N = 200 FLOAT Real distance calculation: 0.00049000 FLOAT Complex distance calculation: 0.00090000 DOUBLE Real distance calculation: 0.00055000 DOUBLE Complex distance calculation: 0.00086000 "Fluffing" distance calculation: 0.00025000 ---- N = 300 FLOAT Real distance calculation: 0.00082000 FLOAT Complex distance calculation: 0.00187000 DOUBLE Real distance calculation: 0.00127000 DOUBLE Complex distance calculation: 0.00236000 "Fluffing" distance calculation: 0.00054000 ---- N = 400 FLOAT Real distance calculation: 0.00079000 FLOAT Complex distance calculation: 0.00147000 DOUBLE Real distance calculation: 0.00192000 DOUBLE Complex distance calculation: 0.00257000 "Fluffing" distance calculation: 0.00084000 ---- N = 500 FLOAT Real distance calculation: 0.00128000 FLOAT Complex distance calculation: 0.00229000 DOUBLE Real distance calculation: 0.00316000 DOUBLE Complex distance calculation: 0.00425000 "Fluffing" distance calculation: 0.00136000
Version of IDL used to prepare this article: IDL 8.2.2.