Subscribe to 10 GOTO 10        RSS Feed
***** 2 Votes

Beginner Series: Lookup Table

Icon 3 Comments
Lookup Tables



a very common pattern in programming is converting a number into some enumerated string. Like converting 1 into January, 2 into February etc. -- these kinds of problems are often done with switch statements like so:

#include <iostream>

using namespace std;

const char* getMonth(int monthNum);

int main() {
    
    cout << getMonth(9) << endl;
    return 0;
}


const char* getMonth(int monthNum) {
    switch(monthNum) {
        case 1: {
            return "January";
        }
        case 2: {
            return "February";
        }
        case 3: {
            return "March";
        }
        case 4: {
            return "April";
        }
        case 5: {
            return "May";
        }
        case 6: {
            return "June";
        }
        case 7: {
            return "July";
        }
        case 8: {
            return "August";
        }
        case 9: {
            return "September";
        }
        case 10: {
            return "October";
        }
        case 11: {
            return "November";
        }
        case 12: {
            return "December";
        }
        default:
            return "";
    }
}


When we look at the assembly language produces[1] we find a structure called a "jump table" which is basically this: The compiler makes an array filled with offsets to code for each block, then it loads an address from the array based upon the monthnum.

Switch statements that use this jump-table are much more efficient than if-else if-else if...else blocks - not ALL switch statements become jump tables (and some compilers an make if-else if... block into jump tables) because the compiler does not have to check the individual cases. Now I am not going to go into how to properly build switch statements to form efficient jump tables, or how to program your own jump tables -- Rather I want to talk about using the idea of an array to replace the switch-statement all together.

There really is no need for the switch statement here. Lets replace the switch statement with an array that converts the number (our index) the a string (or element):

#include <iostream>

using namespace std;

const char* MonthTable[] = {
    "January",
    "February",
    "March",
    "April",
    "May",
    "June",
    "July",
    "August",
    "September",
    "October",
    "November",
    "December",
};

const char* getMonth(int monthNum);

int main() {
    
    cout << getMonth(9) << endl;
    return 0;
}


const char* getMonth(unsigned int monthNum) {
    monthNum--;
    if (monthNum < sizeof(MonthTable)/sizeof(const char*)) {
        return MonthTable[monthNum];
    }
    return "";
}


so now we have an array of month names, and we take the number subtract 1 which brings us into the range of our array index values and then we check bounds and return the string from the table.

Is this more efficient? Definitely so in terms of space. Possibly in terms of performance. However the code is also compact and easily parsed with the eye. If we take out the concerns for bounds (i.e. if we KNOW that our monthnum actually corresponds to a month) we can even ditch the function and just use: MonthTable[monthNum].

So the idea of a lookup table is that we put data into a table and then access it via some index. Some examples:

Floating point operation such as sin and cos can be costly, even more so if we need to convert to and from radians to degrees. So if your program uses sin/cos a good deal you can simply fill out an array of 359 values and look up the sin/cos that you want:
#include <iostream>
#include <cmath>

using namespace std;


class QuickSinCos {
    double CosTable[360];
    double deg2rad;
    public:
    QuickSinCos() {
        deg2rad = 4 * atan(1.0)/180.0;
        for (int i = 0; i < 360; ++i) {
            CosTable[i] = cos(i * deg2rad);
        }
    }
    
    inline double Cos(int deg) {
        if (deg < 0) { deg = (deg % 360) + 360; }
        else {deg = deg % 360; }
        return CosTable[deg];
    }
    
    inline double Sin(unsigned int deg) {
        deg = deg - 90;
        return Cos(deg);
    }
};


int main() {
    QuickSinCos qsc;
    char buffer[41];
    int sinv = 0, cosv = 0;
    
    //fill buffer with 40 spaces
    for (int i = 0; i < 40; ++i) {
        buffer[i] = 0x20;
    }
    buffer[40] = 0x00; // add terminating zero
    
    for (int angle = 0; angle < 360; angle++) {
        //reset the buffer
        buffer[sinv] = 0x20;
        buffer[cosv] = 0x20;
        //buffer[20] = '|';
        sinv = 19*qsc.Sin(angle*8) + 20;
        cosv = 19*qsc.Cos(angle*8) + 20;
        buffer[sinv] = '*';
        buffer[cosv] = '+';
        cout << buffer << endl;
    };
    cout.flush();
    return 0;
}


(note that modern math coprocessors can calculate these values very quickly (may even use their own lookup tables) and so this may not be necessary anymore).

Lookup tables can be used to save results previously calculated. This can be a big help in recursive algorithms that may calculate the same sub value multiple times.

The idea of a lookup table in this respect is much like caching. Once a time consuming process has been done once, there is no real need to redo the process if you know the results will be the same. Simple store the results and retrieve them when needed again. For example a web server may cache pages generated from Database lookups to avoid the overhead of having to ask the database the same question, get the same answer and generate the same page over and over.

One of the trickier parts of lookup tables (and generating good switch cases) is finding a way to map the possible input values into a set of number 0 - n. So if you find yourself writing a switch statement to convert your input into an index -- maybe you are better off not using a lookup table and just using a switch statement.

3 Comments On This Entry

Page 1 of 1

nmeans73 Icon

02 April 2011 - 12:53 PM

Quote

Lookup tables can be used to save results previously calculated. This can be a big help in recursive algorithms that may calculate the same sub value multiple times.


Would this create a tail recursive function? If so, you may not see any increase in efficiency depending on if your compiler supports tail-call optimization.
0

NickDMax Icon

04 April 2011 - 12:31 PM

Quote

Would this create a tail recursive function?
-- not at all. Lets say I am calculating a factorial. Now the first factorial I need is 10! -- so I have to calculate 9! and multiply that by 10 -- but I also store the result in a table. To calculate 9! I need 8! etc... So by the time I get to 10! I have added 1!, 2!, 3!, 4!, 5!, 6!, 7!, 8!, 9!, and 10! to my lookup table. Did having the lookup table do anything for me? No! It probably slowed me down! Yuck!

Next I need to calculate 5! -- well now rather than having to calculate 4!, 3! etc. I just grab the value from the table. Time to process O(1). Did the lookup table help? YES!

Next I need to calculate 11! -- here the lookup table does a little for me, I lets me start with 10! and then just multiply by 11. So it "caches" previous results so that I don't have to "recalculate".

There are times when this is not a benefit. You have to be sure that you are going to be reusing the values stored in the table.
0

nmeans73 Icon

04 April 2011 - 02:24 PM
I see. So it really is a question the number of uses of a recursive function and whether storing the data is worth the increase in time it gives you to use the function. I guess it isn't tail recursive at all and is in fact even better because it's O(1) as opposed to the tail recursive function which would be optimized into an iterative process.

I just enjoy bringing up tail recursion every time i see someone mention recursion. Programming in Lisp will do that to you. :)
0
Page 1 of 1

October 2014

S M T W T F S
   1234
567891011
12131415161718
1920 21 22232425
262728293031 

Recent Entries

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)