LFU cache implementation in python
Question: I have implemented LFU cache in python with the help of Priority Queue
Implementation given at
<https://docs.python.org/2/library/heapq.html#priority-queue-implementation-
notes>

I have given code in the end of the post.

But I feel that code has some serious problems:  
1\. To give a scenario, suppose there is only one page is continuously getting
visited (say 50 times). But this code will always mark the already added node
as "removed" and add it to heap again. So basically it will have 50 different
nodes for the same page. Hence increasing heap size enormously.  
2\. This question is almost similar to Q1 of Telephonic Interview of
<http://www.geeksforgeeks.org/flipkart-interview-set-2-sde-2/> And the person
mentioned that doubly linked list can give better efficiency as compared to
heap. Can anyone explain me, how?

    
    
    from llist import dllist
    import sys
    from heapq import heappush, heappop
    
    class LFUCache:
        heap = []
        cache_map = {}
        REMOVED = "<removed-task>"
    
        def __init__(self, cache_size):
            self.cache_size = cache_size
    
        def get_page_content(self, page_no):
            if self.cache_map.has_key(page_no):
                self.update_frequency_of_page_in_cache(page_no)  
            else:
                self.add_page_in_cache(page_no)
    
            return self.cache_map[page_no][2]       
    
        def add_page_in_cache(self, page_no):
            if (len(self.cache_map) == self.cache_size):
                self.delete_page_from_cache() 
    
            heap_node = [1, page_no, "content of page " + str(page_no)]
            heappush(self.heap, heap_node)
            self.cache_map[page_no] = heap_node
    
        def delete_page_from_cache(self):
            while self.heap:
                count, page_no, page_content = heappop(self.heap)
                if page_content is not self.REMOVED:
                    del self.cache_map[page_no]
                    return
    
        def update_frequency_of_page_in_cache(self, page_no): 
            heap_node = self.cache_map[page_no]
            heap_node[2] = self.REMOVED
            count = heap_node[0]
    
            heap_node = [count+1, page_no, "content of page " + str(page_no)]
            heappush(self.heap, heap_node)
            self.cache_map[page_no] = heap_node
    
    def main():
        cache_size = int(raw_input("Enter cache size "))
        cache = LFUCache(cache_size)
    
        while 1:
            page_no = int(raw_input("Enter page no needed "))
            print cache.get_page_content(page_no)
            print cache.heap, cache.cache_map, "\n"
    
    
    if __name__ == "__main__":
        main() 
    


Answer: Efficiency is a tricky thing. In real-world applications, it's often a good
idea to use the simplest and easiest algorithm, and only start to optimize
when that's measurably slow. And then you optimize by doing profiling to
figure out where the code is slow.

If you are using CPython, it gets especially tricky, as even an inefficient
algorithm implemented in C can beat an efficient algorithm implemented in
Python due to the large constant factors; e.g. a double-linked list
implemented in Python tends to be a lot slower than simply using the normal
Python list, even for cases where in theory it should be faster.

**Simple algorithm:**

For an LFU, the simplest algorithm is to use a dictionary that maps keys to
(item, frequency) objects, and update the frequency on each access. This makes
access very fast (O(1)), but pruning the cache is slower as you need to sort
by frequency to cut off the least-used elements. For certain usage
characteristics, this is actually faster than other "smarter" solutions,
though.

You can optimize for this pattern by not simply pruning your LFU cache to the
maximum length, but to prune it to, say, 50% of the maximum length when it
grows too large. That means your prune operation is called infrequently, so it
can be inefficient compared to the read operation.

**Using a heap:**

In (1), you used a heap because that's an efficient way of storing a priority
queue. But you are not implementing a priority queue. The resulting algorithm
is optimized for pruning, but not access: You can easily find the n smallest
elements, but it's not quite as obvious how to update the priority of an
existing element. In theory, you'd have to rebalance the heap after every
access, which is highly inefficient.

To avoid that, you added a trick by keeping elements around even if they are
deleted. But this trades in space for time.

If you don't want to trade in time, you could update the frequencies in-place,
and simply rebalance the heap before pruning the cache. You regain fast access
times at the expense of slower pruning time, like the simple algorithm above.
(I doubt there is any speed difference between the two, but I have not
measured this.)

**Using a double-linked list:**

The double-linked list mentioned in (2) takes advantage of the nature of the
possible changes here: An element is either added as the lowest priority (0
accesses), or an existing element's priority is incremented exactly by 1. You
can use these attributes to your advantage if you design your data structures
like this:

You have a double-linked list of elements which is ordered by the frequency of
the elements. In addition, you have a dictionary that maps items to elements
within that list.

Accessing an element then means:

  * Either it's not in the dictionary, that is, it's a new item, in which case you can simply append it to the end of the double-linked list (O(1))
  * or it's in the dictionary, in which case you increment the frequency in the element and move it leftwards through the double-linked list until the list is ordered again (O(n) worst-case, but usually closer to O(1)).

To prune the cache, you simply cut off n elements from the end of the list
(O(n)).

