[Ecls-list] Hopefully some innovation..

[Juan Jose Garcia-Ripoll]

On Jan 8, 2008 6:40 AM, Brian Spilsbury <brian.spilsbury at gmail.com> wrote:
> Here we view the hash-table as a kind of list, which we can sweep around
> with the clock hand. So the hand starts at the first entry, then moves to the
> second -- the hand doesn't care about the keys.

The problem I find is that the hash is actually not ordered while the
motion of the clock has a precise sense and most of the time you end
up deleting quite recent entries when there are older ones that should
have been expired.

I have implemented an alternative algorithm, which is based on the
clock one and it is not yet committed to CVS, but seems to work
better. It is based on  a generation counter. The algorithm is of my
own cook and works as follows: compute the hash key and thus obtain a
site "i" which is associated to this element; search in the range [i,
i+10] for this element or for the site with the oldest generation
counter "k". If the element is found at position "k" < "m", it is
moved to this earlier place and "k" is returned. If the element is
found at "m" >= "k", the element is returned. If the element was not
in the hash table, we insert the new one in the site "k" and increase
the generation counter.

The number "20" is an empirical value which seems to work. The
algorithm already works better than what is implemented when the
number of methods is comparable to the size of the hash (i.e.
(make-tree 11) in the program I passed before).

If somebody has a better idea, please speak up :-)

Juanjo

-- 
Facultad de Fisicas, Universidad Complutense,
Ciudad Universitaria s/n Madrid 28040 (Spain)
http://juanjose.garciaripoll.googlepages.com