A typical story is definitely a good story.

Analyse your code in different parts -> find which part cost most of the time -> optimize the slowest part(s) instead of some other detailed part -> analyse again to make sure it works.

Back up your code before you Modify it. LoL

9.2 A First Aid Sample

One. Change from modulus to subtraction.

A one line optimization. Change mod to sub.

When we are using circular queue data structure in some searching algorithm. (e.g. SPFA) This unlike-taken branch is more effective than modulus operation.

Two. Use macro.

I am not very familiar with macro… I know macro is widely used by some Vietnamese in their codes. It’s like operator overriding. They make their cpp code as simple as a python code! WTF…

But in these column, you see the dangerous of using macro. I insist my opinion here… No much comment.

Three. For loop.

It is sequential search. But the most important part is the for loop right?

A typical for loop in C programming language is:

for (init; end condition; step) {;}

The end condition is usually a comparison.

How could you decrease the number of comparison in the code?

Try to think about the for loop.

Another thing for for loop is unrolling. I don’t like this kind of code… It’s ugly. Even though it is efficient, I might not like to employ this strategy.

Four. Change to another representation.

I write a question in the end of : Programming Pearls Clmn 7

So how could you solve the bad cell？

A good way of representation is mark the bad cell to -Maxint. Then you can do the maximum sub-matrix like there is no bad ones. Because you will never take -Maxint as part of your solution. (not exactily never, likely to be never)

This is another example of changing representation of solving a problem in a faster way.

9.3 Major Surgery — Binary Search

I never thought about how to make a binary search faster. I thought it was already fast enough.

This section makes great sense to me.

1. reduce comparison
2. Quantize the size into 2^n
3. Unrolling

The most common optimization is part 1. The most brilliant one is part 2. The most frenzied one is definitely the last one…

Part 2 reduce the overhead of modulus operations. But this make the code more error-prone.

Part 3… LoL… Hehe…

The problems given in this chapter are either easy or very hard to understand the question itself…

I am Lan Duo to write all these question down.

Haha… Nice reading. ^_^