guile-user
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Resizing hash tables in Guile


From: Joris van der Hoeven
Subject: Re: Resizing hash tables in Guile
Date: Thu, 13 Feb 2003 10:52:12 +0100 (MET)

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





reply via email to

[Prev in Thread] Current Thread [Next in Thread]