Ralf Hemmecke wrote:
>
> [[XHashTable]]
> > We should fix the issue with vacant/deleted marker
>
> Oh, then you haven't yet looked at my work from yesterday? There is no
> problem anymore, but it could be improved.
>
> I've implemented (A) (a counter that tells me when every position had
> been checked).
I am affraid that this is not good solution. Namely, before you
get every position taken by an entry or deleted marker you will
have period of time when effective load factor for insertiong
new entries is close to one. Crude estimate of runtime indicates
that average time to insert an entry will be of order of logarithm
of table size.
IMHO we should rehash if effective load factor for insertions (that
is ratio of number of occupied and deleted entires to the table
size) exceeds some fixed treshold (say 0.8 or 0.9). If load factor
is small enough (say < 0.6) then keep size, otherwise grow the table.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
