This is the mail archive of the
gdb@sources.redhat.com
mailing list for the GDB project.
Re: suggestion for dictionary representation
- From: David Carlton <carlton at math dot stanford dot edu>
- To: Daniel Berlin <dberlin at dberlin dot org>
- Cc: Daniel Jacobowitz <drow at mvista dot com>, Jim Blandy <jimb at redhat dot com>, gdb at sources dot redhat dot com
- Date: 24 Sep 2002 10:53:42 -0700
- Subject: Re: suggestion for dictionary representation
- References: <F8B4847E-CFE4-11D6-AF7A-000393575BCC@dberlin.org>
On Tue, 24 Sep 2002 13:42:18 -0400, Daniel Berlin <dberlin@dberlin.org> said:
> (Who the heck thought it would be smart to have a big Oh and little
> Oh, fer instance)
:-)
> If your average chain lengths go above log n (the number of keys
> we'd have to strcmp in the skiplist), which in fact, for large
> files, they were, then the skiplist will likely be better, because
> it'll perform less comparisons, *and* doesn't have do to the hash
> function calculation.
I'm not entirely sure I understand your assumptions in this last
paragraph; are you assuming the number of buckets will remain
constant? I think that, if we're going to use hash tables for global
symbols, we'll want to resize the hash tables as necessary. My
apologies for not making that clear; that's why I said that hash
tables were amortized O(n) rather than just O(n). (But this is, of
course, yet another way that the constant factor for hash tables could
be larger than one might like.)
> I would actually suggest neither hash tables or skiplists, but
> ternary search trees.
Thanks for the references; I'll give them a look.
David Carlton
carlton@math.stanford.edu