[Top][All Lists]
[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)...
- Re: Resizing hash tables in Guile, (continued)
- Re: Resizing hash tables in Guile, Marius Vollmer, 2003/02/12
- Re: Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/12
- Re: Resizing hash tables in Guile, Roland Orre, 2003/02/12
- Re: Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/13
- Re: Resizing hash tables in Guile, Harvey J. Stein, 2003/02/13
- Re: Resizing hash tables in Guile, Joris van der Hoeven, 2003/02/13
- Re: Resizing hash tables in Guile, Harvey J. Stein, 2003/02/13
- Re: Resizing hash tables in Guile, Paul Jarc, 2003/02/13
- Re: Resizing hash tables in Guile,
Joris van der Hoeven <=
- Re: Resizing hash tables in Guile, Rob Browning, 2003/02/12