Re: Switch statement code generation
Ira Baxter
> nathan....@gmail.com wrote:
>
> > On Nov 5, 12:12 pm, Walter Banks <wal...@bytecraft.com> wrote:
> >> Joshua Cranmer wrote:
> >> > I'm trying to put together a list of various methods to do code
> >> > generate for switch statements. ...
> >
> > Has anyone seen tries used for the string-based switch statements?
>
> I think the winner for string switches is a string representation with
> a precomputed hash code, used in combination with a hashtable of
> jump addresses.
I'm surprised nobody mentioned perfect hashing. This is ideal
when the set of values is known in advance. No rehashing.
(I'll put this in my ToTry list for our parlanse compiler :)
-- IDB
[I gather that finding a perfect hash function that runs quickly is
not always easy, and that a slightly imperfect hash, e.g., into a
hash table with no collisions but a few empty slots can often be
a lot faster. -John]
Pertti Kellomaki
> [I gather that finding a perfect hash function that runs quickly is
> not always easy, and that a slightly imperfect hash, e.g., into a
> hash table with no collisions but a few empty slots can often be
> a lot faster. -John]
Is there a technical term for such slightly imperfect hashes?
Mathematically it would be an injection I suppose, but I have
not seen that term used in connection with hashing.
--
Pertti
Hans Aberg
The Wikipedia perfect hash function page says this is the definition of
a perfect hash function. It is called a minimal perfect function if the
image is an interval.
It also mentions some libraries implementing minimal perfect hash functions:
http://cmph.sourceforge.net/
http://sux4j.dsi.unimi.it/
The latter also implements monotone minimal perfect hash functions, that
is, the order of the keys are preserved.
Hans