2 ms·

>I can now see a small comment saying it's running in O(n^2) and there is no technical reason why it needs to. What technical reason?!!? That was my point! In

>I can now see a small comment saying it's running in O(n^2) and there is no technical reason why it needs to. What technical reason?!!? That was my point! In your comment there is an implicit assumption that an O(N^2) algorithm is a potential problem simply because it is an O(N^2) algorithm. That's just wrong. Would you put a comment like: "This is O(n). Might cause issues if the 'c' gets too big"? It's useless. __IF__ it is a potential problem, your laziness simply created a time-bomb that will blow up in somebody's face later. Your comment isn't helping anybody. For example, when your product is new, you may have 10 users, taking 10 courses in various permutations. You write your naive O(N^2) search and everything looks great, and you put your comment in. Everything is great for months, then you hit it big, and now you have 100 courses and 10,000 users and now you're dead. Thanks for your comment, it was really helpful! Devs tend to be allergic to O(N^2) because it is beaten into us in school and during interviews. On the one hand, that's good, it gets people thinking about runtime performance. On the other hand, if you just have a shallow view of it it's a crutch. Those same people may for example, wrap that algorithm in an a lambda that has an internal time-complexity of O(N^2) anyway (but at least you don't see the double for-loop) or use a chain of lambda calls, getting their O(N) but nevertheless losing performance because of constant costs around execution and allocation. >and it might make life easier for someone in the future, so i'll do it. That's where I disagree. It really doesn't.

Klathmon 10y ago
>For example, when your product is new, you may have 10 users, taking 10 courses in various permutations. You write your naive O(N^2) search and everything looks great, and you put your comment in. Everything is great for months, then you hit it big, and now you have 100 courses and 10,000 users and now you're dead. Thanks for your comment, it was really helpful! You seem to think that it's inevitable that my O(n^2) function will become a problem, it won't. I'm using it in the context of tasks in a build system. There is no way that any human is going to have 100,000 tasks, 100,000 independent targets. It's not going to happen, so optimizing this now is completely pointless. The time savings on the CPU would literally never add up to the amount of extra time i'd spend on it. But in the future let's say that the platform pivots and the dependency mapping system gets pulled out and used for something else, or we switch to another architecture where each file involved in the task becomes a "task" itself, now the chance that there are 100,000 tasks is not only possible, but pretty likely, and that O(n^2) algorithm is now a problem. Switching to something like a depth first search of the dependency tree and some creative use of tags could probably do the same job in linear time, but it adds complexity to the code, takes longer to develop, will be harder to test, and will provide 0 benefit to the codebase as it is. You can see how optimizing for a possibility that the whole system might change purpose and that code is still there is a silly rabbit hole to go down. (how would you ever actually produce anything?) >>and it might make life easier for someone in the future, so i'll do it. >That's where I disagree. It really doesn't. Then there is no harm no foul. Nobody is harmed by the extra comment, and life goes on. There isn't a scenario where a one-line comment explaining why the code is the way it is causes anyone an issue, so there's no reason to not do it. But the point of the code is to give assurance to the future developer that the only reason why the code is that way is because there was no reason to optimize it that way at the time. On the other hand, if the algorithm is required to be O(n^2) (like in a maximum matching graph), then i'd put a comment explaining that it's needed. Again, it might be entirely useless (in which case, nobody loses anything), or it might help the dev skip over that in the preliminary searches and look deeper for where any possible speedups can be found, saving time and money.

Klathmon 10y ago

>For example, when your product is new, you may have 10 users, taking 10 courses in various permutations. You write your naive O(N^2) search and everything looks great, and you put your comment in. Everything is great for months, then you hit it big, and now you have 100 courses and 10,000 users and now you're dead. Thanks for your comment, it was really helpful! You seem to think that it's inevitable that my O(n^2) function will become a problem, it won't. I'm using it in the context of tasks in a build system. There is no way that any human is going to have 100,000 tasks, 100,000 independent targets. It's not going to happen, so optimizing this now is completely pointless. The time savings on the CPU would literally never add up to the amount of extra time i'd spend on it. But in the future let's say that the platform pivots and the dependency mapping system gets pulled out and used for something else, or we switch to another architecture where each file involved in the task becomes a "task" itself, now the chance that there are 100,000 tasks is not only possible, but pretty likely, and that O(n^2) algorithm is now a problem. Switching to something like a depth first search of the dependency tree and some creative use of tags could probably do the same job in linear time, but it adds complexity to the code, takes longer to develop, will be harder to test, and will provide 0 benefit to the codebase as it is. You can see how optimizing for a possibility that the whole system might change purpose and that code is still there is a silly rabbit hole to go down. (how would you ever actually produce anything?) >>and it might make life easier for someone in the future, so i'll do it. >That's where I disagree. It really doesn't. Then there is no harm no foul. Nobody is harmed by the extra comment, and life goes on. There isn't a scenario where a one-line comment explaining why the code is the way it is causes anyone an issue, so there's no reason to not do it. But the point of the code is to give assurance to the future developer that the only reason why the code is that way is because there was no reason to optimize it that way at the time. On the other hand, if the algorithm is required to be O(n^2) (like in a maximum matching graph), then i'd put a comment explaining that it's needed. Again, it might be entirely useless (in which case, nobody loses anything), or it might help the dev skip over that in the preliminary searches and look deeper for where any possible speedups can be found, saving time and money.