[self-interest] embedding based prototype languages
Steve Dekorte
steve at dekorte.com
Thu Nov 7 06:24:57 UTC 2002
On Wednesday, November 6, 2002, at 07:30 PM, James McCartney wrote:
>> A perfect hash would take care of that(I use them in Io)
> I'm not really sure that the perfect hash as you have implemented them
> really buys you anything. You use a prime sized table and the %
> operator
Actually, I don't use a prime size table. The table grows by one until
the hash is perfect, so it can be any size above the minimum.
> instead of using a power of two sized table and masking.
Memory usage may be a problem there. The important bit about getting a
small perfect hash is having a lot of sizes to try out (because the
chance of any given small size working is small). There aren't many
powers of 2 before you get big numbers.
> Mod % is a pretty slow operation.
That's true.
> In the time it takes to do the % operation
> you could probably have chained along once. With a 0.5 load factor and
> separate chaining, the average chain length is 1.27 . So I'd think that
> your perfect hash is not really winning on performance, but is losing
> big on space.
I've found it doesn't take much space as long as the number of slots is
low(which is typical when using differential inheritance).
But I'd certainly like to move to another technique if it's better.
I'll run a memory&speed comparison if you send me a piece of your
sample code(just the hash code) and post the results.
Cheers,
Steve
OSX freeware and shareware: http://www.dekorte.com/downloads.html
More information about the Self-interest
mailing list