
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.