At 2:18 PM -0800 11/7/06, Marshall Clow wrote:

At 5:15 PM -0500 11/7/06, wrote:

...

There's a theorem in hash theory (proved by Komlos, one of my old profs) that says that you can always generate a perfect hash function if you know the values you need to hash. That is, you can generate a hash function that requires exactly one lookup in every case. But I don't know any compiler that actually does this. Since all cases are known at compile time, doing this should be a beneficial runtime optimization for large switches (if the generated hash function is sufficiently cheap). Maybe this could be done using the MPL? I don't know TMP well enough to know where to begin on something like this.

I remember doing this in college, in the "compiler construction" class - we had a perfect hash table for the keywords in the language that we were compiling.

Looking over my posting, I misspoke - it was another group in my class, not mine, who had the perfect hash function in their compiler. Historical Revisionism strikes again :-( -- -- Marshall Marshall Clow Idio Software mailto:marshall@idio.com Here's to parties we tossed, to the games that we lost; We will say that we won them, some day. -- Bright College Days; Tom Lehrer.

Sebastian Redl wrote:

...

doing an array lookup is O(n). Huh? Array indexing is constant time. The compiler doesn't scan the array, it uses the switch value directly as the index (after some mathematical

james.jones@firstinvestors.com wrote: transformation, perhaps.)

I think I see where the confusion came from: poor wording on my part. In step three, where I talk about "looking stuff up" in the arrays, I meant to say the array is indexed by the stuff, not that the runtime must search for it. The lookup, in this case, is a simple indexing operation, and is often implemented in one or two machine instructions.