3 ms·
Then again, thing's aren't in the critical path until suddenly they are. Regardless of scenario I will never willingly do a O(n^2) sort when writing new code.
by magicalhippo 4y ago
Then again, thing's aren't in the critical path until suddenly they are.
Regardless of scenario I will never willingly do a O(n^2) sort when writing new code. Just in case those 10 items suddenly turn to 10000 one day.
- joaonmatos 4y agoAre you even manually implementing sorts frequently? Even languages that are notorious for having tiny libraries, like C and JS, have built-in sorts.
- mattgreenrocks 4y agoIt’s less about accidentally writing n^2 sorts and more about not accidentally creating n^2 algorithms.
- whstl 4y agoNot sorting, but very simple algorithms that can't afford having O(n^2) performance? That's common even in CRUD apps.
- dagw 4y agoPerhaps not sort so much, but certainly with search I've seen people roll their own inefficient search functions many times.
- joaonmatos 4y agoIt is the exact same situation, though. Most people can just chain a sort and a binary search to do it, and both are included in most languages. Or just put it into a tree map, if your language has it.
- bcrosby95 4y agoThe moon doesn't fall into the ocean until it does.
- TeMPOraL 4y agoNot a fair comparison :P. The point is that the developers may think O(n^2) is fine because their toy use cases had n=10...100, but then actual users will try to use the software for n=10k, or n=100k, and then either waste their lives working with suddenly slow software, or look for alternatives. I walked into a case like this the other day. I wanted to do a little semi-collaborative project planning. I found a nice tool, played with it for a moment, figured it has the functionality I need and it's fast enough. Then decided to do the actual plan. Once the number of entries in the system went from 10-20 to 30-40, I started to feel things get a little laggy. 50-60, more laggy. At this point I was committed, so I suffered the tool for couple of months, as its UI kept breaking when handling 100 entries. If I knew this would happen at the start, I'd look for something else. But instead, I walked into a hidden O(n^2) somewhere, that makes me hate the product with a passion now.
- deleted 4y ago[deleted]
- chenglou 4y agoIt's more than that. The way black box composition is done in modern software, your n=100 code (say, a component) gets reused into a another thing somewhere above, and now you're being iterated through m=100 times. Oops, now n=10k Generally, Casey seems to preach holistic thinking, finding the right mental model and just write the most straightforward code (which is harder than it looks; people get distracted in the gigantic state space of solutions all the time). However this requires 1. a small team of 2. good engineers. Folks argue that this isn't always feasible, which is true, but the point of these presentations is to spread the coding patterns & knowledge to train the next gen of engineers to be more aware of these issues and work toward said smaller team & better engineers direction, knowing that we might never reach it. Most modern patterns (and org structures) don't incentivize these 2 qualities.
- Akronymus 4y ago> The way black box composition is done in modern software, your n=100 code (say, a component) gets reused into a another thing somewhere above, and now you're being iterated through m=100 times. Oops, now n=10k That doesn't seem quite right. as 100 * (100^2) <<<<< 10000^2
- cturner 4y ago"Regardless of scenario" limit your options. If you are shipping a binary to your users that will never be able to get updates, your cautiousness would be justified. There are other situations where it will needlessly limits options. There are situations where I have knowingly written O(n^2) or worse, and put a # xxx dragons marker by it. Quick to write, leave my options open, keep my momentum on the problem I care about. I will grep for xxx issues at some later time. I may end up throwing out the code before that happens. If I hit big-o issues before then, I can refactor. I once had a system where the important problems turned out to be a series of IO bottle-necks - nothing to do with computation - but that was obscured because good sense had been burnt at the altar of compute efficiency.