Nodejs LRU 알고리즘 을 기반 으로 한 캐 시 처리 예제
LRU 는 Least Recently Used 의 줄 임 말로,최근 최소 페이지 교체 알고리즘 을 사용 하 는 것 은 가상 페이지 식 저장 관리 서 비 스 를 위 한 것 으로,페이지 가 메모리 에 들 어간 후의 사용 상황 에 따라 결정 된다.페이지 별 향후 사용 상황 을 예측 할 수 없어'최근 의 과거'를'최근 의 미래'의 근사 성 으로 활용 할 수 밖 에 없 기 때문에 LRU 알고리즘 은 최근 가장 오래 사용 하지 않 은 페이지 를 탈락 시 키 는 것 이다.
현재 사용 하고 있 는 각 페이지 의 페이지 번 호 를 특별한 스 택 으로 저장 할 수 있 습 니 다.새로운 프로 세 스 가 한 페이지 에 접근 할 때 이 페이지 번 호 를 스 택 꼭대기 에 누 르 고 다른 페이지 번 호 는 스 택 밑 으로 이동 합 니 다.메모리 가 부족 하면 스 택 밑 의 페이지 번 호 를 제거 합 니 다.이렇게 해서 스 택 지붕 은 최신 방문 한 페이지 의 번호 이 고 스 택 바닥 은 최근 에 가장 오래 방문 하지 않 은 페이지 의 페이지 번호 입 니 다.
다음 시퀀스 를 입력 할 때:4,7,0,7,1,0,1,2,1,2,6
결 과 는:
4
4 7
4 7 0
4 0 7
4 0 7 1
4 7 1 0
4 7 0 1
4 7 0 1 2
4 7 0 2 1
4 7 0 1 2
7 0 1 2 6
Node.js 에 적용 되 는 LRU 캐 시 입 니 다.capacity 는 캐 시 용량 이 고 0 일 때 일반 캐 시 를 구성 합 니 다.
function CacheLRU(capacity) {
/* Buffer LRU ,capacity , 0 。
myCache = new CacheLRU(capacity); //
myCache.get(key); // key
myCache.put(key, value); // key
myCache.remove(key); // key
myCache.removeAll(); //
myCache.info(); // myCache
LRU : key hash , get put , key ( )。 put , ( ) 。
hash key, hash , 。 。
*/
this.capacity = capacity || Number.MAX_VALUE;
this.data = {};
this.hash = {};
this.linkedList = {
length: 0,
head: null,
end: null
}
if (capacity <= 0) this.capacity = Number.MAX_VALUE;
};
CacheLRU.prototype.get = function(key) {
key = '_' + key;
var lruEntry = this.hash[key];
if (!lruEntry) return;
refresh(this.linkedList, lruEntry);
return JSON.parse(this.data[key].toString());
};
CacheLRU.prototype.put = function(key, value) {
key = '_' + key;
var lruEntry = this.hash[key];
if (value === undefined) return this;
if (!lruEntry) {
this.hash[key] = {key: key};
this.linkedList.length += 1;
lruEntry = this.hash[key];
}
refresh(this.linkedList, lruEntry);
this.data[key] = new Buffer(JSON.stringify(value));
if (this.linkedList.length > this.capacity) this.remove(this.linkedList.end.key.slice(1));
return this;
};
CacheLRU.prototype.remove = function(key) {
key = '_' + key;
var lruEntry = this.hash[key];
if (!lruEntry) return this;
if (lruEntry === this.linkedList.head) this.linkedList.head = lruEntry.p;
if (lruEntry === this.linkedList.end) this.linkedList.end = lruEntry.n;
link(lruEntry.n, lruEntry.p);
delete this.hash[key];
delete this.data[key];
this.linkedList.length -= 1;
return this;
};
CacheLRU.prototype.removeAll = function() {
this.data = {};
this.hash = {};
this.linkedList = {
length: 0,
head: null,
end: null
}
return this;
};
CacheLRU.prototype.info = function() {
var size = 0,
data = this.linkedList.head;
while (data){
size += this.data[data.key].length;
data = data.p;
}
return {
capacity: this.capacity,
length: this.linkedList.length,
size: size
};
};
// , get put key head,
function refresh(linkedList, entry) {
if (entry != linkedList.head) {
if (!linkedList.end) {
linkedList.end = entry;
} else if (linkedList.end == entry) {
linkedList.end = entry.n;
}
link(entry.n, entry.p);
link(entry, linkedList.head);
linkedList.head = entry;
linkedList.head.n = null;
}
}
// ,
function link(nextEntry, prevEntry) {
if (nextEntry != prevEntry) {
if (nextEntry) nextEntry.p = prevEntry;
if (prevEntry) prevEntry.n = nextEntry;
}
}
module.exports = CacheLRU;
// test:
/*var user = new CacheLRU(5);
user.put('user1', {name:'admin', age: 30});
user.put('user2', {name:'user', age: 31});
user.put('user3', {name:'guest', age: 32});
user.put('user4', {name:'guest', age: 34});
user.put('user5', {name:'guest', age: 35});
console.log(user.get('user1'));
console.log(user.get('user2'));
console.log(user.get('user3'));
user.put('user6', {name:'guest', age: 36});
console.log(user.info());*/
LRU 알고리즘 은 브 라 우 저 를 만 들 거나 타 오 바 오 클 라 이언 트 와 유사 한 응용 을 하려 면 이 원 리 를 사용 해 야 합 니 다.브 라 우 저 는 웹 페이지 를 탐색 할 때 다운로드 한 그림 을 이 컴퓨터 의 한 폴 더 에 임시로 저장 하고 다음 에 다시 방문 할 때 이 컴퓨터 의 임시 폴 더 에서 직접 읽 는 것 을 잘 알 고 있 습 니 다.그러나 그림 을 저장 하 는 임시 폴 더 는 일정한 용량 제한 이 있 습 니 다.웹 페이지 를 너무 많이 찾 으 면 가장 자주 사용 하지 않 는 그림 을 삭제 하고 최근 에 가장 오래 사용 한 그림 만 유지 합 니 다.이때 LRU 알고리즘 을 사용 할 수 있 습 니 다.이때 위의 알고리즘 에 있 는 이 특수 한 스 택 은 페이지 의 번호 가 아니 라 모든 그림 의 번호 나 크기 입 니 다.그래서 위 에 있 는 이 스 택 의 요 소 는 모두 Object 류 로 표시 합 니 다.그러면 이 스 택 은 맞 게 저장 할 수 있 습 니 다.본 논문 에서 말 한 것 이 여러분 의 nodejs 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Nodejs LRU 알고리즘 을 기반 으로 한 캐 시 처리 예제LRU 알고리즘 은 브 라 우 저 를 만 들 거나 타 오 바 오 클 라 이언 트 와 유사 한 응용 을 하려 면 이 원 리 를 사용 해 야 합 니 다.브 라 우 저 는 웹 페이지 를 탐색 할 때 다운로드 한 그림 을 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.