4 ms·

> These can be so powerful that may make a dumb algorithm perform like an absolute superstar. That's an over-generalization that is only valid for small input

> These can be so powerful that may make a dumb algorithm perform like an absolute superstar. That's an over-generalization that is only valid for small input sizes. Consider: - an O(N*log N) heap-sort implemented by a decent programmer in idiomatic high-level code. - a dumb O(N^2) bubble-sort coded by an absolute assembly optimization wizard. Your O(N^2) sort will probably be much faster for small input sizes, but it won't take a large input size for it to become dog-crap slow. You can improve constant factors all day, but that won't obviate the need for doing millions or billions of comparisons. You can only take a dumb algorithm so far before it breaks down completely in practice. This is not a theoretical thing either - in unoptimized codebases, I've often seen people finding low-hanging fruit by looking for inadvertent O(N^2) or even O(N^3) behaviour (usually it's not obvious nested loops, but looping hidden by indirection i.e. function calls) and replacing it with an O(N*log N) or O(N) alternative.

madsbuch 4y ago
If your problem domain never expands to more than a couple of thousand elements that needs to be ordered, but really often (which is very often the case) the the bubble sort is the way to go (Especially if you have almost-sorted data making bubble sort the ideal choice). > That's an over-generalization I think this is exactly the problem with these types of comparisons. As the original commenter also hinted: You can not generalize best choice about the algorithm.
- twawaaay 4y ago
  I am pretty used to people defending their blind trust in big-O notation. As I mentioned, the idea is to be open to alternative ways of thinking. Performance is incredibly difficult or impossible to generalise. I have many times worked on a project where people said confidently it is not possible to speed something up and then I speeded it up by multiple orders of magnitude. I worked for one of largest banks in the world and we had a batch task on MongoDB that took 12 hours to complete. The previous team, before I joined, took it down to 4 hours but then said it is not possible to improve it anymore. The consultants from MongoDB confirmed it. This was a huge problem because there was a delay of 4 hours between end of trading day and the report being finished which was unacceptable. I took it down to ~15 seconds. Without changing data structure or the database or the application technology. The only significant thing I did is I made both the data suppliers to stream it to our app and the consumers to stream the results during the data. So the data was being processed during trading day and partial results were already being pushed to the client. The only thing that needed to be done was to sync between the sources and the clients and it took about 15 s to do it (and I could probably take it even further but it was not worth the effort). So you see, it is all about being open minded.
- kragen 4y ago
  bubble sort is never as good as insertion sort, not even for almost-sorted data or for six elements bubble sort is never the way to go generally in the case you're describing, where you have a few thousand elements that need to stay sorted in the face of insertions, a b-tree would be a better choice, or failing that, merge in a batch of updates whenever the update file gets big enough either of these can beat bubble sort or insertion sort in this situation by more than an order of magnitude
  - cozzyd 4y ago
    I'm sure it's possible to conceive of a pathological hardware architecture where bubble sort is faster than insertion sort on small inputs.
    - saagarjha 4y ago
      I mean sure, you can always come up with a processor that tries to detect insertion sort and makes it slow while it has hardware acceleration for bubble sort. That doesn't make it a very useful model, though.
astrobe_ 4y ago
> That's an over-generalization I think most people here will interpret the word "can" in the sentence you're quoting as a caveat emptor; and I would add the same applies to TFA. Loop fusion can etc. but measure if it actually does in your exact context. > You can improve constant factors all day, but that won't obviate the need for doing millions comparisons. > You can only take a dumb algorithm so far before it breaks down completely in practice. If the dumb algorithm relies entirely on arithmetic while the better algorithm has conditional jumps, branch prediction misses can play against it for unexpectedly large input sizes. Micro-optimizations may fall short quickly, but big-O() approved algorithms don't always win either, in practice.
- pclmulqdq 4y ago
  People usually underestimate where that line is. In my past experience, I ended up benchmarking binary search vs linear search on a collection of small objects. The breakeven point on a modern CPU was at 10 megabytes of data. Although this is a particularly extreme example, most people assume that collections of a few thousand items are where you should switch to big-O-optimal algorithms, but the breakeven is usually several orders of magnitude higher.
  - AgentOrange1234 4y ago
    That’s very surprising to me. My intuition screams that surely a binary search is competitive with a linear search even at small sizes. I would love to see benchmarks and code for this if you have them handy.
karmakaze 4y ago
Also using big-O notation turns the "1/2" of the post title into a discarded constant.
- mrguyorama 4y ago
  My algorithms class discussed the importance of not forgetting the constants. We talked about an algorithm for recursively taking averages of a list of numbers (or whatever that's not important) that was O(n^2) but only in worst case, while there was a version that is guaranteed O(nlogn) or something but the constant factor was 27. This meant the growth only mattered in extreme cases.
  - karmakaze 4y ago
    That math doesn't seem to check out. Say with base-2 log and a 27 factor difference, for 1000 it would be 1000^2 = 1,000,000 vs 27 * 1000 x log 1000 = 270,000. I wouldn't call n=1000 an extreme case for most problems. Just because practical counterexamples exist, don't think that it applies to your problem unless demonstratably so, an then still worry about N being larger than originally designed for.

madsbuch 4y ago

If your problem domain never expands to more than a couple of thousand elements that needs to be ordered, but really often (which is very often the case) the the bubble sort is the way to go (Especially if you have almost-sorted data making bubble sort the ideal choice). > That's an over-generalization I think this is exactly the problem with these types of comparisons. As the original commenter also hinted: You can not generalize best choice about the algorithm.

twawaaay 4y ago
I am pretty used to people defending their blind trust in big-O notation. As I mentioned, the idea is to be open to alternative ways of thinking. Performance is incredibly difficult or impossible to generalise. I have many times worked on a project where people said confidently it is not possible to speed something up and then I speeded it up by multiple orders of magnitude. I worked for one of largest banks in the world and we had a batch task on MongoDB that took 12 hours to complete. The previous team, before I joined, took it down to 4 hours but then said it is not possible to improve it anymore. The consultants from MongoDB confirmed it. This was a huge problem because there was a delay of 4 hours between end of trading day and the report being finished which was unacceptable. I took it down to ~15 seconds. Without changing data structure or the database or the application technology. The only significant thing I did is I made both the data suppliers to stream it to our app and the consumers to stream the results during the data. So the data was being processed during trading day and partial results were already being pushed to the client. The only thing that needed to be done was to sync between the sources and the clients and it took about 15 s to do it (and I could probably take it even further but it was not worth the effort). So you see, it is all about being open minded.
kragen 4y ago
bubble sort is never as good as insertion sort, not even for almost-sorted data or for six elements bubble sort is never the way to go generally in the case you're describing, where you have a few thousand elements that need to stay sorted in the face of insertions, a b-tree would be a better choice, or failing that, merge in a batch of updates whenever the update file gets big enough either of these can beat bubble sort or insertion sort in this situation by more than an order of magnitude
- cozzyd 4y ago
  I'm sure it's possible to conceive of a pathological hardware architecture where bubble sort is faster than insertion sort on small inputs.
  - saagarjha 4y ago
    I mean sure, you can always come up with a processor that tries to detect insertion sort and makes it slow while it has hardware acceleration for bubble sort. That doesn't make it a very useful model, though.

astrobe_ 4y ago

> That's an over-generalization I think most people here will interpret the word "can" in the sentence you're quoting as a caveat emptor; and I would add the same applies to TFA. Loop fusion can etc. but measure if it actually does in your exact context. > You can improve constant factors all day, but that won't obviate the need for doing millions comparisons. > You can only take a dumb algorithm so far before it breaks down completely in practice. If the dumb algorithm relies entirely on arithmetic while the better algorithm has conditional jumps, branch prediction misses can play against it for unexpectedly large input sizes. Micro-optimizations may fall short quickly, but big-O() approved algorithms don't always win either, in practice.

pclmulqdq 4y ago
People usually underestimate where that line is. In my past experience, I ended up benchmarking binary search vs linear search on a collection of small objects. The breakeven point on a modern CPU was at 10 megabytes of data. Although this is a particularly extreme example, most people assume that collections of a few thousand items are where you should switch to big-O-optimal algorithms, but the breakeven is usually several orders of magnitude higher.
- AgentOrange1234 4y ago
  That’s very surprising to me. My intuition screams that surely a binary search is competitive with a linear search even at small sizes. I would love to see benchmarks and code for this if you have them handy.

karmakaze 4y ago

Also using big-O notation turns the "1/2" of the post title into a discarded constant.

mrguyorama 4y ago
My algorithms class discussed the importance of not forgetting the constants. We talked about an algorithm for recursively taking averages of a list of numbers (or whatever that's not important) that was O(n^2) but only in worst case, while there was a version that is guaranteed O(nlogn) or something but the constant factor was 27. This meant the growth only mattered in extreme cases.
- karmakaze 4y ago
  That math doesn't seem to check out. Say with base-2 log and a 27 factor difference, for 1000 it would be 1000^2 = 1,000,000 vs 27 * 1000 x log 1000 = 270,000. I wouldn't call n=1000 an extreme case for most problems. Just because practical counterexamples exist, don't think that it applies to your problem unless demonstratably so, an then still worry about N being larger than originally designed for.