Boost logo

Boost Users :

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


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.

-- 
-- Marshall
Marshall Clow     Idio Software   <mailto:marshall_at_[hidden]>
It is by caffeine alone I set my mind in motion.
It is by the beans of Java that thoughts acquire speed,
the hands acquire shaking, the shaking becomes a warning.
It is by caffeine alone I set my mind in motion.

Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net