31 October 2007

Avoid premature optimization

A lot of people who write about algorithms say that you should avoid prematurely optimizing an algorithm until you've analyzed it carefully enough that you know which parts of the algorithm are the parts that slow it down.

There are two ways to do this. The first is, of course, to go through some sort of formal analysis of the algorithm, until you notice something like "hey, I'm evaluating lots of polynomials, shouldn't I think about how I could evaluate them quickly?" And then you'd remember that polynomials can be written in a form like
((ax+b)x+c)x+d = ax^3 + bx^2 + cx + d

where the left-hand side requires three multiplications (generally, n multiplications for a polynomial of degree n) and three (generally, n) additions to be evaluated; the right-hand side requirese six (generally, n(n+1)/2 = n + (n-1) + ... + 1) multiplications and three (generally, n) additions. (This is, of course, assuming that you've forgotten what x2 is when you get to evaluating x3. You wouldn't... but a computer probably would!) Generally,

But sometimes it's easier to just step through the algorithm step by step and realize what you find yourself doing over and over again. For example, in evaluating a polynomial anxn + an-1xn-1 + ... + a1x + a0, you'd realize that when you compute xn you start by computing xn-1 and then you multiply it by x; if you did that by hand over and over again you'd eventually want to find a way to speed things up. Wouldn't it be easier if you had already stored the value of xn-1? So you'd first compute the list [1, x, x^2, ... , x^n] by just noticing that each term is x times the previous one, and then you'd multiply those by their respective coefficients ai and add those sums up. This takes 2n multiplications and n additions; it's not quite as good as the form I've given above, but the point is that just storing your intermediate results instead of recalculating them over and over again saves a lot of time. And if you don't realize this from formally analyzing the algorithm, you can realize it by just stepping through the algorithm until you get to the point where you start cursing and thinking "didn't I already do this? Why the *^%)!*!# am I doing it again?"

(By the way, this was inspired by my trying to compute the numbers of factorizations of various integers; it turns out that you want a lot of numbers of the form "the number of factorizations of n into factors at most k" and if you're not careful you can end up computing the same numbers over and over again. So I got careful.)

4 comments:

Pseudonym said...

Ye have heard it said in the past, that there are three rules of optimisation.

1. Don't.
2. (advanced) Don't yet.
3. (really advanced) Don't until you've analysed and/or instrumented your code to find out where the real bottlenecks are.

But very truly, I say unto you: There are some problems for which you need to optimise early, and for which the performance bottlenecks are known in advance Therefore:

4. (really, really advanced) If you must optimise prematurely, do it on the back of an envelope, rather than in code.

jmbr said...

You may also consider using your compiler's profiling capabilities to find (possibly unexpected) bottlenecks in your code.
Memoization is a technique that can help sometimes, too.

Anonymous said...

I was going to note, too, that this is memoization.

Anonymous said...

vimax pills - good blog friends! Post your article which is also useful for readers and to share information or experiences you have. I will visit your blog again. penis enlargement pills - http://www.male-sexual.com