--------Ursprungligt meddelande-----
Fr�n: Greg Nudelman [mailto:[EMAIL PROTECTED]
Skickat: den 13 november 2003 02:07
Till: jdjlist
�mne: [jdjlist] LFUCache problemDear All:
I'm trying to create a cache that sorts elements by the number of times
accessed and then FIFO by order added. Simple right? :-)
However, I can't make this TreeMap work correctly. I overrode hashCode,
equals, and compare, (in about 5 different ways so far) and still I'm
getting elments out of order. Right now it sorts this collection of keys
as D, C, B, A. I think the problem may be with the way I overrode hashCode
-- any ideas there? Do I need to call any special sort() before I call the
iterator?? Does anyone have a good example of how to use the TreeMap with
non-Java-native objects (i.e. NOT Strings, Integers, etc.) as keys? This is
my first encounter with this Class and I must say that it pretty much *sucks
gas*. I've spent a few hours already on this "little" project, when I
thought it would be about a 30 min job...
Go figure. Any help (or blatant scolding) is welcome.
Greg (...who thinks that he should get some new hobbies)
import java.util.*;
import java.text.*;public class LFUCache {
private long addCounter;
private long getSuccessfulCounter;
private int maxSize;
private int currentSize;
private Hashtable cache;private static final String DUD = "DUD";
private class Container {
Comparable key;
Object item;
int size;
int useFrequency;
long addCount;
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj instanceof Container) {
Container c1 = (Container)obj;
if(useFrequency == c1.useFrequency &&
addCount == c1.addCount &&
(key).equals(c1.key))
return true;
}return false;
}public int hashCode() {
return (int)(useFrequency * 31 + addCount * 17 + key.hashCode());
}
public String toString() {
return new StringBuffer()
.append("\nContainer {")
.append("key=")
.append(key)
.append("; size=")
.append(size)
.append("; useFrequency=")
.append(useFrequency)
.append("; addCount=")
.append(addCount)
.append("; item=")
.append(item)
.append("}\n")
.toString();
}
}private TreeMap order;
public LFUCache(int maxSize) {
this.maxSize = maxSize;
clear();
}public synchronized int getSize() {
return currentSize;
}public synchronized int getMaxSize() {
return maxSize;
}public synchronized void add(Comparable key, Object item) {
add(key, item , 1);
}
public synchronized void add(Comparable key, Object item, int size) {remove(key);
while (currentSize + size > maxSize) {
if (!deleteLFU()) {
break;
}
}
if (currentSize + size > maxSize)
// Just not enough room: can't cache an item this big
return;
Container container = new Container();
container.key = key;
container.addCount = this.addCounter;
container.item = item;
container.size = size;order.put(container, DUD);
cache.put(key, container);this.addCounter++;
currentSize += size;
}public synchronized Object get(Comparable key) {
Container container = (Container)cache.get(key);
if (container == null)
return null;this.getSuccessfulCounter++;
container.useFrequency++;
return container.item;
}
public synchronized Object remove(Comparable key) {
Container container = (Container)cache.remove(key);
if (null == container)
return null;currentSize -= container.size;
order.remove(container);
return container.item;
}public synchronized void clear() {
cache = new Hashtable(this.maxSize);
order = new TreeMap(
new Comparator() {public int compare(Object o1, Object o2) {
Container c1 = (Container)o1;
Container c2 = (Container)o2;
int index = c1.useFrequency - c2.useFrequency;
if(index > 0) {
return 1;
} else if(index < 0) {
return -1;
}long index2 = c1.addCount - c2.addCount;
if(index2 > 0) {
return 1;
} else if(index2 < 0) {
return -1;
}return (c1.key).compareTo(c2.key);
}
});
currentSize = 0;
}private boolean deleteLFU() {
Container container = (Container)order.firstKey();if(null == container)
return false;currentSize -= container.size;
cache.remove(container.key);
order.remove(container);return true;
}public synchronized String toString() {
//clean up so you don't get /0 errors
long goodHits = (getSuccessfulCounter == 0) ? 1 : getSuccessfulCounter;
int physicalItems = (order.size() == 0) ? 1 : order.size();
double aveItemSize = ((double)currentSize / (double)physicalItems);StringBuffer buf = new StringBuffer()
.append("\nLFU ")
.append(currentSize)
.append("/")
.append(maxSize)
.append(" Physical items: ")
.append(order.size())
.append(" Ave item size: ")
.append(aveItemSize)
.append(" Adds: ")
.append(addCounter) //also "miss counter"
.append(" Gets: ")
.append(getSuccessfulCounter)
.append(" Miss ratio: ")
.append(addCounter / goodHits)
.append(" Order: { ");Container container = null;
Iterator i = order.keySet().iterator();
boolean isFirst = true;
while (i.hasNext()) {
if(! isFirst) {
buf.append(", ");
}
container = (Container)i.next();
buf.append(container.key); //just add the keys and use frequency
buf.append("*");
buf.append(container.useFrequency);
isFirst = false;
}buf.append(" }\n");
return buf.toString();
}public static void main(String[] args) {
---
LFUCache f = new LFUCache(3);
f.add("A", "VALUE");
f.add("B", "VALUE");
f.add("C", "VALUE");
f.get("A");
f.get("A");
f.get("A");
f.get("B");
f.get("C");
f.get("C");
f.get("C");
f.get("C");
System.out.println(">>>>>>>>>>> ALL ADDED <<<<<<<<<< " + f);
}
}
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
