This is the mail archive of the
gdb@sources.redhat.com
mailing list for the GDB project.
Re: suggestion for dictionary representation
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: David Carlton <carlton at math dot stanford dot edu>
- Cc: Daniel Jacobowitz <drow at mvista dot com>,Jim Blandy <jimb at redhat dot com>, gdb at sources dot redhat dot com
- Date: Mon, 23 Sep 2002 20:34:50 -0400
- Subject: Re: suggestion for dictionary representation
I'm also curious about how it would affect the speed of reading in
symbols. Right now, that should be O(n), where n is the number of
global symbols, right?
If we used expandable hash tables, then I
think it would be amortized O(n) and with the constant factor larger.
Nope.
Our string hash function is O(N) right now (as are most). Hash tables
are only O(N) when the hash function is O(1).
Now, if you have it only hash the first x characters, you can make your
hash table O(N) again, with the x as the constant. Of course, if only
hashing the first x characters causes tons of hash conflicts, it's not
going to make your hash table very fast.
(But, I think, not larger in a way that would make a difference.) I'm
curious about how often the "amortized" bit would lead to strange
hiccups, but I don't think that's a big deal.
But for skip lists, wouldn't it be something like O(n log n)? If so,
that's an issue we have to consider.
Put it in perspective.
for 1 billion symbols, n is 29.89.
for 1 million symbols, n is 19.93.