[Ecls-list] Hopefully some innovation..
brian.spilsbury at gmail.com
Sat Jan 12 10:57:28 UTC 2008
On Jan 12, 2008 6:46 PM, Juan Jose Garcia-Ripoll
<jjgarcia at users.sourceforge.net> wrote:
> 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.
Since you insert items pre-marked, this problem doesn't occur -- the hand
needs to touch the object twice without a hit.
This means that for an object to be a candidate for deletion it must
one pass, and given that this is a one bit approximation to LRU, that's as old
as you can measurably get.
More information about the ecl-devel