commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Smith" <mich...@iammichael.org>
Subject [collections][PATCH] LRUMap - license, docs update
Date Sun, 10 Feb 2002 05:53:35 GMT
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

Mime
View raw message