3 ms·
Sometimes a worse O algo is way better in real life, due to things such as memory alignment and page size. The more time you spend writing high performance code
by brianwawok 11y ago
Sometimes a worse O algo is way better in real life, due to things such as memory alignment and page size. The more time you spend writing high performance code, the more you learn that the kind of algorithm analysis you learn in school is crap in the real world. If my O(N^2) also is 3 lines and smoking in real benchmarks your 600 line O(n log n) algo, guess which one I am using?
- buckhx 11y agoRaycasting is a pretty expensive operation since you have to check every edge of the polygon. Honestly I'm guessing they implemented the brute force method and called it good enough. Otherwise they would have posted comparisons as to why they stuck with brute force.
- brianwawok 11y agoWell they had a clearly defined goal (which is rare!). 99% of requests in <= 100ms. So if brute force was a very simple algo and met the goal - hey why not? If you can come up with a goal of what you need the response times to be, I think the easiest (in terms of readability, testability, length, etc) solution to meet the goal should win.
- sesquipedalian 11y agoI've found that BSP trees are a quite elegant, albeit, more complicated alternative for handling point-in-polygon queries compared to raycasting. Essentially, it decomposes an arbitrary non-convex polygon into a binary tree of half-spaces. A point-in-poly test then just becomes a binary search. That being said sometimes brute force is good enough.
- vvanders 11y agoYup, so much this. I always have fun trotting out Radix Sort and watching fresh CS grads try to understand how a O(kN) walks over O(NlogN) by a factor of 10x+.
- brianwawok 11y agoI also have fun busting out O(N^2) and getting a death stare. Then I ask them the biggest N could possibly be and get an answer like "16"...
- vvanders 11y agoHaha yeah, Fun bit about Radix is it really scales well if your dataset fits in memory. Last time I benched my lame Java implementation it was about 2-5x faster than the built in Arrays.sort() on native values(float, int) and 20x faster when you started putting it up against Comparable. Trended that way well up to 65k+ entries. It gets even better if you can drop down to a proper native language that lets you prefetch.
- chris_overseas 11y agoAbsolutely. But the impression I get from the article isn't that they benchmarked their solution vs R-trees or S2 and it proved quicker, rather it seems to me they didn't bother trying the other approaches at all because of their perceived complexity. I might have the wrong end of the stick because the article doesn't go into enough detail to truly know either way. If they really didn't benchmark any other algorithms then talking about the performance of the language seems somewhat moot.
- rifung 11y agoI'm not sure that your example shows that the analysis you learn in school is "crap in the real world". Using O analysis is for seeing how an algorithm scales with respect to the input size. If anything, the fact that someone believes a O(nlogn) algorithm is always faster than O(n^2) is a failure on that person's part in properly understanding what O is used to measure.