It's worrying that this article completely glosses over the fact that the Manhattan distance approximation is seriously wrong. It may have given the right answer in this case, but it definitely won't do so in all cases, and if you don't already have the right answer to compare to then how will you know if it's working or not?<p>Literally any problem can be solved quickly in any language if you're willing to accept an incorrect answer.
Seems the lesson is that Python is slow. Author's realization about how to use it correctly was to just call C instead.<p>Article not worth reading. Would have been much better as a quick tip. "Quick tip: if you need to loop through an array in Python, do it this way instead..."
The lesson here is that for any fairly-common Python task, there is likely to be a library that already does it 300% faster than your implementation will likely ever be. It's got nothing to do with using this or that style of programming.
His variable names really bother me. I can live with "lat", "lon" if I must, but "d", "md", "trkpts"? Readability would be greatly enhanced if he just spelled those out.<p>Programmers shouldn't be wasting brain power deciphering cryptic variable names. Save that energy for where it counts (solving actual problems!)
The same mental shift could be attributed to R as well. For instance use the *ply function (apply, lapply, sapply, tapply) if you want to loop over vectors of data instead of using "for" loops.
There are many programmers out there using Python as if it was C, and that leads to slower than necessary code. It takes some time getting used to and learning the performant way to write loops. For example, if 'trkpts' was a list of (lat, lon) tuples/lists, he could've avoided the lookups (but it would also mean having a different structure).<p>Another example, if memory isn't a concern he could write a list comprehension with all the distance values, and then get the index of the smallest. This, however, has the problem that, though the list comprhension surely runs faster than the for loop, it takes more memory and then looking for the lowest value can take all the time you saved (and maybe some more).<p>Without prfiling in his use case, it's difficult to say what is "the best solution", but his problem comes mostly from coding Python as if it were C.<p>Edit: yes, I ignored the fact tha he used numpy (a good solution, giving his 300x speedup with changing the structures), because sometimes your data isn't prone to "numpy array conversion" -- for example, if you aren't programming numerical code.
If you're iterating over all your points calculating distances, you are going about this the wrong way.<p>(edit) The author could use my handy python quad tree if he so wishes -- <a href="https://github.com/Dav3xor/pyquadtree" rel="nofollow">https://github.com/Dav3xor/pyquadtree</a>, and if he asks nicely, I could even add support for simple approximation of spherical coordinates.
Interesting to see this - we ran into a similar problem of finding points within a certain distance from amongst thousands or millions of points. We ended up using Cython[0].<p>Would this numpy trick work if he still needed an accurate distance calculation? Kind of underwhelming to throw away the accuracy to get speed without adding it back later.<p>[0] <a href="http://doublemap.github.io/blog/2015/05/29/optimizing-python/" rel="nofollow">http://doublemap.github.io/blog/2015/05/29/optimizing-python...</a>
The post is about using numpy or pypy to get better speed in python since in python for is slow. That is well known, is like the well known fact that you should use vectorized operations in R to get better performance. Anyway there is something interesting: The problem of given a point P0 as input, find the the nearest point to P0 among a fixed billion points (all of them on a sphere) can be solved easily and quickly. You should be surprised the code a mathematician could devise to solve this.
Some time ago I wrote a really simple code snippet to see the performance differences between Python, PHP, C and Java (the languages I tinker in) on my particular machine (i3 M 330, 2.13 GHz / 4 GB RAM / Ubuntu 15.04 x64).<p>The results were as follows:<p>~ 14.2 seconds for Python 3.4.3 [1]<p>~ 9.0 seconds for Python 2.7.9 [1]<p>~ 9.0 seconds for PHP 5.6 [2]<p>~ 2.3 seconds for C [3]<p>~ 2.3 seconds for Java 8 [4]<p>Again, this was on my machine with out of the box settings. I have linked the test code that I wrote and perhaps there is something wrong with my Python and PHP code but to me the results were quite revealing. Also it's interesting to see that on my configuration C and Java both hit the limit of my CPU (I can't explain the score otherwise) and I can't know for sure if on a more powerful CPU Java would still be on pair with C.<p>[1] <a href="https://gist.github.com/anonymous/7edafa3889be967a1e1d" rel="nofollow">https://gist.github.com/anonymous/7edafa3889be967a1e1d</a><p>[2] <a href="https://gist.github.com/anonymous/56ff76849f5a312340d9" rel="nofollow">https://gist.github.com/anonymous/56ff76849f5a312340d9</a><p>[3] <a href="https://gist.github.com/anonymous/5717ba935b43bad09e1d" rel="nofollow">https://gist.github.com/anonymous/5717ba935b43bad09e1d</a><p>[4] <a href="https://gist.github.com/anonymous/6b0c2f11609b951b64f3" rel="nofollow">https://gist.github.com/anonymous/6b0c2f11609b951b64f3</a>
It's not Python, you face the same problems with Matlab, unless you vectorize your code to remove loops it's quite unusable for anything but small arrays
To make it even faster, there is a (non-free) numpy version compiled with the Intel MKL math library [1].
We use this library in high-performance-computing, it's as fast as you can get on intel hardware.<p>[1] <a href="https://store.continuum.io/cshop/mkl-optimizations/" rel="nofollow">https://store.continuum.io/cshop/mkl-optimizations/</a>
I'd personally have jumped straight to PyPy.<p>And let me get this straight. He can use C, but cannot use PyPy? How does that make sense? If he's able to use C, he's able to run binaries anyways, at which point he should be able to use PyPy. Unless I'm missing something?
He missed a critical option: you can write those loops in python and JIT them to C fast LLVM with numba: <a href="https://github.com/numba/numba" rel="nofollow">https://github.com/numba/numba</a>
> <i>The reason for that speedup is that numpy array operations are written in C.</i><p>> [ ... ]<p>> <i>The lesson is clear: do not write Python code as you would do in C.</i><p>:)