Laurentluce.com Website Review

LEAST FREQUENTLY USED CACHE EVICTION SCHEME WITH COMPLEXITY O(1) IN PYTHON. This post describes the implementation in Python of a “Least Frequently Used” (LFU) algorithm cache eviction scheme with written by Prof. Ketan Shah, Anirban Mitra and Dhruv Matani. The naming in the implementation follows the naming in the paper. LFU cache eviction scheme is useful for an HTTP caching network proxy for example, where we want the least frequently used items to be The goal here is for the LFU cache algorithm to have a runtime complexity of O(1) for all of its operations, which include insertion, Doubly linked lists are used in this algorithm. One for the access frequency and each node in that list contains a list with the elements of same access frequency. Let say we have five elements in our cache. Two have been accessed one time and three have been accessed two times. In that case, the access frequency list has two nodes (frequency = 1 and frequency = 2). The first frequency node has two nodes in its list and the second frequency node has three nodes in its list.         self.data = data         self.prev = None Next, our doubly linked list. Each node has a prev and next attribute equal to the previous node and next node respectively. The head is set We can define our doubly linked list with methods to add a node at the end of the list, insert a node, remove a node and get a list with the         self.head = None         self.tail = None         # Number of nodes in list.         self.count = 0         node = cls(data)         node.prev = prev         node.next = next         if prev:             prev.next = node         if next:             next.prev = node         if not self.head or next is self.head:             self.head = node         if not self.tail or prev is self.tail: