3 ms·

Yeah and it almost always stops being fine. The problem with an O(N^2) solution is that you rarely put in an assert that N < 100 or something like that to guard

Yeah and it almost always stops being fine. The problem with an O(N^2) solution is that you rarely put in an assert that N < 100 or something like that to guard your assumption that big N "doesn't happen". Because after all it's better that the process eventually completes than that the process crashes. And if you don't dare to put that in, you perhaps shouldn't use O(N^2). N^2 or N^3 is fine for things that are fixed size and very unlikely to stop being fixed size, or at least unlikely to grow a lot. But any time you think "oh it's just a few files" when there is nothing to stop it from being 1000 files in ten years, or at one rare user: don't use an O(N^2) solution.

kortilla 3y ago
> Yeah and it almost always stops being fine. No, it’s just a non-issue in the 99% of cases where it really does stay at small inputs. I come across configuration code all of the time that is stupidly inefficient like this and it’s almost always irrelevant. Tons of stuff works on inputs of <10.
- alkonaut 3y ago
  It's an observation with heavy selection bias: in 100% of the cases where you had to deal with a perf problem it had stopped being fine... Since it also almost invariably is accidentally quadratic and not deliberately quadratic as with BubbleSort, you also have a hard time estimating how many quadratic algorithms you have that haven't caused problems, and perhaps never will. Adding complexity because of an anticipation that some input will grow to an unreasonable size (at the time of writing) may or may not be a good idea. But using a different off the shelf function or data structure is usually not a high cost for making sure it's not a problem down the line. Of course, that also assumes that there is a good and efficient standard lib of methods and data structures so that "making a more clever choice" isn't also a burden or risk in terms of code size, complexity, risk of bugs.
- GuB-42 3y ago
  The problem is that it is an issue in 1% of cases, and it is hard to know in advance which 1%. So either you do a proper analysis to see how many inputs you really need, or you use an algorithm that scale. For sorting, getting a n.log(N) algorithm that doesn't break down is usually just a matter of calling a library, or writing <100 lines of code if you really can't use a library. It usually doesn't have much of a negative impact when the number of inputs is small, and it is often simpler than making a proper analysis. So, when in doubt, never use a n^2 sorting algorithm.
masklinn 3y ago
Here it took almost 30 years for it to stop being fine, which is a pretty good run. And it was a blatant O(n^2) algorithm, easily swapped out, it’s not like they were calling sscanf in a loop and whoopsie turns out C strings are shit so now parsing a 4 characters decimal number is O(buflen^2).
- alkonaut 3y ago
  One should indeed be forgiven when getting 30 years out of a code base, any code base. It's hard to predict that you'd need to shave milliseconds of cloud/VM startups or from some embedded device, if you can't imagine Clouds, VMs or computers the size of watches.
toast0 3y ago
> Yeah and it almost always stops being fine. Properly predicting if it will be fine or not is a sign of wisdom. But something like this is a fine place to use something where the complexity blows up. The sort happens in a clear place; early boot is a little hard to debug, but still. It's much worse when you put something N^3 in where when it blows up, the time spent is diffuse.

kortilla 3y ago

> Yeah and it almost always stops being fine. No, it’s just a non-issue in the 99% of cases where it really does stay at small inputs. I come across configuration code all of the time that is stupidly inefficient like this and it’s almost always irrelevant. Tons of stuff works on inputs of <10.

alkonaut 3y ago
It's an observation with heavy selection bias: in 100% of the cases where you had to deal with a perf problem it had stopped being fine... Since it also almost invariably is accidentally quadratic and not deliberately quadratic as with BubbleSort, you also have a hard time estimating how many quadratic algorithms you have that haven't caused problems, and perhaps never will. Adding complexity because of an anticipation that some input will grow to an unreasonable size (at the time of writing) may or may not be a good idea. But using a different off the shelf function or data structure is usually not a high cost for making sure it's not a problem down the line. Of course, that also assumes that there is a good and efficient standard lib of methods and data structures so that "making a more clever choice" isn't also a burden or risk in terms of code size, complexity, risk of bugs.
GuB-42 3y ago
The problem is that it is an issue in 1% of cases, and it is hard to know in advance which 1%. So either you do a proper analysis to see how many inputs you really need, or you use an algorithm that scale. For sorting, getting a n.log(N) algorithm that doesn't break down is usually just a matter of calling a library, or writing <100 lines of code if you really can't use a library. It usually doesn't have much of a negative impact when the number of inputs is small, and it is often simpler than making a proper analysis. So, when in doubt, never use a n^2 sorting algorithm.

masklinn 3y ago

Here it took almost 30 years for it to stop being fine, which is a pretty good run. And it was a blatant O(n^2) algorithm, easily swapped out, it’s not like they were calling sscanf in a loop and whoopsie turns out C strings are shit so now parsing a 4 characters decimal number is O(buflen^2).

alkonaut 3y ago
One should indeed be forgiven when getting 30 years out of a code base, any code base. It's hard to predict that you'd need to shave milliseconds of cloud/VM startups or from some embedded device, if you can't imagine Clouds, VMs or computers the size of watches.

toast0 3y ago

> Yeah and it almost always stops being fine. Properly predicting if it will be fine or not is a sign of wisdom. But something like this is a fine place to use something where the complexity blows up. The sort happens in a clear place; early boot is a little hard to debug, but still. It's much worse when you put something N^3 in where when it blows up, the time spent is diffuse.