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?
Literally any problem can be solved quickly in any language if you're willing to accept an incorrect answer.
It would have been nice to come back and see how fast calculating the correct answer would be using numpy arrays. I bet it would have been acceptably fast.
When the goal is to find the closest point out of a set of points, it's pretty wrong. This is especially true when you consider that it's doing Manhattan distance on raw latitude and longitude. That means that if you happen to be near the poles, you could end up choosing a point that's orders of magnitude farther away than the nearest point. Even in more usual latitudes it means you'll treat east-west distances as substantially longer than north-south distances.
Sure, it could be a reasonable choice for some problems, but I have a hard time thinking of which ones those would be, and it would definitely need some discussion about the tradeoffs.
Like I said, "depending on the problem domain". In something close enough to a plane, you're guaranteed to be no worse than ~1.4 times the optimal solution. In an urban setting, euclidean tends to underestimate walking distance, so manhattan would compare even better. If you're working at close to fixed latitude, you can squash longitudes by a fixed amount and that'll give you a decent correction factor. Of course, this is true iff speed matters more than accuracy, and the relevant assumptions hold.
I'm sad, though, that he didn't just try to convert the original sophisticated function to numpy. I suspect the end result would've been "the really accurate function actually performs decently!"
I'm talking about this specific case, not the entire generalized idea of applying Manhattan distance to anything. Yeah, on a plane you're off by at most 1.4, but this isn't on a plane.
And really, I have no objection at all to approximations, but the lack of any acknowledgement that it even was an approximation is what bugged me.
True, but then it's never mentioned again even though the results could end up being way off, and there's more potential for error than the longitude factor that isn't mentioned at all.
Raw longitude is by far the largest approximation. It becomes really flawed near poles. But all my points are in mainland USA, and there we're pretty safe.
Anyway, I did say that I was using an approximation.
I don't know, there are a lot of regions where it transitions from horizontal to vertical where this naive latitude/longitude sum of differences will be way off.
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.
Nope; *ply are implemented as loops, you are only saving time on reallocating memory structures. Real speed-up is gained from using vectorised functions and operators (implemented in C or Fortran in R engine or a certain package) for whole vectors.
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.
Programmers shouldn't be wasting brain power deciphering cryptic variable names. Save that energy for where it counts (solving actual problems!)
"Not crazy" is a low standard. The point is I shouldn't have had to exert any mental energy whatsoever to understand what those variable names represented.
The point is, I shouldn't need to exert any mental energy at all. Code is read more than it is written. The onus is on the author to make things clear.
The example provided is trivial, sure. As complexity increases and you have more cryptic variable names to juggle, you'll be glad for the explicit, clear names.
Also, keep it mind that code will need to be comprehended in less than ideal circumstances. The engineer getting woken up in the middle of the night to fix a bug in production will not be at their mental peak. They'll be grateful for the clear naming conventions.
Meh... the idea that you can boost some brain power by relaxing other tasks seems unproven.
I will go so far as to say all of the truly buggy software I have ever seen had the most explicit variables. To the point that it is just a sideshow. Use them if they don't get in the way. Don't if they do.
I've found that sometimes its due to the programmer not wanting to try and figure out a good name for the variable. It sounds like a simple problem, but it is actually quite hard! Good variable names provide meaningful context that improve readability.
To be fair, this has the scent of a one-off script to do some simple analysis, versus something that's going to live in a git repo for the rest of eternity.
In the project I work on, I found a wonderful rats nest of variable names in a function that led to an excellent bug where "N" and "n" were swapped, leading to a completely different result.
Naming is one of THE difficult problems in software development, once you have the name decided, the functionality can be determined from that.
Poorly named functions/modules/variables/classes, etc are indicative of poorly thought out code.... as the other subject of this post (c vs python) also confirms.
Not that I necessarily agree, but here's what K&R has to say on naming variables:
"A variable or function name should be sufficient to understand the meaning, while remaining concise. The shorter the lifespan or scope of a variable, the shorter its name should be; conversely, the more important a variable, and the more places it is used, the more descriptive that name should be."
Seems the lesson is that Python is slow. Author's realization about how to use it correctly was to just call C instead.
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..."
Exactly. Usually a first approach at speeding up a loop is to just make it a list comprehension. I feel it's more pythonic to optimize for readability first and performance as needed; is the author upset he didn't get both at the same time?
umm NO. Whats next, BasicPerformanceTips? Its an interpreted language, it will always be at least 10x slower. Great for prototyping, bad for serious work.
There are a lot of problems where a 10x speed hit is totally fine, but a 100x speed hit is unacceptable. In cases like that, knowing how to make your interpreted code go faster can be really useful.
There is no such thing as an "interpreted language", there are only implementations. Please get rid of these old concepts.
CPython, which is the standard, most common implementation, uses bytecodes (and so does Java). There's nothing preventing one from generating machine code from a Python source. Some of Python's dynamic features are mandated from the spec, and there are limits on how fast that can be. But that has nothing to do with "being an interpreted language".
Agree, non-informative article. If you're doing linear algebra, it is always a good idea to notice and then use a library. Even in c/c++ using eigen[1] or mkl[2] for speed and stability is a good idea when doing linear algebra.
I like eigen, but their documentation is very lacking (only contains basic usage and toy examples). However, this isn't what caused me to abandon the library, it was the lack of support for 3-dimensional matrices.
therobot24 - What libraries do you like better? Eigen is my current favorite free linear algebra library but it doesn't have 3d matrices and doesn't support avx instructions which are both areas for improvement.
If you're iterating over all your points calculating distances, you are going about this the wrong way.
(edit) The author could use my handy python quad tree if he so wishes -- https://github.com/Dav3xor/pyquadtree, and if he asks nicely, I could even add support for simple approximation of spherical coordinates.
It is simple indeed. The performance I got was good enough to spare me the effort of using quad trees. Yes, I know what quad trees are. I even coded octrees for 3D reasoning in a previous life ;)
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].
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.
Just thinking a little bit about this problem, there is an easy to code, precise and top performance algorithm for solving the following two problems:
1) finding the points Pi within a certain distance d0 of a fixed point P0 in your database
2) finding the nearest point Pmin to P0, with Pmin in your database.
I will keep it for myself, but as a hint here are two steps:
first: read the John Cook article about deriving the distance formula, and second: think and easy way of avoiding unneeded computation.
It took me just a minute to realize the correct way to solve the OP, so it shouldn't take you long to solve it.
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.
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).
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).
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.
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.
It depends on what the for loop does, but main difference is that a for loop runs "interpreted", vs the list comprehensions that runs "compiled" (or in "C-space"). The list comprehension has some additional benefits, the pattern:
squares = []
for x in xrange(100):
squares.append(x*x)
in which you have an append call on every iteration is a mess because it may lead to a lot of memory operations which are really unnecesary. The LC version of it is much shorter an runs faster, because the memory allocation is handled differently:
squares = [x*x for x in xrange(100)]
Append may be O(1) but in some cases it doesn't behave nicely. On large lists, you can hit spots in which it reallocates parts of the list in memory, leading to weird slowdowns. Timings from ipython on a Windows 8 64bit Python 2.7.9 machine:
In [12]: def f1():
....: sq = []
....: for x in xrange(100):
....: sq.append(x*x)
....: return sq
....:
In [13]: def f2():
....: return [x*x for x in xrange(100)]
....:
In [14]: %timeit f1()
10000 loops, best of 3: 20.7 µs per loop
In [15]: %timeit f2()
100000 loops, best of 3: 11.9 µs per loop
Bear in mind that the LC will take all the memory needed at once, and that can bring some problems. You can also use a generator expresion (similar to a LC, but you use parenthesis instead of brackets) to avoid this problem, if you're expecting an iterable object and have no further need for the values after the computation is done:
In [1]: (x*x for x in xrange(100))
Out[1]: <generator object <genexpr> at 0x0000000003558438>
And the generator expression could be used inside a for loop in cases where de LC would be awkward or take more time (because you have to allocate memory for a billion numbers all at once, just to check those that are meet a certain requirement).
In your case reaching to numpy was probably the best you could do, as it abstracts and solves many things. Using properly "vectorized" numpy is also a big plus for readability.
I just wanted to mention a few things regarding the "pure python optimization" views which could help in cases where you're not writing numerical code that won't benefit from numpy.
> There are many programmers out there using Python as if it was C, and that leads to slower than necessary code.
I think it's because a lot of the Python (and I figure, other languages too) learning resources treat the learners the same way, whether you do not know any programming or are a 20-year veteran of C/C++.
I'd love to see resources which show the ideological way of doing things in a language. Take some of the most common tasks performed in other languages, and show how they're mapped properly to constructs in Python.
In this particular instance: I'm guessing the author could have used pure Python alone to get a decent speedup, without reaching for NumPy.
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.
I've begun to leverage the points made in the article quite a bit. Alas, now I get stuck when writing numpy based code because it constrains my ability to express a solution in the best suited idiom.
I just glanced through that document. Some thoughts (which may be stupid).
> Devectorize expressions
Why can't a compiler/whatever do this devectorisation for us if it is faster - I see that there is a macro package for this why not do it as standard?
> Write cache-friendly codes
Well duh.
> Identify opportunities to use BLAS
Is this not what numpy does already?
I suppose my real question about Julia is. Why? Why not put the effort into optimising numpy or making fortran a little more convenient to use rather than making a whole new special snowflake language just for one set of problems.
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.
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
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).
The results were as follows:
~ 14.2 seconds for Python 3.4.3 [1]
~ 9.0 seconds for Python 2.7.9 [1]
~ 9.0 seconds for PHP 5.6 [2]
~ 2.3 seconds for C [3]
~ 2.3 seconds for Java 8 [4]
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.
I have updated the test with the new figures that I got. Initially I only tested with Python 2 with math.pow. I have to say I am quite disappointed with the performance of Python 3 though and even using the built-in pow function, PHP 5.6 still is the fastest in this particular case.
PHP is no better, if you add an intval call it will add almost 4 seconds to the result! This is an extraordinary proof that being a little sloppy can cost you a lot when using interpreted scripting languages!
Also, I am thinking if and how much speed gain could one inject by not using OOP in PHP...
Now that is just ridiculous! With O2 and O3 I get 0.03 seconds on average! I try to understand what could possibly mean all of the flags that get switched on with optimizations from this page: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
I also wonder if Java has any kind of optimizations to experiment with.
Java doesn't have any optimization flags and the debugging info slowdown makes sense I suppose. That is the exact difference between them, GCC with -O3 is almost 100x faster in another test I just did: 10s for Java, 0.1 for C. When you turn off the optimization flags C jumps right at the same 10s figure though.
That's what I figured - a lot of people who say "Java is as fast as C" aren't doing proper compiler optimizations on their C. I suspected that was true, but I didn't spend the time on a proper test.
-O2 or -O3 does some neat stuff like unrolling loops and inlining functions
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?
103 comments
[ 5.1 ms ] story [ 153 ms ] threadLiterally any problem can be solved quickly in any language if you're willing to accept an incorrect answer.
The Manhattan (1-norm) metric is strongly equivalent to euclidean (2-norm) metric. Depending on your problem domain, that might be good enough.
Sure, it could be a reasonable choice for some problems, but I have a hard time thinking of which ones those would be, and it would definitely need some discussion about the tradeoffs.
I'm sad, though, that he didn't just try to convert the original sophisticated function to numpy. I suspect the end result would've been "the really accurate function actually performs decently!"
And really, I have no objection at all to approximations, but the lack of any acknowledgement that it even was an approximation is what bugged me.
' ignoring the fact that 1 degree difference in latitude yields a larger distance than 1 degree difference in longitude'
Anyway, I did say that I was using an approximation.
https://www.ibm.com/developerworks/community/blogs/jfp/resou...
Programmers shouldn't be wasting brain power deciphering cryptic variable names. Save that energy for where it counts (solving actual problems!)
The example provided is trivial, sure. As complexity increases and you have more cryptic variable names to juggle, you'll be glad for the explicit, clear names.
Also, keep it mind that code will need to be comprehended in less than ideal circumstances. The engineer getting woken up in the middle of the night to fix a bug in production will not be at their mental peak. They'll be grateful for the clear naming conventions.
I will go so far as to say all of the truly buggy software I have ever seen had the most explicit variables. To the point that it is just a sideshow. Use them if they don't get in the way. Don't if they do.
"I notice a lot of Python programmers tend to use less descriptive variable names."
In the project I work on, I found a wonderful rats nest of variable names in a function that led to an excellent bug where "N" and "n" were swapped, leading to a completely different result.
Poorly named functions/modules/variables/classes, etc are indicative of poorly thought out code.... as the other subject of this post (c vs python) also confirms.
You will see similar naming idiosyncrasies if someone writes Java in Python, or lisp in python (or Python in C, or Java in Lisp, etc.).
no excuse for names like that regardless of language.
"A variable or function name should be sufficient to understand the meaning, while remaining concise. The shorter the lifespan or scope of a variable, the shorter its name should be; conversely, the more important a variable, and the more places it is used, the more descriptive that name should be."
These names certainly conform to this standard.
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..."
I see numerous issues with the loop, for example, hash key lookups on 'Lat' and 'Long' for every iteration.
CPython, which is the standard, most common implementation, uses bytecodes (and so does Java). There's nothing preventing one from generating machine code from a Python source. Some of Python's dynamic features are mandated from the spec, and there are limits on how fast that can be. But that has nothing to do with "being an interpreted language".
[1]http://eigen.tuxfamily.org/index.php?title=Main_Page [2]https://software.intel.com/en-us/intel-mkl
(edit) The author could use my handy python quad tree if he so wishes -- https://github.com/Dav3xor/pyquadtree, and if he asks nicely, I could even add support for simple approximation of spherical coordinates.
K-d trees are even built in to SciPy, which the author probably already has installed (Scikit-Learn also has an implementation).
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.
[0] http://doublemap.github.io/blog/2015/05/29/optimizing-python...
1) finding the points Pi within a certain distance d0 of a fixed point P0 in your database
2) finding the nearest point Pmin to P0, with Pmin in your database.
I will keep it for myself, but as a hint here are two steps: first: read the John Cook article about deriving the distance formula, and second: think and easy way of avoiding unneeded computation.
It took me just a minute to realize the correct way to solve the OP, so it shouldn't take you long to solve it.
Not many things approach C speed, but PyPy has always seemed like pretty close
Yes, I used @jit(nopython=True). It does not compile pandas code.
More details here: http://pandas.pydata.org/pandas-docs/version/0.16.2/enhancin...
Also they recently added support for array expressions and allocation so you should upgrade if you haven't already.
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).
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.
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.
How much quicker? It isn't too significant, is it? I mean, we have two O(1) operations to worry about, I suppose: lookup and appending to the list.
That's a pretty good speed-up! Makes me reconsider writing some "complex" LC as for-loops.
In your case reaching to numpy was probably the best you could do, as it abstracts and solves many things. Using properly "vectorized" numpy is also a big plus for readability.
I just wanted to mention a few things regarding the "pure python optimization" views which could help in cases where you're not writing numerical code that won't benefit from numpy.
I think it's because a lot of the Python (and I figure, other languages too) learning resources treat the learners the same way, whether you do not know any programming or are a 20-year veteran of C/C++.
I'd love to see resources which show the ideological way of doing things in a language. Take some of the most common tasks performed in other languages, and show how they're mapped properly to constructs in Python.
In this particular instance: I'm guessing the author could have used pure Python alone to get a decent speedup, without reaching for NumPy.
[1] https://store.continuum.io/cshop/mkl-optimizations/
This article changed my opinion quite a bit and highlights the power of having a real macro system: http://julialang.org/blog/2013/09/fast-numeric/
I've begun to leverage the points made in the article quite a bit. Alas, now I get stuck when writing numpy based code because it constrains my ability to express a solution in the best suited idiom.
> Devectorize expressions
Why can't a compiler/whatever do this devectorisation for us if it is faster - I see that there is a macro package for this why not do it as standard?
> Write cache-friendly codes
Well duh.
> Identify opportunities to use BLAS
Is this not what numpy does already?
I suppose my real question about Julia is. Why? Why not put the effort into optimising numpy or making fortran a little more convenient to use rather than making a whole new special snowflake language just for one set of problems.
I contemplated quad trees but the performance of these 2 lines of code was good enough. Why would I bother writing something more complex?
you'd be surprised by my mathematical background ;)
The results were as follows:
~ 14.2 seconds for Python 3.4.3 [1]
~ 9.0 seconds for Python 2.7.9 [1]
~ 9.0 seconds for PHP 5.6 [2]
~ 2.3 seconds for C [3]
~ 2.3 seconds for Java 8 [4]
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.
[1] https://gist.github.com/anonymous/7edafa3889be967a1e1d
[2] https://gist.github.com/anonymous/56ff76849f5a312340d9
[3] https://gist.github.com/anonymous/5717ba935b43bad09e1d
[4] https://gist.github.com/anonymous/6b0c2f11609b951b64f3
The type conversion behavior of the math.pow function is clearly documented:
https://docs.python.org/3/library/math.html#math.pow
Also, I am thinking if and how much speed gain could one inject by not using OOP in PHP...
I also wonder if Java has any kind of optimizations to experiment with.
I don't know anything about Java optimization.
Really cool interesting stuff!
-O2 or -O3 does some neat stuff like unrolling loops and inlining functions
--fast_math is another one I use
> [ ... ]
> The lesson is clear: do not write Python code as you would do in C.
:)
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?
Pypy was not an option either, details in the post now.