LFU Cache


  • 1
    J

    Write an implementation for Least Frequently Used Cache.


  • 0

    ref LinkedHashMap


  • 0

    @elmirap How would that work?


  • 0

    @StefanPochmann LinkedHashMap could be used as Least Frequently Used Cache, when accessOrder is used. @jbuddha could take a look at the source of LinkedHashMap.Of course there are other sources which give an idea what Least Frequently Used Cache looks like


  • 0

    @elmirap I still don't get it. Are you sure you're not confusing this with "least recently used"?


  • 0

    @StefanPochmann yes, apparently it is my mistake, sorry


  • 0

    Not tested code. Hint : Time complexity could be improved with other implementation

    
    public class LFU<K,V> {    
            
            private static final int  LIMIT = 10;
            
            static class Entry<K,V> {
                public Entry(K k, V v) {
                   key = k;
                   f = 1;
                   value = v;
               }
               K key;
               V value;
               int f;           
            }
            
            PriorityQueue<Entry<K,V>> frequences = new PriorityQueue<>(new Comparator<Entry<K,V>>(){
                public int compare(Entry<K,V> e1,Entry<K,V> e2) {
                    return e1.f - e2.f;
                }
            });
            
            
            Map<K,Entry<K,V>> cache = new HashMap<>();
            public void set(K key ,V value) {
                if (!cache.containsKey(key)) {                
                    if (frequences.size() == LIMIT)  {
                        Entry<K,V> tmp = frequences.poll();
                        cache.remove(tmp.key);                   
                    } 
                    Entry<K,V> e = new Entry<>(key,value);
                    cache.put(key, e);
                    frequences.add(e);  
                }
            }
            public V get(K key) {
                if (cache.containsKey(key)) {
                    Entry<K,V> entry = cache.get(key);
                    frequences.remove(entry);
                    entry.f =entry.f + 1;
                    frequences.add(entry);
                    return entry.value;
                }
                return null;
            }
        }

  • 1
    J

    I have implemented using a doubly linked list and a hashmap.


  • 0

    LFU implementation using minheap.

    public class LFUCache<T extends Comparable<T>> {

    private final int LIMIT = 1 + 5; 	// position idx 0 has been reserved to null. (swap operations)
    private int size = 0;
    private Entry<T>[] entries = new Entry[LIMIT];
    private static int indexer = 0; 
    
    private class Entry<T> {
    	int hitCount;
    	T value;
    	
    	public Entry(T value) {
    		this.value = value;
    		this.hitCount = indexer ++;
    	}
    	
    	@Override
    	public String toString() {
    		return value.toString() + "(" + hitCount + ")";
    	}
    }
    
    public void insert(T value) {
    	int index = find(value);
    	
    	if (index > 0)
    		entries[index].hitCount = indexer ++;
    	else {
    		if ((size + 1) < LIMIT) {
    			entries[++ size] = new Entry<>(value);	
    		} else {
    			System.out.println("removing least reacently used : " + entries[1].value.toString());
    			entries[1] = new Entry<>(value);
    		}
    	}
    	
    	maintainHeap();
    }
    
    public int find(T value) {
    	int index = -1;
    	for (int idx = 1; idx <= size; idx ++) {
    		if (entries[idx].value.compareTo(value) == 0) {
    			index = idx;
    			break;
    		}
    	}
    	return index;
    }
    
    private void maintainHeap() {
    	for (int idx = size/2; idx > 0; idx --)
    		heapify(idx);
    }
    
    private void heapify(int idx) {
    	if (idx <= 0)
    		return;
    	
    	int swapIndex = -1;
    	
    	if ((2 * idx) <= size && entries[idx].hitCount > entries[2 * idx].hitCount) 
    		swapIndex = ((2 * idx + 1) <= size && (entries[2 * idx].hitCount > entries[2 * idx + 1].hitCount)) ? (2 * idx + 1) : (2 * idx) ;
    	
    	else if ((2 * idx + 1) <= size && (entries[idx].hitCount > entries[2 * idx + 1].hitCount)) 
    		swapIndex = (2 * idx + 1);
    	
    	if (swapIndex > 0) {
    		entries[0] = entries[swapIndex];
    		entries[swapIndex] = entries[idx];
    		entries[idx] = entries[0];
    		entries[0] = null;
    
    		heapify(swapIndex);
    	}
    }
    
    public String stringify() {
    	StringBuilder builder = new StringBuilder();
    	
    	for (int idx = 1; idx <= size; idx ++) 
    		builder.append(entries[idx].value.toString());
    	
    	return builder.toString();
    }
    
    /*
     * Driver code
     */
    public static void main(String[] args) {
    	assertEquals(new String[] {"ABC", "CDFAE", "DEFAB"},  runAndReturn("ABC!DEAF!B!"));
    }
    
    // runner method
    private static String[] runAndReturn(String input) {
    	LFUCache<String> cache = new LFUCache<>();
    	
    	List<String> output = new ArrayList<>();
    	
    	for (int idx = 0; idx < input.length(); idx ++) {
    		if (input.charAt(idx) == '!')
    			output.add(cache.stringify());
    		else
    			cache.insert(String.valueOf(input.charAt(idx)));
    	}
    	
    	return output.toArray(new String[0]);
    }
    

    }


  • 0

    There is an implementation with linked lists, which provides constant time access


  • 0

    @elmirap Indeed that would be efficient. I will try that too. Thanks :)


  • 1

    @himanshu41 I don't want to spoil but I will share a solution I read about. You could create the following list:

    head - > 1 -> 2 -> 4
    ---------- |-----|-----|
    -----------i1----it3---it5
    -----------|-----|------|
    -----------it2---it4----it6

    here it1,it2 are items with frequence 1
    it3 and it4 have frequence 2
    i5 and it6 have frequence 4
    Each item has additional pointer to its parent 1,2, or 4
    When you need to update item's frequece you have to remove it from its frequence's list and to move it to new if such list exists.Otherwise you have to create it.
    All lists are double linked.


  • 0

    This is O(1) LFU Cache Implementation.

    Reference: http://javarticles.com/2012/06/lfu-cache.html

    package Amazon;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    
    class MyValue {
    	int value, freq;
    	
    	public MyValue(int value, int freq) {
    		this.value = value;
    		this.freq = freq;
    	}
    }
    
    public class LfuCache {
    	private Map<Integer, MyValue> lfuCache;
    	private List<LinkedList<Integer>> freqList;
    	int CAPACITY;
    
    	public LfuCache(int cap) {
    		this.CAPACITY = cap;
    		this.lfuCache = new HashMap<>();
    		this.freqList = new ArrayList<>();
    	}
    	
    	private int get(int key) { 
    		MyValue myValue = lfuCache.get(key);
    		
    		// value doesn't exist
    		if(null == myValue) {
    			return -1;
    		}
    		
    		freqList.get(myValue.freq - 1).remove(new Integer(key));
    
    		if(myValue.freq < CAPACITY)
    			++myValue.freq;
    		
    		
    		if(freqList.size() <= myValue.freq -1 || null == freqList.get(myValue.freq -1)) {
    			freqList.add(myValue.freq -1, new LinkedList<>()); 
    		}
    		
    		freqList.get(myValue.freq -1).add(key);
    		
    		lfuCache.put(key, myValue);
    		
    		return myValue.value;
    		
    	}
    
    	private void put(int key, int value) {
    		MyValue myValue = lfuCache.get(key);
    		
    		// value doesn't exist
    		if(null == myValue) {
    			myValue = new MyValue(value, 1);
    			
    			// time to remove least frequently used value
    			if(lfuCache.size() == CAPACITY) {
    				int myEvictedKey = freqList.get(0).removeFirst();
    				lfuCache.remove(myEvictedKey);
    			}
    			
    			lfuCache.put(key, myValue);
    			
    			if(freqList.size() < 1 || null == freqList.get(0)) {
    				freqList.add(0, new LinkedList<>()); 
    			}
    
    			freqList.get(0).add(key);
    
    		} else {
    			// value already exist, so just update the frequency
    			
    			freqList.get(myValue.freq - 1).remove(new Integer(key));
    
    			if(myValue.freq < CAPACITY)
    				++myValue.freq;
    
    			if(freqList.size() <= myValue.freq -1 || null == freqList.get(myValue.freq -1)) {
    				freqList.add(myValue.freq -1, new LinkedList<>()); 
    			}
    			
    			freqList.get(myValue.freq -1).add(key);
    			
    			lfuCache.put(key, myValue);
    		}
    	}
    
    	public static void main(String[] args) {
    		LfuCache cache = new LfuCache(3);
    
    		// Key 1 : freq 1
    		cache.put(1, 10);
    
    		// Key 2 : freq 1
    		cache.put(2, 20);
    		
    		// Key 1 : freq 2
    		System.out.println(cache.get(1));
    		
    		// Key 3 : freq 1
    		cache.put(3, 30);
    
    		// Key 4 : freq 1
    		cache.put(4, 40);
    
    		// Now one of the LFU element should get removed which is 2. Let's see
    		System.out.println(cache.get(2));
    
    	}
    
    }
    
    

  • 0

    @elmirap hey did you get a chance to share this O(1) solution?


  • 2
    W

    Here is my solution to implement a Least Frequently Used Cache in C++.

    • The idea is based on the so-called, Index Priority Queue, which maintains not only a priority queue but also a hashmap, indexMap, that map an the key of the element to its position (index) in the priority queue. The reason why we need the indexMap is that: when we access an existing element using get() or set(), its usage frequency should be increased by one, and this forces us to change the position of this element. To quickly access the element in the priority queue, we need to use the indexMap.

    • Another tricky point is that when we need to evict an element, but there are multiple elements with the same minimum usage frequency, we need to evict the least recently used element. To handle this, I maintain a time-stamp variable in the LFRCache. When two elements have the same usage frequency, the least recently used one will be at parent node.

    Here is my code that has been tested at Lintcode.

    class LFUCache{
    public:
        struct Node {
            int key;
            int val;
            int fre;
            int timeStamp;
            Node(): key(-1), val(-1), timeStamp(-1), fre(0) {}
            Node(int k, int v, int ts): key(k), val(v), timeStamp(ts), fre(1) {}
        };
    
        LFUCache(int capacity) {
            Cap = capacity;
            Node* root = new Node();
            pq.push_back(root);
            ts = 0;
        }
    
        void set(int key, int value) {
    		if(Cap <= 0) return;
    		if(mp.count(key)) {
    			int index = mp[key];
    			pq[index]->val = value;
    			get(key);
    		}
    		else {
    			if(pq.size() - 1 == Cap) {
    				int oldKey = pq[1]->key;
    				mp.erase(oldKey);
    				Node* newnode = new Node(key, value, ++ts);
    				pq[1] = newnode;
    				mp[key] = 1;
    				sink(1);
    			}
    			else {
    				Node* newnode = new Node(key, value, ++ts);
    				pq.push_back(newnode);
    				mp[key] = pq.size() - 1;
    				swim(pq.size() - 1);
    			}
    		}
    	}
    
    	int get(int key) {
    		if(!mp.count(key)) return -1;
    		int index = mp[key];
    		int val = pq[index]->val;
    		pq[index]->fre++;
    		pq[index]->timeStamp = ++ts;
    		sink(index);
    		return val;
    	}
    
    private:
    	vector<Node*> pq; // A priority queue, with the least usage frequency and least recently used element at the top.
    	unordered_map<int, int> mp; // A mapping from the key of the element to its index in the priority queue.
    	int Cap; // Capcity of the cache
    	int ts; // time-stamp: indicate the time stamp of the latest operation of an element. According to the requirement of LFU cache, when we need to evict an element from the cache, but there are multiple elements with the same minimum frequency, then the least recently used element should be evicted.
    
        /*
         * Recursively sink a node in priority queue. A node will be sinked, when its frequency is larger than any of its
         * children nodes, or the node has the same frequency with a child, but it is recently updated. 
         */
    	void sink(int index) {
    		int left = 2 * index, right = 2 * index + 1, target = index;
    		if(left < pq.size() && pq[left]->fre <= pq[target]->fre) // If the left child has the same frequency, we probably need to swap the parent node and the child node, because the parent node is recently accessed, and the left child node was accessed at an older time stamp.
    		    target = left;
                    if(right < pq.size()) { 
                           if(pq[right]->fre < pq[target]->fre || (pq[right]->fre == pq[target]->fre && pq[right]->timeStamp < pq[target]->timeStamp)) // If right child has the same frequency and an older time stamp, we must swap it.
                                target = right;
    		}
    		if(target != index) {
    			myswap(target, index);
    			sink(target);
    		}
    	}
        
        /*a
         * Recursively swim a node in priority queue. A node will be swimmed, when its frequency is less than its
         * parent node. If the node has the same frequency with its parent, it is not needed to be swimmed, because
         * it is recently accessed.
         */
    	void swim(int index) {
    		int par = index / 2;
    		while(par > 0 && pq[par]->fre > pq[index]->fre) {
    			myswap(par, index);
    			index = par;
    			par /= 2;
    		}
    	}
    
    	void myswap(int id1, int id2) {
    		swap(pq[id1], pq[id2]);
    		mp[pq[id1]->key] = id1;
    		mp[pq[id2]->key] = id2;
    	}
    };
    

  • 0
    K

    @ramanpreetSinghKhinda You should use LinkedHashSet instead of LinkedList for freqList, because LinkedList has O(n) complexity for remove operation. LinkedHashSet has O(1) complexity for this operation.


  • 0
    C

    @ramanpreetSinghKhinda said in LFU Cache:

    I don't think this is actually O(1) time. I read the "paper" your link linked to. I don't think the author is correct because you can't traverse a linkedlist in O(1) time. Maybe I'm wrong, but I don't think it is actually O(1).


  • 0

    @cysmith he has a pointer to the node from the hashmap, no need to traverse. similar to the lru idea. however the author of the paper doesn't explain how we're going to move an item from a frequency list to another, how we're going to find the other list that has this specific frequency? I think a simple hashmap with key = frequency and value = head of the list that has all nodes with this frequency would do. But you are right, I don't think that this paper is correct


  • 0
    C

    @k' so do you mean a HashMap<Integer, LinkedHashMap<Integer, Integer>>()?


  • 0

    @cysmith i don't wanna be language specific but the hashtable should be something like hashtable (key, ptr to node that you will insert in the list)
    whatever you wanna call it pointer, reference, mem address


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.