LRUcachingdevise

最近最less使用(LRU)caching是放弃最近最less使用的项目首先如何devise和实现这样的caching类? devise要求如下:

1)尽可能快地find物品

2)一旦caching未命中并且caching已满,我们需要尽快replace最近最less使用的项目。

如何从devise模式和algorithmdevise的angular度分析和实现这个问题?

指向链表节点的链表+哈希表是实现LRUcaching的常用方法。 这给了O(1)操作(假设一个体面的散列)。 这个优点(O(1)):你可以通过locking整个结构来做一个multithreading的版本。 你不必担心粒度锁等

简而言之,它的工作方式是:

在访问一个值时,将链表中的相应节点移动到头部。

当你需要从caching中删除一个值时,你从尾部删除。

将值添加到caching时,只需将其放置在链接列表的头部即可。

感谢doublep,这里是一个C ++实现的网站: 杂项容器模板 。

这是我简单的示例c ++实现LRUcaching,结合散列(unordered_map)和列表。 列表中的项目有访问地图的键,地图上的项目有列表的迭代器访问列表。

#include <list> #include <unordered_map> #include <assert.h> using namespace std; template <class KEY_T, class VAL_T> class LRUCache{ private: list< pair<KEY_T,VAL_T> > item_list; unordered_map<KEY_T, decltype(item_list.begin()) > item_map; size_t cache_size; private: void clean(void){ while(item_map.size()>cache_size){ auto last_it = item_list.end(); last_it --; item_map.erase(last_it->first); item_list.pop_back(); } }; public: LRUCache(int cache_size_):cache_size(cache_size_){ ; }; void put(const KEY_T &key, const VAL_T &val){ auto it = item_map.find(key); if(it != item_map.end()){ item_list.erase(it->second); item_map.erase(it); } item_list.push_front(make_pair(key,val)); item_map.insert(make_pair(key, item_list.begin())); clean(); }; bool exist(const KEY_T &key){ return (item_map.count(key)>0); }; VAL_T get(const KEY_T &key){ assert(exist(key)); auto it = item_map.find(key); item_list.splice(item_list.begin(), item_list, it->second); return it->second->second; }; }; 

使用散列表和双向链表来deviseLRU Cache

双链表可以处理这个。 地图是根据其关键字跟踪节点位置的好方法。

 class LRUCache{ //define the double linked list, each node stores both the key and value. struct Node{ Node* next; Node* prev; int value; int key; Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){}; Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){}; }; map<int,Node*>mp; //map the key to the node in the linked list int cp; //capacity Node* tail; // double linked list tail pointer Node* head; // double linked list head pointer public: //constructor LRUCache(int capacity) { cp = capacity; mp.clear(); head=NULL; tail=NULL; } //insert node to the tail of the linked list void insertNode(Node* node){ if (!head){ head = node; tail = node; }else{ tail->next = node; node->prev = tail; tail = tail->next; } } //remove current node void rmNode(Node* node){ if (node==head){ head = head->next; if (head){head->prev = NULL;} }else{ if (node==tail){ tail =tail->prev; tail->next = NULL; }else{ node->next->prev = node->prev; node->prev->next = node->next; } } } // move current node to the tail of the linked list void moveNode(Node* node){ if (tail==node){ return; }else{ if (node==head){ node->next->prev = NULL; head = node->next; tail->next = node; node->prev = tail; tail=tail->next; }else{ node->prev->next = node->next; node->next->prev = node->prev; tail->next = node; node->prev = tail; tail=tail->next; } } } /////////////////////////////////////////////////////////////////////// // get method /////////////////////////////////////////////////////////////////////// int get(int key) { if (mp.find(key)==mp.end()){ return -1; }else{ Node *tmp = mp[key]; moveNode(tmp); return mp[key]->value; } } /////////////////////////////////////////////////////////////////////// // set method /////////////////////////////////////////////////////////////////////// void set(int key, int value) { if (mp.find(key)!=mp.end()){ moveNode(mp[key]); mp[key]->value = value; }else{ if (mp.size()==cp){ mp.erase(head->key); rmNode(head); } Node * node = new Node(key,value); mp[key] = node; insertNode(node); } } }; 

我在这里有一个LRU实现。 接口遵循std :: map,所以它不应该很难使用。 另外,您可以提供一个自定义的备份处理程序,用于数据在caching中失效的情况。

 sweet::Cache<std::string,std::vector<int>, 48> c1; c1.insert("key1", std::vector<int>()); c1.insert("key2", std::vector<int>()); assert(c1.contains("key1")); 

这是我的基本的,简单的LRUcaching的实现。

 //LRU Cache #include <cassert> #include <list> template <typename K, typename V > class LRUCache { // Key access history, most recent at back typedef std::list<K> List; // Key to value and key history iterator typedef unordered_map< K, std::pair< V, typename std::list<K>::iterator > > Cache; typedef V (*Fn)(const K&); public: LRUCache( size_t aCapacity, Fn aFn ) : mFn( aFn ) , mCapacity( aCapacity ) {} //get value for key aKey V operator()( const K& aKey ) { typename Cache::iterator it = mCache.find( aKey ); if( it == mCache.end() ) //cache-miss: did not find the key { V v = mFn( aKey ); insert( aKey, v ); return v; } // cache-hit // Update access record by moving accessed key to back of the list mList.splice( mList.end(), mList, (it)->second.second ); // return the retrieved value return (it)->second.first; } private: // insert a new key-value pair in the cache void insert( const K& aKey, V aValue ) { //method should be called only when cache-miss happens assert( mCache.find( aKey ) == mCache.end() ); // make space if necessary if( mList.size() == mCapacity ) { evict(); } // record k as most-recently-used key typename std::list<K>::iterator it = mList.insert( mList.end(), aKey ); // create key-value entry, linked to the usage record mCache.insert( std::make_pair( aKey, std::make_pair( aValue, it ) ) ); } //Purge the least-recently used element in the cache void evict() { assert( !mList.empty() ); // identify least-recently-used key const typename Cache::iterator it = mCache.find( mList.front() ); //erase both elements to completely purge record mCache.erase( it ); mList.pop_front(); } private: List mList; Cache mCache; Fn mFn; size_t mCapacity; }; 

caching一个像哈希表一样支持检索值的数据结构? LRU意味着caching有一定的大小限制,我们需要定期丢弃最less使用的条目。

如果你使用指针的链表+散列表实现,你怎么能做O(1)通过键检索值?

我会用散列表实现LRUcaching,每个条目的值是值+指向prev / next条目的指针。

关于multithreading访问,我宁愿读写器locking(理想情况下由自旋锁实现,因为争用通常很快)来监视。

LRU页面replace技术:

当引用页面时,所需的页面可能在caching中。

If in the cache :我们需要把它放到caching队列的前面。

If NOT in the cache :我们把它放在caching中。 简而言之,我们在caching队列的前面添加一个新页面。 如果caching已满,即所有的帧都已满,我们从caching队列的后面移除一个页面,并将新页面添加到caching队列的前面。

 # Cache Size csize = int(input()) # Sequence of pages pages = list(map(int,input().split())) # Take a cache list cache=[] # Keep track of number of elements in cache n=0 # Count Page Fault fault=0 for page in pages: # If page exists in cache if page in cache: # Move the page to front as it is most recent page # First remove from cache and then append at front cache.remove(page) cache.append(page) else: # Cache is full if(n==csize): # Remove the least recent page cache.pop(0) else: # Increment element count in cache n=n+1 # Page not exist in cache => Page Fault fault += 1 cache.append(page) print("Page Fault:",fault) 

input输出

 Input: 3 1 2 3 4 1 2 5 1 2 3 4 5 Output: Page Fault: 10