4 ms·

I think there are phases to this. 1) Not knowing 2) Knowing Big O and thinking it is always important 3) Knowing Big O and realizing constants matter in prac

I think there are phases to this. 1) Not knowing 2) Knowing Big O and thinking it is always important 3) Knowing Big O and realizing constants matter in practice so you stop optimizing prematurely Anyway, that was my evolution. I agree with most of what you say except I think I would change complex algorithm to complex data structure.

smabie 6y ago
In fact, with the way that modern CPUs work, big O can be very misleading, especially with small to moderate amounts of data. Performance nowadays is all about memory locality, avoiding pointers, eliminating the need for branches, etc. For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad. Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.
megameter 6y ago
There is a 4 and 5. 4) Realizing that there is a Big O around the larger architecture and thinking it is always important 5) Realizing that archecture is determined by the problem space, so addressing the problem itself as directly as possible will converge on optimal Big O Once you've done it over and over for years it becomes more clear how Big O just reflects the assumptions, and fighting it at the terminating point of the specific algorithms and data is a thing to defer until an easy win is needed. The only effort greenfield code deserves for optimization, OTOH, is to quickly review the language's built-in structures, and pick the one that is approximately best. Push the features, then as time permits build profiling mechanisms to find the hotspots as the system gets production data.
- pmiller2 6y ago
  There's a 6 as well. 6) Realizing that Big O doesn't matter when you can guarantee your data is always small. Maybe this is more like 4.1 or 5.1, but it certainly does come up.
ZephyrBlu 6y ago
I think the fetishizing of algorithms has caused a lot of people to not move out of the 2) camp.
bJGVygG7MQVF8c 6y ago
100%. in reality you're more often than not well nigh of asymptotic, so it's not always obvious what implementation is preferable. there are situations where you have a crossover in runtime between two implementations. if the n for your practical use case is less than than critical value, the asymptotically optimal solution is suboptimal.

smabie 6y ago

In fact, with the way that modern CPUs work, big O can be very misleading, especially with small to moderate amounts of data. Performance nowadays is all about memory locality, avoiding pointers, eliminating the need for branches, etc. For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad. Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.

megameter 6y ago

There is a 4 and 5. 4) Realizing that there is a Big O around the larger architecture and thinking it is always important 5) Realizing that archecture is determined by the problem space, so addressing the problem itself as directly as possible will converge on optimal Big O Once you've done it over and over for years it becomes more clear how Big O just reflects the assumptions, and fighting it at the terminating point of the specific algorithms and data is a thing to defer until an easy win is needed. The only effort greenfield code deserves for optimization, OTOH, is to quickly review the language's built-in structures, and pick the one that is approximately best. Push the features, then as time permits build profiling mechanisms to find the hotspots as the system gets production data.

pmiller2 6y ago
There's a 6 as well. 6) Realizing that Big O doesn't matter when you can guarantee your data is always small. Maybe this is more like 4.1 or 5.1, but it certainly does come up.

ZephyrBlu 6y ago

I think the fetishizing of algorithms has caused a lot of people to not move out of the 2) camp.

bJGVygG7MQVF8c 6y ago

100%. in reality you're more often than not well nigh of asymptotic, so it's not always obvious what implementation is preferable. there are situations where you have a crossover in runtime between two implementations. if the n for your practical use case is less than than critical value, the asymptotically optimal solution is suboptimal.