(2022.10.17 Mon)
LRU, Least Recently Used是一種頁面置換算法(page replacement algorithm)，其應(yīng)用包括Python內(nèi)存管理和智能手機"最近任務(wù)"等場景。LRU將剛剛使用的任務(wù)提前，選擇最久未使用的任務(wù)予以淘汰。

比如手機的最近任務(wù)瀏覽功能，你可以在這里看到按時間順序排列的最近使用的功能，每次當點擊某個app，其對應(yīng)的圖標就會出現(xiàn)在最近任務(wù)列表的第一位，其他已經(jīng)保存的任務(wù)依次向后移動。

LRU_case.jpeg

LRU的實現(xiàn)

在了解了LRU的基本特征之后，這部分我們實現(xiàn)LRU。根據(jù)其特點描述，每個app/任務(wù)會在使用之后放置于整個LRU隊列的最前端，其他任務(wù)向后移動。該部分可考慮使用隊列(array)或鏈表(linked list)實現(xiàn)。

使用array實現(xiàn)，優(yōu)勢在于占用空間小且連續(xù)(考慮到鏈表的每個元素需要保存指向其他元素的指針)，訪問元素只需要通過index即可實現(xiàn)，復雜度為常數(shù)時間；劣勢在于當某任務(wù)被前置時，排名其后的所有元素都要向后移動，復雜度為。

使用linked list實現(xiàn)，優(yōu)勢在于其中元素的位置調(diào)整靈活，只需要調(diào)整前后指針，復雜度為；劣勢在于占用空間相比array更多，比如每個元素需要包含指向其他元素的指針，訪問元素需要從頭開始遍歷，最壞情況達到了。

然而在Linked list的實現(xiàn)中，可通過hash table的方式，將訪問元素的復雜度從降為。

實現(xiàn)：Doubly Linked List

在雙向鏈表中，每個元素保留向前和向后兩個指針，為了hash table使用，也保留了key和element/value兩個字段的信息。

該Python實現(xiàn)中提供了三個類，Node，doublyLinkedList和LRU，其中前兩個是LRU類實現(xiàn)的基礎(chǔ)。這里的hash table實現(xiàn)采用了Python的dict。

• Node類：代表了每個任務(wù)/app，包含4個字段，key，value，previous pointer和next pointer。
• doublyLinkedList類：雙向鏈表，可實現(xiàn)刪除點、尾部彈出、從頭加入節(jié)點。
• LRU類：包含兩個方法，set和get，前者為加入新的任務(wù)/app，在加入該新的對象時，自動將其放在鏈表的頭部，后者為訪問特定任務(wù)/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)

實現(xiàn)：Redis

Redis提供了LRU的實現(xiàn)方案。
placeholder