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" <[EMAIL PROTECTED]> To: "Jakarta Commons Developers List" <[EMAIL PROTECTED]> 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:[EMAIL PROTECTED]> > For additional commands, e-mail: <mailto:[EMAIL PROTECTED]> _________________________________________________________ Do You Yahoo!? Get your free @yahoo.com address at http://mail.yahoo.com -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
