Re: [Boost-users] Sequence of Types, What For?

From: Marshall Clow (marshall_at_[hidden])
Date: 2006-11-07 17:22:36

At 2:18 PM -0800 11/7/06, Marshall Clow wrote:
>At 5:15 PM -0500 11/7/06, <james.jones_at_[hidden]> 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_at_[hidden]>
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.