4 ms·
It seems like it is very simple to me: You should always code with your performance requirements in mind. But you shouldn't do detailed optimization until you
by colomon 15y ago
It seems like it is very simple to me: You should always code with your performance requirements in mind. But you shouldn't do detailed optimization until you have some sort of profiling feedback.
You have to do your basic coding with your performance requirements in mind, because it is all too easy to come up with code that can never meet your performance requirements, no matter how much you profile and optimize it.
Case in point: http://strangelyconsistent.org/blog/p1-best-way-to-multiply-a-chain-of-matrices http://strangelyconsistent.org/blog/p1-best-way-to-multiply-... . My solution (http://strangelyconsistent.org/p6cc2010/p1-colomon/ http://strangelyconsistent.org/p6cc2010/p1-colomon/) was quite elegant, IMO, setting up things so I simply generated all the all the possible solutions, and then took the min with respect to the number of multiplications.
But it was also appallingly inefficient. Generating all the possible solutions is completely the wrong approach, and no amount of optimizations to my algorithm would ever be sufficiently efficient for non-trivial problems. The only possible approach is to start over from scratch: http://strangelyconsistent.org/p6cc2010/p1-moritz/ http://strangelyconsistent.org/p6cc2010/p1-moritz/
So if I had properly considering my performance requirements, I would have come up with a much better solution. (Or just failed: dynamic programming is not really in my programming toolbox. I need to get around to remedying that!) But at the same time, worrying about how to most efficiently represent my Ordering object would have been completely pointless.
That's what "avoid premature optimization" means, IMO. It's not an excuse ignore performance. It's about not sweating the small details until you're certain they're important.
- abecedarius 15y agoI only glanced at this, but usually when a recursive solution can be improved upon by dynamic programming, you can make a comparable improvement by memoizing instead, without needing a full rewrite. In this case using stacks instead of recursion appears to have gotten in the way of that and might count as premature optimization. (I might be completely barking up the wrong tree as far as your particular code goes, again, but code described as generating all possible solutions could be made efficient without much change.) For example, the memoized word-splitting code at http://norvig.com/ngrams/ http://norvig.com/ngrams/ compared to the recent discussion here on HN of doing it with dynamic programming (as an interview problem).
- colomon 15y agoI don't think it would have helped here. The problem is that the code actually goes through the entire massive list of possibilities to determine the best result, and that list will rapidly get too long to be practical no matter how fast the rest of the code is. Memoizing might win back some performance, but it won't alter that fundamental issue.