Re: suggestion for dictionary representation

Daniel Jacobowitz
2002-09-24T01:39:40Z

On Mon, Sep 23, 2002 at 08:34:50PM -0400, Daniel Berlin wrote:
> >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.

Wait a second... aren't you switching N's on us? N is the number of
global symbols. We're talking about the total time of adding all
symbols to the table. Hashing a string is "effectively" constant time,
because all string lengths are "small".

> >(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.

You mean "log n", of course.

--
Daniel Jacobowitz
MontaVista Software Debian GNU/Linux Developer