(2022.10.17 Mon)
LRU, Least Recently Used是一种页面置换算法(page replacement algorithm)，其应用包括Python内存管理和智能手机"最近任务"等场景。LRU将刚刚使用的任务提前，选择最久未使用的任务予以淘汰。

比如手机的最近任务浏览功能，你可以在这里看到按时间顺序排列的最近使用的功能，每次当点击某个app，其对应的图标就会出现在最近任务列表的第一位，其他已经保存的任务依次向后移动。

LRU_case.jpeg

LRU的实现

在了解了LRU的基本特征之后，这部分我们实现LRU。根据其特点描述，每个app/任务会在使用之后放置于整个LRU队列的最前端，其他任务向后移动。该部分可考虑使用队列(array)或链表(linked list)实现。

使用array实现，优势在于占用空间小且连续(考虑到链表的每个元素需要保存指向其他元素的指针)，访问元素只需要通过index即可实现，复杂度为常数时间；劣势在于当某任务被前置时，排名其后的所有元素都要向后移动，复杂度为。

使用linked list实现，优势在于其中元素的位置调整灵活，只需要调整前后指针，复杂度为；劣势在于占用空间相比array更多，比如每个元素需要包含指向其他元素的指针，访问元素需要从头开始遍历，最坏情况达到了。

然而在Linked list的实现中，可通过hash table的方式，将访问元素的复杂度从降为。

实现：Doubly Linked List

在双向链表中，每个元素保留向前和向后两个指针，为了hash table使用，也保留了key和element/value两个字段的信息。

该Python实现中提供了三个类，Node，doublyLinkedList和LRU，其中前两个是LRU类实现的基础。这里的hash table实现采用了Python的dict。

• Node类：代表了每个任务/app，包含4个字段，key，value，previous pointer和next pointer。
• doublyLinkedList类：双向链表，可实现删除点、尾部弹出、从头加入节点。
• LRU类：包含两个方法，set和get，前者为加入新的任务/app，在加入该新的对象时，自动将其放在链表的头部，后者为访问特定任务/app，访问成功后将该对象置于链表的头部。

class Node:
    """
    Node object, including 4 fields, i.e., key, value, previous&next pointer
    """
    def __init__(self, key, value, prev=None, nex=None):
        self._key = key
        self._value = value
        self._prev = prev
        self._next = nex

class doublyLinkedList(object):
    def __init__(self):
        """
        head and tail work as placeholder
        """
        self._head = Node(None, None)
        self._tail = Node(None, None)
        self._len = 0

    def append_front(self, node):
        """
        add a node to the front
        """
        if self._len <= 0:
            logging.info(f"""into append_front method: {node}""")
            node._prev = self._head
            node._next = self._tail
            self._head._next = node
            self._tail._prev = node
            self._len += 1
            return
        old_head = self._head._next
        self._head._next = node
        node._prev = self._head
        node._next = old_head
        if old_head:
            old_head._prev = node
        self._len += 1

    def remove(self, node):
        """
        remove a node, update the pointers of prev&next nodes
        """
        logging.info(f"""into remove method of DLL: {node}""")
        logging.info(f"""prev pointer: {node._prev}""")
        prev = node._prev
        logging.info(f"""next pointer: {node._next}""")
        nex = node._next
        if node == self._head._next:
            self._head._next = nex
        if node == self._tail._prev:
            self._tail._prev = prev
        if prev:
            prev._next = nex
        if nex:
            nex._prev = prev
    
        node._prev = None
        node._next = None
        self._len -= 1
        return node

    def pop_tail(self):
        """
        remove last node in the list
        """
        tail = self._tail._prev
        if not tail:
            return tail
        prev_tail = tail._prev
        self._tail = prev_tail
        self._len -= 1
        if prev_tail:
            prev_tail._next = self._tail
        return tail

class LRU():
    """
    LRU is based on doubly linked list, setup capacity though
    """
    def __init__(self, capacity=5):
        self._capacity = capacity
        self._keys = {}
        self._list = doublyLinkedList()

    def set(self, key, value):
        """
        add a new node/element
        """
        if key in self._keys:
            logging.info(f"""key exists in the hash table: {key}""")
            node = self._keys[key]
            node._value = value
            logging.info(f"""about to conduct remove and append_front operation: {key}""")
            logging.info(f"""remove first: {key}""")
            r_node = self._list.remove(node)
            logging.info(f"""append front follows: {key}""")
            self._list.append_front(r_node)
            print(self._list._len, self._list)
            return f"""{key} updated: {value}"""
        if self._list._len >= self._capacity:
            p_node = self._list.pop_tail()
            if p_node:
                del self._keys[p_node._key]
                del p_node
        logging.info(f"""about to add new key to the hash map: {key}""")
        node = Node(key, value)
        self._keys[key] = node
        logging.info(f"""conduct append_front operation: {key}""")
        self._list.append_front(node)
        print("SET - key: %s, value: %s" % (key, value))
        print("length: ", self._list._len, ", head:", self._list._head._next._value)

    def get(self, key):
        """
        access to an existing node in the list
        """
        if key not in self._keys:
            return None
        logging.info(f"""get method: key {key} in the list""")
        node = self._keys[key]
        logging.info(f"""get method: conduct remove and append_front operations""")
        r_node = self._list.remove(node)
        self._list.append_front(r_node)
        print("GET - key: %s, value: %s" % (key, node._value))
        return node._value

运行 查看过程

if __name__ == '__main__':
    format = "%(asctime)s: %(message)s"
    logging.basicConfig(format=format, level=logging.INFO)
    lru = LRU(3)
    lru.set('name', 'jeff')
    lru.set('gender', 'male')
    lru.set('age', 39)
    lru.set('location', 'Hong Kong')
    lru.get('age')
    # lru.set
    print('lru keys: ', lru._keys)
    print('lru list: ', lru._list)

实现：Redis

Redis提供了LRU的实现方案。
placeholder