commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "James Strachan" <james_strac...@yahoo.co.uk>
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?

James
----- Original Message -----
From: "Michael Smith" <michael@iammichael.org>
To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
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:
>
> http://www.mail-archive.com/commons-dev%40jakarta.apache.org/msg02555.ht
> 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:
<mailto:commons-dev-unsubscribe@jakarta.apache.org>
> For additional commands, e-mail:
<mailto:commons-dev-help@jakarta.apache.org>


_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com


--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message