commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "James Strachan" <>
Subject Re: [collections][PATCH] LRUMap - license, docs update
Date Sun, 10 Feb 2002 08:16:34 GMT
Applied. Thanks Michael.

I've also been pondering a solution to the LRU issue that preserves the
efficiency of the bubble list (and avoids expensive tree or count-indexing
data structuers) but solves the problem that Aaron found. Still not had any
bright ideas yet :-(

Maybe renaming it to FastLRUMap that approximates LRU but isn't totally
accurate in all circumstances might help?

----- Original Message -----
From: "Michael Smith" <>
To: "Jakarta Commons Developers List" <>
Sent: Sunday, February 10, 2002 5:53 AM
Subject: [collections][PATCH] LRUMap - license, docs update

> Changed license to proper long form.
> Added warnings to class documenation about the problems the class has.
> FYI:
> I plan on revisiting this class to address the following problems (I
> documentated these in the patch so users of the class are also aware the
> problem exists):
>  - LRU algorithm is not actually "least recently used".  The idea of
> moving an
> entry only slightly further from the "drop zone" rather than all the way
> to the
> beginning is interesting, but it is not "least recently used".  See
> example
> case exhibiting a flaw in the implementation in this email from Aaron
> Smuts:
> ml
> The approach in LRUMap may have been at attempt at a "most used" where
> the most
> used element is at the front of the list, but it fails to do that as
> well.  An
> alternative data structure that may be interesting to implement woud be
> a splay
> tree, which attempts to keep freqeuently accessed items at the top of
> the tree,
> while less frequent items are at the bottom of the tree.   Another
> alternative
> would be to use a heap, with priorities based on the account count.
> Both the
> splay tree and heap would operate more slowly than a HashMap though
> (splay
> trees and heaps have inherant O(log n) runtime for some operations.
>  - To fix the above problem, the "Bubble List" probably won't exist, but
> if for
> some reason it still does, it appears as though things will break if you
> remove
> an item.  remove(Object) removes the item from the map, but not the
> bubble
> list.
>  - The results from entrySet() and values() are not properly backed by
> the map
> in violation of the Map API contract.  Removes from the returned
> structures are
> not reflected in he overall Map.
> I didn't do a full review on this though, so there may be other items I
> might
> want to address.
> Regards,
> michael


> --
> To unsubscribe, e-mail:
> For additional commands, e-mail:

Do You Yahoo!?
Get your free address at

To unsubscribe, e-mail:   <>
For additional commands, e-mail: <>

View raw message