Simple C++ Coding Exercise – Use Lookup Table to Eliminate the Condition Checks



There is a popular IQ question, e.g. according to the first few number patterns, find the answer to the input:

1234 = 0
4567 = 1
2345 = 0
1290 = 2
8811 = 4
6561 = 2
1980 = ?

The answer is to count the number of circles. The only digits that have circles are 0, 6, 8 and 9 while the number 8 has two circles. One can write a C++ function to sum up the circles quickly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// helloacm.com
int CountCircles0(int n) {
    int r = 0;
    while (n > 0) {
        switch (n % 10) {
            case 8: r += 2; break; // edited:  before was r ++; // without break
            case 0:
            case 6:
            case 9: r ++; break;
        }
        n /= 10;
    }
    return r;
}
// helloacm.com
int CountCircles0(int n) {
    int r = 0;
    while (n > 0) {
        switch (n % 10) {
            case 8: r += 2; break; // edited:  before was r ++; // without break
            case 0:
            case 6:
            case 9: r ++; break;
        }
        n /= 10;
    }
    return r;
}

Now, the switch is essentially a condition checks while some compilers are cleverer enough to optimise this into lookup tables. However, you can help compilers to optimise this manually by writing a much better and concise code.

1
2
3
4
5
6
7
8
9
10
11
// helloacm.com
int CountCircles1(int n) {
    int r = 0;
    // lookup tables
    const int x[] = {1, 0, 0, 0, 0, 0, 1, 0, 2, 1};
    while (n > 0) {
        r += x[n % 10];
        n /= 10;
    }
    return r;
}
// helloacm.com
int CountCircles1(int n) {
    int r = 0;
    // lookup tables
    const int x[] = {1, 0, 0, 0, 0, 0, 1, 0, 2, 1};
    while (n > 0) {
        r += x[n % 10];
        n /= 10;
    }
    return r;
}

Under GNU C++ compiler 4.9.1, the running time of the optimised version is approximately half as the naive version (uses switch). Both are compiled and tested at RELEASE under codeblocks.

So, the point made here is not to rely on compilers even it looks a very simple task.

Featured Comments

Things are not so obvious. There’s a lot of case where generated code is faster (with the appropriate flags) but when you try to do clever things on your code you break compiler’s heuristics and prevent further optimization.

In the example described in the article, to obtain similar performances, you should probably transform the case for 8 with a “r += 2; break;” otherwise there’s no reason to produce a lookup table.

Bad advice in the time it took you to figure out how to do it yourself you could have earned enough cash as a contractor to buy a faster processor

Good advice.. unless it’s .NET.

It’s retarded to expect code optimization from a compiler. Any programmer should write clean and smart code in order to achieve perfect results.

As long as we’re talking about hot code I can agree with the statement. If this is interrupt code or something running in a tight loop then there might be merit in hand-optimizing. For the overwhelming majority of code it’s a complete waste. Optimizing code that needs frequent maintenance and update just increases cost. Programmers aren’t cheap and hiring ASM programmers to maintain an application that could just as well have been written in Python is a sure fire way to bankrupt the company with no product delivered. Worse still there’s no chance to redeem since very few would be able to understand the resulting code and you’ll have a real hard time hiring to fix it up.

The only magic bullet you need to know: “There are no magic bullets.”

Course, but if you are paid by the hour some employers won’t tolerate extended obsessive navel gazing and would prefer you turn optimisation on. Or if for personal profit your long suffering other half might be awake by the time you come home to bed and reward you with hot sex. It’s three keystrokes on a makefile.

What you shown is applicable for some scenarios only, but as the compilers are designed to do code native optimization also. If we think over and write the code in the way that u shown. We are stopping the compilers native optimization. All predefined way of the logics are well optimized in the compiler, the only thing I’d we have to use it properly.: P

–EOF (Coding For Speed) —

GD Star Rating
loading...
669 words Last Post: C++ Coding Example, Using Hash Algorithm to Remove Duplicate Number by O(n)
Next Post: Ahmdal's Law

The Permanent URL is: Simple C++ Coding Exercise – Use Lookup Table to Eliminate the Condition Checks (AMP Version)

3 Comments

Leave a Reply