4 ms·

I've been a team lead and head geek for a small software company for a good number of years. I'd say that these questions matter a lot more than you'd think. U

by leonroy 10y ago

I've been a team lead and head geek for a small software company for a good number of years. I'd say that these questions matter a lot more than you'd think. Using the wrong data structure or a data structure in the wrong scenario can make the difference between an application which can serve 1000 users per node or 100. That impacts the number of servers we recommend deploying in our cluster and in turn the hardware and maintenance costs for a customer buying a license for our software. An understanding of Big-O and algos is very important and any good software eng or team lead should refresh themselves on the topics regularly since these really can make the difference between a performant app and one which brings the host device to its knees.

abstractbeliefs 10y ago
So really you're saying that actually you don't need to be able to implement these off-the-cuff, but you should understand big-O and based on the sort of data you have, pick the best algorithm from a table like this one: http://bigocheatsheet.com/ http://bigocheatsheet.com/ ?
- burntsushi 10y ago
  Eh. I wouldn't put it that way. I'd say you need enough experience to know what you don't know. Which is hard and will vary based on the problem you're trying to solve. A simple cheat sheet won't be enough.
amorphid 10y ago
Do you really use Big-O at work? I don't know if I've ever heard it brought up outside of an interview. In my experience, when something is slow, people notice and start complaining about it. "Why does it take 30 seconds to complete this seemingly simple request? Oh, it's making a database call for every element in the list, vs. efficiently sending a single request. I fixed it, and pull request submitted." "What is this script taking so long? Oh, exec is being called on every command, so let's just pull that out and put it in a wrapper script." "What performance tweak can we use to make this Rails app hellza faster, since we've maxed out low hanging fruit caching options? Rewriting this part in Elixir takes advantage of concurrency in a way that Ruby can't do all that well." I guess real world discussions don't seem to incorporate Big O lingo.
- maccard 10y ago
  Comes up fairly regularly for us in code reviews. People will question the data structures used. E.g. This find operation in a tight loop is actually called on a vector not a map, meaning it's a linear search rather than a constant operation.
- Bahamut 10y ago
  I have encountered a few situations where time complexity matters during the normal course of work. The most notable one for me was where I did two DB queries to fetch a list of elements in one and another of the same length and related to the first one - to create a list of objects from the first list, I iterated on it, and it had to do another iteration inside to find the element in the second list. It turned out this approach showed some performance problems on larger datasets, so another coworker took a look at optimizing it - he ended up grouping the second list by id in one iteration so that it eliminated the need to iterate again inside the loop, transforming it from time complexity O(n^2) to O(n). These situations don't come up too often, but when they do, it becomes important to at least be able to solve them in some fashion in a non-high pressure situation.

by leonroy 10y ago

abstractbeliefs 10y ago

So really you're saying that actually you don't need to be able to implement these off-the-cuff, but you should understand big-O and based on the sort of data you have, pick the best algorithm from a table like this one: http://bigocheatsheet.com/ http://bigocheatsheet.com/ ?

burntsushi 10y ago
Eh. I wouldn't put it that way. I'd say you need enough experience to know what you don't know. Which is hard and will vary based on the problem you're trying to solve. A simple cheat sheet won't be enough.

amorphid 10y ago

Do you really use Big-O at work? I don't know if I've ever heard it brought up outside of an interview. In my experience, when something is slow, people notice and start complaining about it. "Why does it take 30 seconds to complete this seemingly simple request? Oh, it's making a database call for every element in the list, vs. efficiently sending a single request. I fixed it, and pull request submitted." "What is this script taking so long? Oh, exec is being called on every command, so let's just pull that out and put it in a wrapper script." "What performance tweak can we use to make this Rails app hellza faster, since we've maxed out low hanging fruit caching options? Rewriting this part in Elixir takes advantage of concurrency in a way that Ruby can't do all that well." I guess real world discussions don't seem to incorporate Big O lingo.

maccard 10y ago
Comes up fairly regularly for us in code reviews. People will question the data structures used. E.g. This find operation in a tight loop is actually called on a vector not a map, meaning it's a linear search rather than a constant operation.
Bahamut 10y ago
I have encountered a few situations where time complexity matters during the normal course of work. The most notable one for me was where I did two DB queries to fetch a list of elements in one and another of the same length and related to the first one - to create a list of objects from the first list, I iterated on it, and it had to do another iteration inside to find the element in the second list. It turned out this approach showed some performance problems on larger datasets, so another coworker took a look at optimizing it - he ended up grouping the second list by id in one iteration so that it eliminated the need to iterate again inside the loop, transforming it from time complexity O(n^2) to O(n). These situations don't come up too often, but when they do, it becomes important to at least be able to solve them in some fashion in a non-high pressure situation.