Author: manik.surtani(a)jboss.com Date: 2009-02-06 13:10:10 -0500 (Fri, 06 Feb 2009) New Revision: 7661 Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUQueue.java core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuQueueTest.java Log: Better LFU impl Modified: core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUQueue.java =================================================================== --- core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUQueue.java 2009-02-06 17:46:20 UTC (rev 7660) +++ core/branches/flat/src/main/java/org/horizon/eviction/algorithms/lfu/LFUQueue.java 2009-02-06 18:10:10 UTC (rev 7661) @@ -21,136 +21,129 @@ */ package org.horizon.eviction.algorithms.lfu; -import org.horizon.CacheException; import org.horizon.eviction.algorithms.BaseEvictionQueue; +import java.util.Comparator; import java.util.HashMap; +import java.util.HashSet; import java.util.Iterator; -import java.util.PriorityQueue; +import java.util.Map; +import java.util.Set; +import java.util.TreeMap; /** * Least frequently used queue for use with the {@link org.horizon.eviction.algorithms.lfu.LFUAlgorithm}. This - * implementation guarantees O(ln n) for put and remove operations, and 2O(ln n) for visits since this requires a - * re-sort. + * implementation guarantees O (ln n) for put and remove, visit an iteration operations. * <p/> * // TODO investigate using a Fibonacci Heap or a Brodal Queue (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8133) - * instead of a TreeMap to implement // Since this will give us O(1) for insert, iteration and O(ln n) for remove and - * visit + * // another potential is Bernard Chazelle's SoftHeap * * @author Manik Surtani * @since 1.0 */ public class LFUQueue extends BaseEvictionQueue { - PriorityQueue<VisitableKey> keys = new PriorityQueue<VisitableKey>(); - HashMap<Object, VisitableKey> keyMap = new HashMap<Object, VisitableKey>(); + Map<Object, Integer> visitLog = new HashMap<Object, Integer>(); + Map<Integer, Set<Object>> iterationMap = new TreeMap<Integer, Set<Object>>(new Comparator<Integer>() { + public int compare(Integer o1, Integer o2) { + return (o1 < o2 ? 1 : (o1 == o2 ? 0 : -1)); + } + }); - public void visit(Object key) { - VisitableKey vk = keyMap.get(key); - if (vk != null) { + final Set<Object> getKeySet(int numVisits) { + Set<Object> set = iterationMap.get(numVisits); + if (set == null) { + set = new HashSet<Object>(); + iterationMap.put(numVisits, set); + } + return set; + } - // need to remove and add to reorder the tree - keys.remove(vk); - vk.visits++; - keys.add(vk); + final void addToKeySet(Object key, int numVisits) { + getKeySet(numVisits).add(key); + } + + final void removeFromKeySet(Object key, int numVisits) { + Set<Object> set = iterationMap.get(numVisits); + if (set != null) { + set.remove(key); + if (set.isEmpty()) iterationMap.remove(numVisits); } } + public void visit(Object key) { + Integer numVisits = visitLog.get(key); + if (numVisits != null) { + removeFromKeySet(key, numVisits); + numVisits++; + addToKeySet(key, numVisits); + visitLog.put(key, numVisits); + } + } + public boolean contains(Object key) { - return keyMap.containsKey(key); + return visitLog.containsKey(key); } public void remove(Object key) { - VisitableKey vk = keyMap.remove(key); - if (vk != null) { - if (!keys.remove(vk)) throw new CacheException("Problem removing key " + key); + Integer numVisits = visitLog.remove(key); + if (numVisits != null) { + removeFromKeySet(key, numVisits); } } public void add(Object key) { - if (!keyMap.containsKey(key)) { - VisitableKey vk = new VisitableKey(); - vk.key = key; - keyMap.put(key, vk); - keys.add(vk); + if (!visitLog.containsKey(key)) { + // new, so numVisits is 1. + getKeySet(1).add(key); + visitLog.put(key, 1); } } public int size() { - return keyMap.size(); + return visitLog.size(); } @Override public boolean isEmpty() { - return keyMap.size() == 0 && keys.size() == 0; + return visitLog.size() == 0; } public void clear() { - keyMap.clear(); - keys.clear(); + visitLog.clear(); + visitLog = new HashMap<Object, Integer>(); + iterationMap.clear(); + iterationMap = new HashMap<Integer, Set<Object>>(); } public Iterator<Object> iterator() { return new Iterator<Object>() { + Iterator<Set<Object>> setIterator = iterationMap.values().iterator(); + Set<Object> currentKeySet; + Iterator<Object> keyIterator; + Object currentKey; - Iterator<VisitableKey> vkIter = keys.iterator(); - Object lastKey; - public boolean hasNext() { - return vkIter.hasNext(); + while (keyIterator == null || !keyIterator.hasNext()) { + if (setIterator.hasNext()) { + currentKeySet = setIterator.next(); + keyIterator = currentKeySet.iterator(); + } else return false; + } + return true; } public Object next() { - lastKey = vkIter.next().key; - return lastKey; + if (keyIterator == null && !hasNext()) throw new IllegalStateException("Out of bounds"); + return (currentKey = keyIterator.next()); } public void remove() { - if (lastKey == null) throw new IllegalStateException("Call next() before remove()!"); - vkIter.remove(); - keyMap.remove(lastKey); + if (currentKey == null) throw new IllegalStateException("Call next() before remove()!"); + keyIterator.remove(); + if (currentKeySet.isEmpty()) setIterator.remove(); + visitLog.remove(currentKey); } }; } - - class VisitableKey implements Comparable { - Object key; - int visits; - - public int compareTo(Object o) { - if (o == null) return -1; - if (o instanceof VisitableKey) { - VisitableKey other = (VisitableKey) o; - return other.visits - visits; - } else { - return -1; - } - } - - @Override - public boolean equals(Object o) { - if (this == o) return true; - if (o == null || getClass() != o.getClass()) return false; - - VisitableKey that = (VisitableKey) o; - - if (key != null ? !key.equals(that.key) : that.key != null) return false; - - return true; - } - - @Override - public int hashCode() { - return key != null ? key.hashCode() : 0; - } - - @Override - public String toString() { - return "VisitableKey{" + - "key=" + key + - ", visits=" + visits + - '}'; - } - } - } Modified: core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuQueueTest.java =================================================================== --- core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuQueueTest.java 2009-02-06 17:46:20 UTC (rev 7660) +++ core/branches/flat/src/test/java/org/horizon/eviction/algorithms/lfu/LfuQueueTest.java 2009-02-06 18:10:10 UTC (rev 7661) @@ -27,6 +27,10 @@ return s; } + private int numVisits(LFUQueue queue, Object key) { + return queue.visitLog.get(key); + } + public void testOrder() throws Exception { LFUQueue queue = (LFUQueue) getNewEvictionQueue(); fillQueue(queue, 500); @@ -37,15 +41,16 @@ assert allKeys.isEmpty() : "Not all keys were encountered. Remaining keys " + allKeys; for (int i = 1; i < 500; i += 2) queue.visit(i); // visit all the even keys - System.out.println("Set: " + queue.keys); - System.out.println("KeyMap: " + queue.keyMap); + for (Object key : queue) System.out.println("Key: " + key); - assert (Integer) getFirstEntry(queue) % 2 == 1 : "We don't know which odd key this would be"; + assert (Integer) getFirstEntry(queue) % 2 == 1 : "First key should be odd. Was " + getFirstEntry(queue); + System.out.println(queue.visitLog); + // now check the sort order. for (Object key : queue) { Integer k = (Integer) key; - assert queue.keyMap.get(key).visits == k % 2 : "Expecting " + (k % 2) + " visits on key " + key + " but it was " + queue.keyMap.get(key).visits; + assert numVisits(queue, key) == 1 + (k % 2) : "Expecting " + (1 + (k % 2)) + " visits on key " + key + " but it was " + numVisits(queue, key); } int k = 0; @@ -60,8 +65,7 @@ for (int i = 0; i < 500; i += 2) { queue.visit(i); - LFUQueue.VisitableKey data = queue.keyMap.get(i); - assert 1 == data.visits : "Expected visit count to be 1 but it was " + data.visits + " on key " + i; + assert 2 == numVisits(queue, i) : "Expected visit count to be 2 but it was " + numVisits(queue, i) + " on key " + i; if (i > 250) queue.visit(i); // visit again! } @@ -70,9 +74,9 @@ for (Object key : queue) { k = (Integer) key; if (k <= 250) - assert 1 == queue.keyMap.get(key).visits : "Expected visit count to be 1 but it was " + queue.keyMap.get(key).visits + " on key " + key; + assert 2 == numVisits(queue, key) : "Expected visit count to be 2 but it was " + numVisits(queue, key) + " on key " + key; else - assert 2 == queue.keyMap.get(key).visits : "Expected visit count to be 2 but it was " + queue.keyMap.get(key).visits + " on key " + key; + assert 3 == numVisits(queue, key) : "Expected visit count to be 3 but it was " + numVisits(queue, key) + " on key " + key; } } @@ -81,7 +85,6 @@ fillQueue(queue, 500); assert 500 == queue.size(); - assert 500 == queue.keyMap.size(); int i = 0; for (Iterator it = queue.iterator(); it.hasNext() && it.next() != null;) {