LRU是近期最少使用的替换算法。其中有两个关键点，一个是近期，另外一个最少使用，也就是说最新更新的数据，生命值最高。在实现模拟算法的时候，可以设置一个成员变量记录访问的次数，每次访问或者设置都会加1，并把这个值设置为每个内存块的生命值，这样最新访问的内存块就不会被替换掉了。模拟的数据结构中，不会有一次访问中访问多个内存块的情况，其实也就只是根据访问的先后来进行替换。如果每次可以访问多个内存块，那么就需要统计每个内存块的访问次数。
public class LRUCache {
// mem is a [capacity][3]
// [][0]:store the value
// [][1]:store the max;
// [][2]:store the key;
private int [][]mem;
private int capacity;
private int max = 0, count = 0;
public LRUCache(int capacity) {
mem = new int[capacity][3];
this.capacity = capacity;
for (int i = 0; i < capacity; i++) {
mem[i][0] = 0;
mem[i][1] = 0;
mem[i][2] = -1;
}
}
///////////////////////////////////////////////////////////////////get
public int get(int key) {
max++;
int i = 0;
for ( i = 0; i < capacity; i++) {
if (mem[i][2] == key) {
mem[i][1] = max;
return mem[i][0];
}
}
return -1;
}
/////////////////////////////////////////////////////////////////////// set
public void set(int key, int value) {
max++;
int i = 0, index = 0, min = max;
for ( i = 0; i < capacity; i++) {
if (mem[i][2] == key) {
mem[i][0] = value;
mem[i][1] = max;
return;
}
}
if (count < capacity)
for (i = 0; i < capacity; i++) {
if (mem[i][2] == -1) {
index = i;
break;
}
}
else
for (i = 0; i < capacity; i++)
if (mem[i][1] < min) {
min = mem[i][1];
index = i;
}
mem[index][0] = value;
mem[index][1] = max;
mem[index][2] = key;
count++;
}
}
阅读(1403) | 评论(0) | 转发(0) |
