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

比如手機(jī)的最近任務(wù)瀏覽功能，你可以在這里看到按時(shí)間順序排列的最近使用的功能提佣，每次當(dāng)點(diǎn)擊某個(gè)app吮蛹，其對(duì)應(yīng)的圖標(biāo)就會(huì)出現(xiàn)在最近任務(wù)列表的第一位，其他已經(jīng)保存的任務(wù)依次向后移動(dòng)拌屏。

LRU_case.jpeg

LRU的實(shí)現(xiàn)

在了解了LRU的基本特征之后潮针，這部分我們實(shí)現(xiàn)LRU。根據(jù)其特點(diǎn)描述倚喂，每個(gè)app/任務(wù)會(huì)在使用之后放置于整個(gè)LRU隊(duì)列的最前端每篷，其他任務(wù)向后移動(dòng)。該部分可考慮使用隊(duì)列(array)或鏈表(linked list)實(shí)現(xiàn)端圈。

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

使用linked list實(shí)現(xiàn)无畔，優(yōu)勢(shì)在于其中元素的位置調(diào)整靈活啊楚，只需要調(diào)整前后指針，復(fù)雜度為浑彰；劣勢(shì)在于占用空間相比array更多恭理，比如每個(gè)元素需要包含指向其他元素的指針，訪問元素需要從頭開始遍歷郭变，最壞情況達(dá)到了颜价。

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

實(shí)現(xiàn)：Doubly Linked List

在雙向鏈表中夕春，每個(gè)元素保留向前和向后兩個(gè)指針，為了hash table使用专挪，也保留了key和element/value兩個(gè)字段的信息及志。

該P(yáng)ython實(shí)現(xiàn)中提供了三個(gè)類，Node寨腔，doublyLinkedList和LRU速侈，其中前兩個(gè)是LRU類實(shí)現(xiàn)的基礎(chǔ)。這里的hash table實(shí)現(xiàn)采用了Python的dict迫卢。

• Node類：代表了每個(gè)任務(wù)/app倚搬，包含4個(gè)字段，key乾蛤，value潭枣，previous pointer和next pointer。
• doublyLinkedList類：雙向鏈表幻捏，可實(shí)現(xiàn)刪除點(diǎn)盆犁、尾部彈出、從頭加入節(jié)點(diǎn)篡九。
• LRU類：包含兩個(gè)方法谐岁，set和get，前者為加入新的任務(wù)/app榛臼，在加入該新的對(duì)象時(shí)伊佃，自動(dòng)將其放在鏈表的頭部，后者為訪問特定任務(wù)/app沛善，訪問成功后將該對(duì)象置于鏈表的頭部航揉。

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

運(yùn)行 查看過程

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)

實(shí)現(xiàn)：Redis

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