The Joy of Look Up Tables

July 16, 1998
by Alex Zavatone

A recent discussion on the direct-l and constant heated discussions with a certain Brian Gray have brought up the topic of look up tables (LUT) -- a highly useful and performance enhancing data structure. I like to think of look up tables as those card catalogs for books in the library. Each card has the book's name and the location of the book on it. So each card actually points to the book.

Simply put, a look up table is a data structure that has a set of data stored for reference and accessed when necessary. Some examples:

Sine and Cosine values are not usually calculated in many computers but for each input value, there is a precalculated result stored as a record in a look up table. (At least that was the case at one time, I'm not so sure now).
CLUTS or Color Look Up Tables are used to establish color palettes in programs like Director.
And one which many of you may have used, a table of rect hotspots for an image map.

In many cases, using a list of precalculated values is faster than calculating the result in real time. The trade off involved is a choice between the memory space it takes to store the LUT versus the processing time it takes to calculate the value -- and in many cases, an LUT is the optimum choice. This is especially true in very complex calculations. If you're a fan of Quake like I am, you're surely aware that your computer is not able to render that entire 3D, shadowed, textured world at 30 frames a second. But for some reason, it appears to. What it is doing is taking data from a prerendered world and turning that into a textured, shadowed realistic looking environment. That's possible because the information has already been calculated and is stored in some sort of look up tables.

A LUT can be as simple as a list, though for someone new to the concept of a lookup and for ease of understanding your code, I'm a big fan of property lists. Why? Well, call me crazy but I like to understand my code when looking at it and when the name of the item preceeds the item in the list, it's a whole lot easier to understand for me. This has been quite true in several of my recent projects, where I'm either keeping track of a window, its elements, its location, its position in the window list or tracking rects in a graphic which are supposed to trigger display of an image when that area is rolled over.

For example...


set myList=["350 BC":rect(609, 0, 651, 48), "50 ¬
   AD":rect(679, 0, 733, 48), "216 AD":rect(766, 0, ¬
   797, 48),... etc]

In the list above, I don't have to know the order of the elements in the list. All I have to do to get the data for the list item at "216 AD" is getProp(myList, "216 AD"). Now if you're going to start playing with these look up tables, I'll state the obvious and let you know that you need to familiarize yourself with basic list operations, property list operations and related information.

Let's say we're going to define a look up table where the items in the list are the profit of a company for each year they've been in business since the start of the company. Like so:


set yearOfIncorporation = 1986
set corpProfitLUT = [1:-45000, 2:20000, 3:32300, ¬
  4:60040, 5:70340, ...]

and to get the corp profit for the year since the company start you'd enter:

set corpProfit = getProp(corpProfitLUT, yearSinceStart)

where yearSinceStart would be the index of elements in the list (1, 2, 3, 4, 5...)

In this case using a property list as a look up table is not necessary since the property names exactly correspond with the index of each element in the list. A linear list would make more sense like so:

set yearOfIncorporation = 1986
set corpProfitLUT = [-45000, 20000, 32300, ¬
  60040, 70340, ...]

and to get the corp profit for the year since the company start you'd enter:

set corpProfit = getAt(corpProfitLUT, yearSinceStart)

where yearSinceStart would simply be the ordered position in the list (1, 2, 3, 4, 5...)

One benefit of using a property list was mentioned to me a few years ago by JT (father of Lingo, John Thompson). A property list is faster if it is sorted. So if you do a sort(myList) and you're using a property list, the order of elements will be changed but you don't care since you're doing your lookups by using getProp which isn't affected by a change in list order. However if your list IS order dependent, don't sort it because that's sure to break your routines. Another great optimization is to use a symbol rather than a string for your property if a descriptive name is required for your property. The lookup will be several times slower if you use a string. Symbols and integers will return the fastest lookups into property lists. In the example below, accessing or adding elements to the first list will be slower by about a factor of 3


-- string properties
set myLUT = ["cat":"meow", "dog":"Bark",...] 
-- symbol properties
set myLUT = [#cat:"meow", #dog:"Bark",...]
-- integer properties 
set myLUT = [1984:"meow", 34:"Bark",...]

So what about some practical uses for lookup tables? Actually, if you check out my Z-Order articles in the Using Director archive, all the window states, window elements, z-order and window positions are maintained through lookup tables that use the keyword of the window name as the identifier. If you want to create an imagemap where you can rollover parts of an image and have different things happen depending on where the cursor is within the image, lookup tables are a great way to store the regions that are "hot". In fact, the sample movie provided shows a well documented and working example of look up tables for just that type of use in script 21. Check it out and have fun.

A sample movie demontrating the above technique is available for download in either Mac (542K) or PC (393K) format.

A Director user since 1987, Alex (Zav) Zavatone has worked on the engineering teams for both Director and Shockwave, 4, 5, 6 and 7. Recent investigations find him developing foundation classes for Director with asynchronous process management and other life threatening activities. In its early days, he had something to do with this Internet thing known as "DOUG". A noted ne'erdowell, slacker and laggard, Mr. Zavatone is nonetheless is trusted by children, small animals and the elderly. In his spare time, Mr. Zavatone rehabilitates lame desert trout.