4 ms·
How much optimization you need depends on the situation. The first question is for how many concurrent users are you going to write it for. In most cases O(n^2)
by cjfd 7y ago
How much optimization you need depends on the situation. The first question is for how many concurrent users are you going to write it for. In most cases O(n^2) is too much unless you know that in practice n is always going to be less than 10. Even then you should be quite certain that n is never going to become bigger, which you very often aren't. Removing constant factors, i.e., turning 3*n into n, should only be done if it is not difficult and is not bad for code quality in most cases. But at some point you should start removing these constant factors. Maybe if you need to handle more than 10000 requests a second. These numbers are highly variable depending on the application, the language and the use.
- wruza 7y agoUpvoted you for the first half. Hell, if algo is cubic or exponential out of pure simplicity, then as little as x3-10 input will bring it to its knees. It is not worth revisiting it later with all surrounding costs, if that’s inevitable anyway. Optimization is premature only if the code is not already fantastically stupid, which may happen too often irl to ignore that. Couldn’t agree with constant factors though. These are pretty random, n-independent (i.e. scalable) and the net expense of making code less obvious is usually bigger than throwing more/better hardware at it, but ymmw.
- saagarjha 7y agoRunning a single pass instead of two is often useful.
- samatman 7y agoThis falls apart when you consider one common scenario: We are loading a number of data files and the source of truth is remote. This is O(n) the amount of data. Two ways to do it: always request the remote data, or cache it, and only ask the remote for changes. These differ by a constant factor, and it's always a good idea to maintain a local cache when it's possible. Otherwise there's a very good chance that startup time will be dominated by network requests.
- wruza 7y agoYeah, it depends on how big that const is. But this also falls into “fantastically stupid” category. Just like all web 2.0 e-stores I have to use, which rerequest their dataset every time you touch sort or filter controls. When their largest category is 150kb json and the entire site json is 10x smaller than their ui/ad frameworks.