北京赛车pk10直播开奖
首頁
登錄 | 注冊

LRU算法原理解析

LRULeast Recently Used的縮寫,即最近最少使用,常用于頁面置換算法,是為虛擬頁式存儲管理服務的。

現代操作系統提供了一種對主存的抽象概念虛擬內存,來對主存進行更好地管理。他將主存看成是一個存儲在磁盤上的地址空間的高速緩存,在主存中只保存活動區域,并根據需要在主存和磁盤之間來回傳送數據。虛擬內存被組織為存放在磁盤上的N個連續的字節組成的數組,每個字節都有唯一的虛擬地址,作為到數組的索引。虛擬內存被分割為大小固定的數據塊虛擬頁(Virtual Page,VP),這些數據塊作為主存和磁盤之間的傳輸單元。類似地,物理內存被分割為物理頁(Physical Page,PP)

虛擬內存使用頁表來記錄和判斷一個虛擬頁是否緩存在物理內存中:

LRU算法原理解析

如上圖所示,當CPU訪問虛擬頁VP3時,發現VP3并未緩存在物理內存之中,這稱之為缺頁,現在需要將VP3從磁盤復制到物理內存中,但在此之前,為了保持原有空間的大小,需要在物理內存中選擇一個犧牲頁,將其復制到磁盤中,這稱之為交換或者頁面調度,圖中的犧牲頁為VP4。把哪個頁面調出去可以達到調動盡量少的目的?最好是每次調換出的頁面是所有內存頁面中最遲將被使用的——這可以最大限度的推遲頁面調換,這種算法,被稱為理想頁面置換算法,但這種算法很難完美達到。

為了盡量減少與理想算法的差距,產生了各種精妙的算法,LRU算法便是其中一個。

LRU原理

LRU 算法的設計原則是:如果一個數據在最近一段時間沒有被訪問到,那么在將來它被訪問的可能性也很小。也就是說,當限定的空間已存滿數據時,應當把最久沒有被訪問到的數據淘汰。

根據LRU原理和Redis實現所示,假定系統為某進程分配了3個物理塊,進程運行時的頁面走向為 7 0 1 2 0 3 0 4,開始時3個物理塊均為空,那么LRU算法是如下工作的:

LRU算法原理解析

基于哈希表和雙向鏈表的LRU算法實現

如果要自己實現一個LRU算法,可以用哈希表加雙向鏈表實現:

LRU算法原理解析

設計思路是,使用哈希表存儲 key,值為鏈表中的節點,節點中存儲值,雙向鏈表來記錄節點的順序,頭部為最近訪問節點。

LRU算法中有兩種基本操作:

  • get(key):查詢key對應的節點,如果key存在,將節點移動至鏈表頭部。
  • set(key, value): 設置key對應的節點的值。如果key不存在,則新建節點,置于鏈表開頭。如果鏈表長度超標,則將處于尾部的最后一個節點去掉。如果節點存在,更新節點的值,同時將節點置于鏈表頭部。

LRU緩存機制

leetcode上有一道關于LRU緩存機制的題目:

運用你所掌握的數據結構,設計和實現一個 LRU (最近最少使用) 緩存機制。它應該支持以下操作: 獲取數據 get 和 寫入數據 put 。

獲取數據 get(key) - 如果密鑰 (key) 存在于緩存中,則獲取密鑰的值(總是正數),否則返回 -1。 寫入數據 put(key, value) - 如果密鑰不存在,則寫入其數據值。當緩存容量達到上限時,它應該在寫入新數據之前刪除最近最少使用的數據值,從而為新的數據值留出空間。

進階:

你是否可以在 O(1) 時間復雜度內完成這兩種操作?

示例:

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 該操作會使得密鑰 2 作廢
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 該操作會使得密鑰 1 作廢
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

我們可以自己實現雙向鏈表,也可以使用現成的數據結構,Python中的數據結構OrderedDict是一個有序哈希表,可以記住加入哈希表的鍵的順序,相當于同時實現了哈希表與雙向鏈表。OrderedDict是將最新數據放置于末尾的:

In [35]: from collections import OrderedDict
In [36]: lru = OrderedDict()
In [37]: lru[1] = 1
In [38]: lru[2] = 2
In [39]: lru
Out[39]: OrderedDict([(1, 1), (2, 2)])
In [40]: lru.popitem()
Out[40]: (2, 2)

OrderedDict有兩個重要方法:

  • popitem(last=True): 返回一個鍵值對,當last=True時,按照LIFO的順序,否則按照FIFO的順序。
  • move_to_end(key, last=True): 將現有 key 移動到有序字典的任一端。 如果 last 為True(默認)則將元素移至末尾;如果 last 為False則將元素移至開頭。

刪除數據時,可以使用popitem(last=False)將開頭最近未訪問的鍵值對刪除。訪問或者設置數據時,使用move_to_end(key, last=True)將鍵值對移動至末尾。

代碼實現:

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity: int):
        self.lru = OrderedDict()
        self.capacity = capacity
         
    def get(self, key: int) -> int:
        self._update(key)
        return self.lru.get(key, -1)
         
    def put(self, key: int, value: int) -> None:
        self._update(key)
        self.lru[key] = value
        if len(self.lru) > self.capacity:
            self.lru.popitem(False)
         
    def _update(self, key: int):
        if key in self.lru:
            self.lru.move_to_end(key)

OrderedDict源碼分析

 OrderedDict其實也是用哈希表與雙向鏈表實現的:

class OrderedDict(dict):
    'Dictionary that remembers insertion order'
    # An inherited dict maps keys to values.
    # The inherited dict provides __getitem__, __len__, __contains__, and get.
    # The remaining methods are order-aware.
    # Big-O running times for all methods are the same as regular dictionaries.
    # The internal self.__map dict maps keys to links in a doubly linked list.
    # The circular doubly linked list starts and ends with a sentinel element.
    # The sentinel element never gets deleted (this simplifies the algorithm).
    # The sentinel is in self.__hardroot with a weakref proxy in self.__root.
    # The prev links are weakref proxies (to prevent circular references).
    # Individual links are kept alive by the hard reference in self.__map.
    # Those hard references disappear when a key is deleted from an OrderedDict.
    def __init__(*args, **kwds):
        '''Initialize an ordered dictionary.  The signature is the same as
        regular dictionaries.  Keyword argument order is preserved.
        '''
        if not args:
            raise TypeError("descriptor '__init__' of 'OrderedDict' object "
                            "needs an argument")
        self, *args = args
        if len(args) > 1:
            raise TypeError('expected at most 1 arguments, got %d' % len(args))
        try:
            self.__root
        except AttributeError:
            self.__hardroot = _Link()
            self.__root = root = _proxy(self.__hardroot)
            root.prev = root.next = root
            self.__map = {}
        self.__update(*args, **kwds)
    def __setitem__(self, key, value,
                    dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
        'od.__setitem__(i, y) <==> od[i]=y'
        # Setting a new item creates a new link at the end of the linked list,
        # and the inherited dictionary is updated with the new key/value pair.
        if key not in self:
            self.__map[key] = link = Link()
            root = self.__root
            last = root.prev
            link.prev, link.next, link.key = last, root, key
            last.next = link
            root.prev = proxy(link)
        dict_setitem(self, key, value)

 由源碼看出,OrderedDict使用self.__map = {}作為哈希表,其中保存了key與鏈表中的節點Link()的鍵值對,self.__map[key] = link = Link():

class _Link(object):
    __slots__ = 'prev', 'next', 'key', '__weakref__'

  節點Link()中保存了指向前一個節點的指針prev,指向后一個節點的指針next以及key值。

  而且,這里的鏈表是一個環形雙向鏈表,OrderedDict使用一個哨兵元素root作為鏈表的headtail

self.__hardroot = _Link()
self.__root = root = _proxy(self.__hardroot)
 root.prev = root.next = root

  由__setitem__可知,向OrderedDict中添加新值時,鏈表變為如下的環形結構:

      next            next            next
root <----> new node1 <----> new node2 <----> root
      prev            prev            prev

 root.next為鏈表的第一個節點,root.prev為鏈表的最后一個節點。

  由于OrderedDict繼承自dict,鍵值對是保存在OrderedDict自身中的,鏈表節點中只保存了key,并未保存value

  如果我們要自己實現的話,無需如此復雜,可以將value置于節點之中,鏈表只需要實現插入最前端與移除最后端節點的功能即可:

from _weakref import proxy as _proxy
class Node:
    __slots__ = ('prev', 'next', 'key', 'value', '__weakref__')
class LRUCache:
    def __init__(self, capacity: int):
        self.__hardroot = Node()
        self.__root = root = _proxy(self.__hardroot)
        root.prev = root.next = root
        self.__map = {}
        self.capacity = capacity
         
    def get(self, key: int) -> int:
        if key in self.__map:
            self.move_to_head(key)
            return self.__map[key].value
        else:
            return -1
         
    def put(self, key: int, value: int) -> None:
        if key in self.__map:
            node = self.__map[key]
            node.value = value
            self.move_to_head(key)
        else:
            node = Node()
            node.key = key
            node.value = value
            self.__map[key] = node
            self.add_head(node)
            if len(self.__map) > self.capacity:
                self.rm_tail()
         
    def move_to_head(self, key: int) -> None:
        if key in self.__map:
            node = self.__map[key]
            node.prev.next = node.next
            node.next.prev = node.prev
            head = self.__root.next
            self.__root.next = node
            node.prev = self.__root
            node.next = head
            head.prev = node
     
    def add_head(self, node: Node) -> None:
        head = self.__root.next
        self.__root.next = node
        node.prev = self.__root
        node.next = head
        head.prev = node
     
    def rm_tail(self) -> None:
        tail = self.__root.prev
        del self.__map[tail.key]
        tail.prev.next = self.__root
        self.__root.prev = tail.prev

node-lru-cache

在實際應用中,要實現LRU緩存算法,還要實現很多額外的功能。

有一個用Javascript實現的很好的node-lru-cache包:

var LRU = require("lru-cache")
  , options = { max: 500
              , length: function (n, key) { return n * 2 + key.length }
              , dispose: function (key, n) { n.close() }
              , maxAge: 1000 * 60 * 60 }
  , cache = new LRU(options)
  , otherCache = new LRU(50) // sets just the max size
cache.set("key", "value")
cache.get("key") // "value"

這個包不是用緩存key的數量來判斷是否要啟動LRU淘汰算法,而是使用保存的鍵值對的實際大小來判斷。選項options中可以設置緩存所占空間的上限max,判斷鍵值對所占空間的函數length,還可以設置鍵值對的過期時間maxAge等,有興趣的可以看下。

參考鏈接



2019 monjeep.com webmaster#monjeep.com
12 q. 0.012 s.
京ICP備10005923號
北京赛车pk10直播开奖
北京时时彩是不是官方彩票 重庆时时彩龙虎合走势图八方集团 广西快3查询 秒速时时彩彩票平台 8波足球即时比分网 贵州十一选五开奖遗漏 pk彩票吧 赛车pk拾官网 六合彩现场直播 宣化双色球