A Geohash (https://en.wikipedia.org/wiki/Geohash), a (decoding of a) recursive spacing-filling curve, would be much faster still: you literally slash a couple of characters of the tail of the hash to end up with your bigger cell, etc. It does mandate the way in which the grid/globe is subdivided though, which may not be suitable for the stated case.
14,000x Speedup (2015)
41–50 of 237 posts
Re: 14,000x Speedup (2015)
#42Sorry, but FTW will always mean "f... the world".
I've never seen it used that way. In WTF and FML, yes, but never in FTW.
Re: 14,000x Speedup (2015)
#43Trying to get Bootcamp grads to learn CS is like pulling teeth. The worst thing I hear as an employer is, "I dropped out of my CS degree because the last couple years of classes weren't applicable to daily programming".
I've started Qvault to try to address the problem... We'll see where it goes.
Re: 14,000x Speedup (2015)
#44Computer Science for the... loss? I did not study computer science in any substantial way, and I hardly consider myself a computer scientist, but I do have a nose for algorithms despite not really thinking about it in a structured way. I think lot of people get wrapped up in the notation without realizing they can approach the problem in a completely different way. Case in point, a professor at a University in the US…
The tagger's speed was probably enough for what the professor intended at the time. They probably knew how to optimize it, but didn't because they had no reason to.
I say this as a professor myself, because we do that all the time in my team: we create some software system (also in NLP, by the way), we do experiments to show that it improves whatever metric we are interested in or that it teaches us something interesting, we publish a paper with it, make the code available and then move on to the next paper. That's what we are typically incentivized to do. The time spent into optimizing a system that we are not going to take to production anyway is time not spent doing more research. Which doesn't mean that we don't know how to optimize.
Re: 14,000x Speedup (2015)
#45The next level is "Google for the win", in which you realize that this particular part of your problem (nearest neighbor search) is so ubiquitous that there is library for it in pretty much any language.
Re: 14,000x Speedup (2015)
#46I was lucky enough to come upon a similar speedup in some code that was used a fair bit at first job; multiple order of magnitude speed up by applying some data structure knowledge.
I feel like base level algorithm/ds knowledge is getting higher so these will disappear, even if you don't know the exact solution your intuition will make you think "there's no way this needs to be so slow" and then you do some research/thinking.
Re: 14,000x Speedup (2015)
#47Earlier quoted context omitted.
Exactly. I like the enthusiasm of the author; but the self-congratulatory attitude doesnt go down very well if you should actually be ashamed of the first version. I mean it is only a few inches from:"you know in the old days we had to flip through the telephone directory from front to end to find a name. But you know what: it is actually a sorted list, so we applied a binary search algorithm and are 14000x faster. T…
You'd be surprised how often "flip through the telephone directory" thing comes out in the real projects. Sometimes it is one of those "we did a quick hack and then forgot about it as data sizes grew", sometimes one just forgot about the complexity, and occasionally there are people who don't understand the problem at all.
I agree, and I also think this should be the first solution since it is obviously correct so you can test your faster algo later against this (at least in the post the invariants of the dataset are not spelled out exactly, and we know premature optimization..). But I do not think you should expect a trophy when later fixing it (when profiling shows it is a problem).
Re: 14,000x Speedup (2015)
#48Earlier quoted context omitted.
Computer Science is just academic/theoretical programming. While having a relevant education usually beats not having one, real-world experience usually beats theoretical knowledge when it comes to achieving real-world gains. E.g. if I want something computed as quickly as possible I'm probably better off asking an average game engine programmer than an average CS professor, since they'll optimize for cache efficienc…
People obsessed with big O are super annoying. To them O(1) trumps O(n) even if it's a tiny little set of data where clearly the latter is actually faster (stopwatch time).
It’s good to understand what the “Big O” for your algorithm is, but, yes, people who obsess over it are annoying. If I know I’m processing 100 items very rarely,[a] does it matter if my quick and dirty sorting (no pun intended) algorithm is bubble or quick sort? They both complete in a fraction of a second, and the user (generally) isn’t going to notice a difference between a single frame update delta or two.
[a] Key words are 100 items very rarely: if you’re sorting many times a second (for whatever reason) or (relatively) large datasets, using a quicker sorting algorithm than bubble or insertion would make sense.
Re: 14,000x Speedup (2015)
#49> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?
Yeah there are plenty of programs where you can tell whether they terminate or not. The proof that the halting problem is decidable has a self referential component and most programs aren't self referential like this, nor do they make any library calls to halting problem deciders :). I think it's OK to do this simlification in a simple post like this, but important to keep in mind that it's a simplification. To make…
The proof that Turing gave never really left me fully convinced. Surely if the Romans had "the answer that denies the former" then clearly some version of it is possible in software.
Re: 14,000x Speedup (2015)
#50Gamedev! One of the best parts of being in gamedev was that the problem space forces you to work this stuff out. People won’t wait 30 minutes for a frame to render. A few ways to solve this pop to mind. As Aeolun mentions in a parallel comment, you can just divide coordinates if your grid is regular. But it often isn’t. In that case, you can attack it in a few ways. One time Feynman was giving a lecture and said “Thi…
That's a quadtree, or an octree in 3D.
A k-D tree?