Re: Resizing hash tables in Guile

[Joris van der Hoeven <TeXmacs@math.u-psud.fr>]

> > I've been thinking that maybe we should continue the move and let the
> > resizing tables entirely replace the fixed size ones.  It seems a
> > little silly to have to explain to Guile users that there are two
> > (sorry, eight) different kinds of hash tables...  Also, I think the
> > opacity of the resizing table objects is an advantage rather than a
> > disadvantage.  If they are opaque, we can any time modify the
> > underlying implementation (the well-known data abstraction argument).
> > 
> > What do you say?
> 
> I think that this is a a good idea, but I would like the optional size
> argument to still be there as an initial guess about the number of
> items to expect to avoid resizing and to optimize performance when
> we have advance information about how many items to expect.

In fact, it is even better to specify the resizing behaviour
using optional arguments. For instance:

	up-ratio   : size up when size/slots >= up-ratio
	up-factor  : new nr slots := old nr slots * up-factor
	down-ratio : size up when size/slots < down-ratio
	down-factor: new nr slots := old nr slots / down-factor

Using a small up-ratio will improve the constant factor in the lookup speed,
but require the usage of a larger number of slots.

> Of course this additional level of abstraction is nice as it also gives
> a future option to use trees if the user e.g gives an optional
> comparision operator.

Yes.

> By the way, Joris van der Hoeven mentioned that this type of resizing
> hash tables are faster than trees, which have a time complexity
> of O(log n)+reshuffling time if they are balanced. Do you have any
> numbers showing how much faster and if possible if there are any
> conditions? The reshuffling time will grow at least O(n) when the
> size of our linear tables increases if I have understood right.

Well: lookup time in a balanced search tree is O(log n),
while lookup time in a table is O(1)...



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user