You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Michael Smith <mi...@iammichael.org> on 2002/02/03 17:31:16 UTC
[collections][PATCH] LRUMap - license, docs update
Fixes in this patch:
- 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
Index:
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa
che/commons/collections/LRUMap.java
===================================================================
RCS file:
/home/cvspublic/jakarta-commons/collections/src/java/org/apache/commons/
collections/LRUMap.java,v
retrieving revision 1.1
diff -u -r1.1 LRUMap.java
---
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa
che/commons/collections/LRUMap.java 6 May 2001 11:04:25 -0000 1.1
+++
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa
che/commons/collections/LRUMap.java 3 Feb 2002 16:19:31 -0000
@@ -1,9 +1,62 @@
/*
- * Copyright (C) The Apache Software Foundation. All rights reserved.
+ * $Header: $
+ * $Revision: $
+ * $Date: $
+ *
+ *
====================================================================
+ *
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 2001-2002 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * 3. The end-user documentation included with the redistribution, if
+ * any, must include the following acknowlegement:
+ * "This product includes software developed by the
+ * Apache Software Foundation (http://www.apache.org/)."
+ * Alternately, this acknowlegement may appear in the software
itself,
+ * if and wherever such third-party acknowlegements normally
appear.
+ *
+ * 4. The names "The Jakarta Project", "Commons", and "Apache Software
+ * Foundation" must not be used to endorse or promote products
derived
+ * from this software without prior written permission. For written
+ * permission, please contact apache@apache.org.
+ *
+ * 5. Products derived from this software may not be called "Apache"
+ * nor may "Apache" appear in their names without prior written
+ * permission of the Apache Group.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
====================================================================
+ *
+ * This software consists of voluntary contributions made by many
+ * individuals on behalf of the Apache Software Foundation. For more
+ * information on the Apache Software Foundation, please see
+ * <http://www.apache.org/>.
*
- * This software is published under the terms of the Apache Software
License
- * version 1.1, a copy of which has been included with this
distribution in
- * the LICENSE file.
*/
package org.apache.commons.collections;
@@ -27,12 +80,50 @@
* </p>
*
* <p>
- * <b>WARNING</b> the values() and entrySet() methods require
optimisation
- * like the standard {@link HashMap} implementations so that
iteration
- * over this Map is efficient.
+ * <p>Warning</p>: This class is not a true "Least Recently Used"
map. When
+ * mappings are accessed, the mapping is moved one position away from
the end
+ * of the list, rather than all the way to the front of the list.
This means
+ * that the "most" recently used, is not at the front of the list,
and the
+ * "least" recently used is not necessarily at the end of the list.
Here's a
+ * simple example (Provided by Aaron Smuts on commons-dev@):
+ *
+ * <pre>
+ * Say that items 0 - 9 are put in. The limit is 10.
+ *
+ * The list looks like:
+ *
+ * Index order (0-9)
+ * 9,8,7,6,5,4,3,2,1,0
+ *
+ * Item 1 is accessed and the list now looks like:
+ * Index order (0-9)
+ * 9,8,7,6,5,4,3,1,2,0
+ *
+ * Item 0 is accessed and the list now looks like:
+ * Index order (0-9)
+ * 9,8,7,6,5,4,3,1,0,2
+ *
+ * Item 2 is accessed and the list now looks like:
+ * Index order (0-9)
+ * 9,8,7,6,5,4,3,1,2,0
+ *
+ * Item 10 is added and the list now looks like
+ * Index order (0-9)
+ * 10,9,8,7,6,5,4,3,1,2
+ *
+ * Item 0 was droped but it was not the least recently used
element.
+ * </pre>
* </p>
+ * <p>
+ * Additionally, the results from entrySet() and values() are not
properly
+ * backed by the map in violation of the Map API contract. These
methods
+ * are also not implemented efficiently.</li>
+ * </ul>
+ * </p>
+ *
+ * <p>These issues hopefully will be corrected at a later date.</p>
*
- * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
+ * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
*/
public class LRUMap extends HashMap implements Externalizable {