This is the mail archive of the gdb@sources.redhat.com mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]