91–100 of 237 posts
The 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.
I used to know a professor who switched from the hardware department to the software department. His reason? With hardware I can reduce runtime by 10 or 100. With software I can reduce runtime by log(x).
Earlier quoted context omitted.
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…
1. Solve the problem.
2. Ensure correctness of that solution
3. The code is easy to reason about
4. The app is robust
5. "good enough" performance
6. Performance tuning
Which is of course the "correct answer", and of course in practice these all blend together I will emphasize any number of those at a given time (who doesn't love spending an occasional afternoon just chasing pointless benchmarks?). But I never come at it from a "big O mindset" even when that's what I'm doing in practice, I just call it "common sense" and heuristics: don't put slow things in tight loops, memoize when you can, and leverage concurrency.
In my line of work (CV), moving a slow blocking operation from serial to async will get you easy, bigger wins 90% of the time, vs seeking out something in polytime and refactoring to nlogn.
Earlier quoted context omitted.
It sounds like you do know how to optimize. Your important metric is just different. You're optimizing for your time rather than the computer's because that's by far the more valuable resource in your set of constraints.
Another consideration is that the unoptimized version of the algorithm may be easier to explain and study. So he might also be optimizing for clarity.
Earlier quoted context omitted.
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).
The way in which I like to often think about these things in practice is with "hidden" constant factors. For example, you can think of the O(1) algorithm as really taking O(1 * K1) time, and the O(n) algorithm taking O(n * K2) time to complete. For different algorithms, K1 and K2 will almost certainly be distinct, and may even differ by significant amounts. Of course, if K1 is less than K2, then the value of "n" is i…
"f(x) ∈ O(g(x)) as there exists c > 0 and x0 such that f(x) ≤ cg(x) whenever x ≥ x0"
Saying f(x) is O(g(x)) doesn't say anything about how those two functions compare below x0?
https://en.wikipedia.org/wiki/Big_O_notation
Edit: Not trying to be snarky - just trying to check whether my 30+ year old memory of education on such matters is even vaguely correct... :-)
Edit2: Added "memory of" - I'm pretty sure what I was taught was correct, just my memory of it that is all too fallible.
Computer 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…
So one of the applications I have worked with was an embedded credit card terminal app which needed a transactional database. Since I could not find a product that would fit all requirements I decided to write one. Now, you can imagine smart algorithms, trees, hashes... Nothing of that sort. The database was written as append only transactional log. To retrieve data, entire file was scanned for initial record and all…
Obviously the author of this script didnt know about sql joint. Reduced the work into one "for" loop and an custom sql join query as input, script running in less than 5 minutes compared to average 5hours before.
Isn’t this just a simple quantization? (Lat/20,Lon/20) should do it?