Guile Mailing List Archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Scheme style auto-resizing hashtable
On Fri, 23 Oct 1998, Jay Glascoe wrote:
> I've found that the expected maximum bucket size seems to be related to
> log(number-entries). I can't prove that, but I am currently modifying
> max-bucket-size to grow at this rate and it does seems to work well.
> My current tests use a big file filled with unique, and very large, random
> numbers. But still, the bigger the hashtable, the bigger the expected
> largest bucket size (relative to average bucket size).
in my resize function, I have
if (imax_bucket_size < log_inumber_entries)
imax_bucket_size = (int)floor(log_inumber_entries + 0.5);
max_bucket_size = SCM_MAKINUM(imax_bucket_size);
which gives fantastic performance. For large hashes (~100,000 entries),
I'm actually out-pacing the Python-style dictionaries. (Which are opaque,
all the book-keeping is kept in a C struct, whereas my hash tables are
constantly convert numbers back and forth between C and Scheme).
Guile Home |
Main Index |