LRU算法-小Y

让我来抄一段
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

题目大意：为LRU Cache设计一个数据结构，它支持两个操作：
　　　1）get(key)：如果key在cache中，则返回对应的value值，否则返回-1

　　　2）set(key,value):如果key不在cache中，则将该(key,value)插入cache中（注意，如果cache已满，则必须把最近最久未使用的元素从cache中删除）；如果key在cache中，则重置value的值。

解题思路：题目让设计一个LRU Cache，即根据LRU算法设计一个缓存。在这之前需要弄清楚LRU算法的核心思想，LRU全称是Least
Recently Used，即最近最久未使用的意思。在操作系统的内存管理中，有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来更新和访问其中的元素。下面说一下LRU算法的核心思想，LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

推荐阅读：
LRU Cache：http://www.cnblogs.com/dolphin0520/p/3741519.html
缓存算法（页面置换算法）-FIFO、LFU、LRU：http://www.cnblogs.com/dolphin0520/p/3749259.html

整个操作其实就是hashtable的实现再加上双链表，代码没写完，犯懒了…

/**
* Your LRUCache struct will be instantiated and called as such:
* struct LRUCache* obj = lRUCacheCreate(capacity);
* int param_1 = lRUCacheGet(obj, key);
* lRUCachePut(obj, key, value);
* lRUCacheFree(obj);
*/

typedef struct {
HashTable *ht;
} LRUCache;

typedef struct {
int key;
int value;
Bucket *next;
} Bucket;

typedef struct {
int num;
Bucket *bucket;
} HashTable;

HashTable* ht_create(int capacity){
HashTable *ht;
ht = (HashTable *)malloc(sizeof(HashTable));
ht->num = capacity;
ht->bucket = (Bucket *)malloc(capacity * sizeof(Bucket));
bzero(ht->bucket, sizeof(capacity * sizeof(Bucket)));
return ht;
}

int ht_get(HashTable *ht, int key){
int n = key%ht->num;
Bucket b = ht->bucket[n];
while(b->key != key && b != NULL){
b = b->next;
}
return b->key;
}

int ht_put(HashTable *ht, int key, int value){
int n = key%ht->num;
Bucket *b = ht->bucket[n];
if(b->key){
Bucket *next = (Bucket *)malloc(sizeof(Bucket));
next->key = key;
next->value = value;
while(b->next != NULL){
b = b->next;
}
b->next = next;
}else{
b->key = key;
b->value = value;
}
return n;
}

LRUCache* lRUCacheCreate(int capacity) {
LRUCache *c;
c = (LURCache *)malloc(sizeof(LURCache));
c->ht = ht_create(capacity);
return c;
}

int lRUCacheGet(LRUCache* obj, int key) {
return ht_get(obj->ht, key);
}

void lRUCachePut(LRUCache* obj, int key, int value) {
return ht_put(obj->ht, key, value);
}

void lRUCacheFree(LRUCache* obj) {

}

转载请注明：小Y » LRU算法

LRU算法

相关推荐

评论抢沙发

相关推荐

评论 抢沙发

评论抢沙发