9 ms·
Python Is Not C
- mikeash 11y agoIt'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.
- cowsandmilk 11y agoIt 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.
- jfpuget 11y agoI did it. It runs way faster than the loop, but it runs about 4x slower than my approximation. Details in the post. Thanks for suggesting that.
- deleted 11y ago[deleted]
- pdpi 11y ago> Manhattan distance approximation is seriously wrong The Manhattan (1-norm) metric is strongly equivalent to euclidean (2-norm) metric. Depending on your problem domain, that might be good enough.
- mikeash 11y agoWhen 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.
- pdpi 11y agoLike 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!"
- mikeash 11y agoI'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.
- pdpi 11y agoFair deuce, the lack of acknowledgement does bug me as well.
- jfpuget 11y agoYou should reread the post to find the acknowledgement that was there since the begining: ' ignoring the fact that 1 degree difference in latitude yields a larger distance than 1 degree difference in longitude'
- mikeash 11y agoTrue, 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.
- im3w1l 11y agoA look at his data indicates it should be good enough. https://www.ibm.com/developerworks/community/blogs/jfp/resource/BLOGS_UPLOADED_IMAGES/raam_route.png https://www.ibm.com/developerworks/community/blogs/jfp/resou...
- mikeash 11y agoI 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.
- larrydag 11y agoThe 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.
- mbq 11y agoNope; *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.
- compostor42 11y agoHis 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!)
- deleted 11y ago[deleted]
- mondoshawan 11y agoThe fact that you're guessing is the parent's point. Code should be explicit.
- deleted 11y ago[deleted]
- compostor42 11y ago"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.
- GFK_of_xmaspast 11y agoIf you're exerting more than a trivial amount of mental energy to figure out those names then you simply need more practice.
- compostor42 11y agoThe 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.
- adultSwim 11y agoSeems 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..."
- dekhn 11y agoActually, in most cases, you can speed up loops in python knowing just a few tricks. https://wiki.python.org/moin/PythonSpeed/PerformanceTips https://wiki.python.org/moin/PythonSpeed/PerformanceTips I see numerous issues with the loop, for example, hash key lookups on 'Lat' and 'Long' for every iteration.
- someone7x 11y agoExactly. 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?
- rasz_pl 11y agoumm NO. Whats next, BasicPerformanceTips? Its an interpreted language, it will always be at least 10x slower. Great for prototyping, bad for serious work.
- e12e 11y agoSure. Quick performance tip for basic, use a complied dialect, like Blitz Basic (now, not quite just BASIC, and called Blitz).
- mikeash 11y agoThere 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.
- 11y ago
- Dav3xor 11y agoIf 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 https://github.com/Dav3xor/pyquadtree, and if he asks nicely, I could even add support for simple approximation of spherical coordinates.
- dhenneberger 11y agoI feel like a k-d tree would be a more appropriate solution, if the programmer wanted to write more than a simple loop.
- Dav3xor 11y agoSure, absolutely. Just wanted to point out that the article isn't very sophisticated.
- jfpuget 11y agoIt 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 ;)
- deleted 11y ago[deleted]
- shoyer 11y agoIndeed, came here to say exactly this. K-d trees are even built in to SciPy, which the author probably already has installed (Scikit-Learn also has an implementation).
- erjiang 11y agoInteresting 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. [0] http://doublemap.github.io/blog/2015/05/29/optimizing-python/ http://doublemap.github.io/blog/2015/05/29/optimizing-python...
- noreasonw 11y agoJust 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.
- hardwaresofton 11y agoI wonder if the poster heard of pypy Not many things approach C speed, but PyPy has always seemed like pretty close
- _dark_matter_ 11y agoOr, you know, Cython. Just find whatever is slowing you down and write that in (semi)raw C. Keep everything else Python.
- jfpuget 11y agoAnd you lose python interactivity. If I have to compile code then I use C or C++ directly.
- chomp 11y agoActually the Python C API is part of the Python language, so part of Python is actually C.
- Lofkin 11y agoHe missed a critical option: you can write those loops in python and JIT them to C fast LLVM with numba: https://github.com/numba/numba https://github.com/numba/numba
- jfpuget 11y agoI tried numba. It isn't helping here. Yes, I used @jit(nopython=True). It does not compile pandas code.
- Lofkin 11y agoTry converting to a numpy array, executing the operations and converting back to pandas. More details here: http://pandas.pydata.org/pandas-docs/version/0.16.2/enhancingperf.html?highlight=numba 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.
- toyg 11y agoThe 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.
- collyw 11y agoI don't think that is exclusive to Python.
- ovis 11y agoIf this is more than a one-off, then maybe he should be using a quadtree rather than a search along a list of points.
- jfpuget 11y agoAgreed.
- dr_zoidberg 11y agoThere 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.
- odonnellryan 11y ago> the list comprhension surely runs faster than the for loop 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.
- dr_zoidberg 11y agoIt 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
- sonium 11y agoTo 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. [1] https://store.continuum.io/cshop/mkl-optimizations/ https://store.continuum.io/cshop/mkl-optimizations/
- dilap 11y agoThe same thing happens in reverse for Julia programmers coming from Python.
- JupiterMoon 11y agoSo if I move to Julia will I need to go back to looping over arrays all the time? I mean Fortran 90 had whole array operations already...
- shele 11y agoNo. You don't get punished for it, if you have to or like to.
- elcritch 11y agoMy initial thoughts as well. It's hard to think about going back to manual looping. Seemed like a step backwards even. 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/ 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.
- JupiterMoon 11y agoI 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.
- noreasonw 11y agoThe 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.
- jfpuget 11y agoI agree it is well known. I am just providing yet another example. 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 ;)
- ArenaSource 11y agoIt'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
- bite_victim 11y agoSome 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. [1] https://gist.github.com/anonymous/7edafa3889be967a1e1d https://gist.github.com/anonymous/7edafa3889be967a1e1d [2] https://gist.github.com/anonymous/56ff76849f5a312340d9 https://gist.github.com/anonymous/56ff76849f5a312340d9 [3] https://gist.github.com/anonymous/5717ba935b43bad09e1d https://gist.github.com/anonymous/5717ba935b43bad09e1d [4] https://gist.github.com/anonymous/6b0c2f11609b951b64f3 https://gist.github.com/anonymous/6b0c2f11609b951b64f3
- maxerickson 11y agoYou should use the built in pow for the python version (or the double asterisk operator). I guess most of the difference with PHP is there. The type conversion behavior of the math.pow function is clearly documented: https://docs.python.org/3/library/math.html#math.pow https://docs.python.org/3/library/math.html#math.pow
- bite_victim 11y agoI 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.
- maxerickson 11y agoThe call to int is unnecessary when using the built in.
- kazinator 11y ago> The reason for that speedup is that numpy array operations are written in C. > [ ... ] > The lesson is clear: do not write Python code as you would do in C. :)
- TheLoneWolfling 11y agoI'd personally have jumped straight to PyPy. 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?
- jfpuget 11y agoI didn't use C. Read again ;) Pypy was not an option either, details in the post now.