天天看點
傳回

常見緩存算法和LRU與LFU的c++實作常見的緩存算法LRU完整C++代碼實作LRU和LFU的差別

目錄

常見的緩存算法

LRU緩存

LRU Cache具備的操作：

LRU的c++實作

雙連結清單節點的定義：

指定容量大小

删除操作

插入操作

擷取操作

插入新節點

LRU完整C++代碼實作

LRU和LFU的差別

原文連結： https://github.com/cpselvis，https://www.cnblogs.com/cpselvis/p/6272096.html；

對于web開發而言，緩存必不可少，也是提高性能最常用的方式。無論是浏覽器緩存(如果是chrome浏覽器，可以通過chrome:😕/cache檢視)，還是服務端的緩存(通過memcached或者redis等記憶體資料庫)。緩存不僅可以加速使用者的通路，同時也可以降低伺服器的負載和壓力。那麼，了解常見的緩存淘汰算法的政策和原理就顯得特别重要。

常見的緩存算法

  • LRU (Least recently used) 最近最少使用，如果資料最近被通路過，那麼将來被通路的幾率也更高。
  • LFU (Least frequently used) 最不經常使用，如果一個資料在最近一段時間内使用次數很少，那麼在将來一段時間内被使用的可能性也很小。
  • FIFO (Fist in first out) 先進先出， 如果一個資料最先進入緩存中，則應該最早淘汰掉。

LRU緩存

像浏覽器的緩存政策、memcached的緩存政策都是使用LRU這個算法，LRU算法會将近期最不會通路的資料淘汰掉。LRU如此流行的原因是實作比較簡單，而且對于實際問題也很實用，良好的運作時性能，命中率較高。下面談談如何實作LRU緩存：

  • 新資料插入到連結清單頭部
  • 每當緩存命中（即緩存資料被通路），則将資料移到連結清單頭部
  • 當連結清單滿的時候，将連結清單尾部的資料丢棄

LRU Cache具備的操作：

  • set(key,value)：如果key在hashmap中存在，則先重置對應的value值，然後擷取對應的節點cur，将cur節點從連結清單删除，并移動到連結清單的頭部；若果key在hashmap不存在，則建立一個節點，并将節點放到連結清單的頭部。當Cache存滿的時候，将連結清單最後一個節點删除即可。
  • get(key)：如果key在hashmap中存在，則把對應的節點放到連結清單頭部，并傳回對應的value值；如果不存在，則傳回-1。

LRU的c++實作

LRU實作采用雙向連結清單 + Map 來進行實作。這裡采用雙向連結清單的原因是：如果采用普通的單連結清單，則删除節點的時候需要從表頭開始周遊查找，效率為O(n)，采用雙向連結清單可以直接改變節點的前驅的指針指向進行删除達到O(1)的效率。使用Map來儲存節點的key、value值便于能在O(logN)的時間查找元素,對應get操作。

雙連結清單節點的定義： 

struct CacheNode {
  int key;      // 鍵
  int value;    // 值
  CacheNode *pre, *next;  // 節點的前驅、後繼指針
  CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {}
};

指定容量大小

對于LRUCache這個類而言，構造函數需要指定容量大小

LRUCache(int capacity)
{
  size = capacity;      // 容量
  head = NULL;          // 連結清單頭指針
  tail = NULL;          // 連結清單尾指針
}

删除操作

雙連結清單的節點删除操作：

void remove(CacheNode *node)
{
  if (node -> pre != NULL)
  {
    node -> pre -> next = node -> next;
  }
  else
  {
    head = node -> next;
  }
  if (node -> next != NULL)
  {
    node -> next -> pre = node -> pre;
  }
  else
  {
    tail = node -> pre;
  }
}

插入操作

将節點插入到頭部的操作：

void setHead(CacheNode *node)
{
  node -> next = head;
  node -> pre = NULL;

  if (head != NULL)
  {
    head -> pre = node;
  }
  head = node;
  if (tail == NULL)
  {
    tail = head;
  }
}

擷取操作

get(key)操作的實作比較簡單，直接通過判斷Map是否含有key值即可，如果查找到key，則傳回對應的value，否則傳回-1;

int get(int key)
{
  map<int, CacheNode *>::iterator it = mp.find(key);
  if (it != mp.end())
  {
    CacheNode *node = it -> second;
    remove(node);
    setHead(node);
    return node -> value;
  }
  else
  {
    return -1;
  }
}

插入新節點

set(key, value)操作需要分情況判斷。如果目前的key值對應的節點已經存在，則将這個節點取出來，并且删除節點所處的原有的位置，并在頭部插入該節點；如果節點不存在節點中，這個時候需要在連結清單的頭部插入新節點，插入新節點可能導緻容量溢出，如果出現溢出的情況，則需要删除連結清單尾部的節點。

void set(int key, int value)
{
  map<int, CacheNode *>::iterator it = mp.find(key);
  if (it != mp.end())
  {
    CacheNode *node = it -> second;
    node -> value = value;
    remove(node);
    setHead(node);
  }
  else
  {
    CacheNode *newNode = new CacheNode(key, value);
    if (mp.size() >= size)
    {
      map<int, CacheNode *>::iterator iter = mp.find(tail -> key);
      remove(tail);
      mp.erase(iter);
    }
    setHead(newNode);
    mp[key] = newNode;
  }
}

至此，LRU算法的實作操作就完成了。

LRU完整C++代碼實作 

/**
 * System design: LRU cache (least recently used).
 *
 * cpselvis([email protected])
 * Oct 8th, 2016
 */
#include<iostream>
#include<map>

using namespace std;

/**
 * Definition of cachelist node, it's double linked list node.
 */
struct CacheNode {
  int key;
  int value;
  CacheNode *pre, *next;
  CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {}
};

class LRUCache{
private:
  int size;                     // Maximum of cachelist size.
  CacheNode *head, *tail;
  map<int, CacheNode *> mp;          // Use hashmap to store
public:
  LRUCache(int capacity)
  {
    size = capacity;
    head = NULL;
    tail = NULL;
  }

  int get(int key)
  {
    map<int, CacheNode *>::iterator it = mp.find(key);
    if (it != mp.end())
    {
      CacheNode *node = it -> second;
      remove(node);
      setHead(node);
      return node -> value;
    }
    else
    {
      return -1;
    }
  }

  void set(int key, int value)
  {
    map<int, CacheNode *>::iterator it = mp.find(key);
    if (it != mp.end())
    {
      CacheNode *node = it -> second;
      node -> value = value;
      remove(node);
      setHead(node);
    }
    else
    {
      CacheNode *newNode = new CacheNode(key, value);
      if (mp.size() >= size)
      {
	map<int, CacheNode *>::iterator iter = mp.find(tail -> key);
      	remove(tail);
	mp.erase(iter);
      }
      setHead(newNode);
      mp[key] = newNode;
    }
  }

  void remove(CacheNode *node)
  {
    if (node -> pre != NULL)
    {
      node -> pre -> next = node -> next;
    }
    else
    {
      head = node -> next;
    }
    if (node -> next != NULL)
    {
      node -> next -> pre = node -> pre;
    }
    else
    {
      tail = node -> pre;
    }
  }

  void setHead(CacheNode *node)
  {
    node -> next = head;
    node -> pre = NULL;

    if (head != NULL)
    {
      head -> pre = node;
    }
    head = node;
    if (tail == NULL)
    {
      tail = head;
    }
  }
};


int main(int argc, char **argv)
{
  LRUCache *lruCache = new LRUCache(2);
  lruCache -> set(2, 1);
  lruCache -> set(1, 1);
  cout << lruCache -> get(2) << endl;
  lruCache -> set(4, 1);
  cout << lruCache -> get(1) << endl;
  cout << lruCache -> get(2) << endl;
}

LRU和LFU的差別

LRU是最近最少使用頁面置換算法(Least Recently Used),也就是首先淘汰最長時間未被使用的頁面!

LFU是最近最不常用頁面置換算法(Least Frequently Used),也就是淘汰一定時期内被通路次數最少的頁!

比如,第二種方法的時期T為10分鐘,如果每分鐘進行一次調頁,主存塊為3,若所需頁面走向為2 1 2 1 2 3 4

注意,當調頁面4時會發生缺頁中斷

若按LRU算法,應換頁面1(1頁面最久未被使用) 但按LFU算法應換頁面3(十分鐘内,頁面3隻使用了一次)

可見LRU關鍵是看頁面最後一次被使用到發生排程的時間長短,

而LFU關鍵是看一定時間段内頁面被使用的頻率!

算法與資料結構 LRU LFU 資料緩存算法
上一篇: JS判斷送出表單不能為空 等的驗證
下一篇: 【Javascript】基礎-命名空間

繼續閱讀