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
