4 ms·
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 answe
by mikeash 11y ago
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.
- 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.