이 기사에서 언급 한 Twoqueues 캐시 모델은 메모리의 데이터 캐시 모델을 나타냅니다.
어떤 언어에 관계없이, 반복적 인 작업과 읽기를 피하기 위해 일부 데이터를 메모리에 넣어야 할 수도 있습니다. 가장 일반적인 시나리오는 jQuery 선택기입니다. 일부 DOM 요소의 선택은 매우 시간이 많이 걸립니다. 우리는 호출 할 때마다 Dom 트리를 다시 전환하지 않고도 이러한 데이터를 캐시하기를 희망합니다.
저장하십시오. 그러나 수량이 있어야합니다! 모든 역사적 데이터를 메모리에 넣을 수는 없습니다. 결국, 현재 메모리 용량은 여전히 매우 불쌍합니다. 메모리가 충분히 크면 이론적으로 각 스레드에 의해 할당 된 메모리는 여전히 제한적입니다.
문제는 어떻게 유용한 데이터를 효율적으로 캐시 할 수 있습니까? 여기에는 제거 알고리즘이 포함되며 유용한 데이터를 보존하려면 정크 데이터를 제거해야합니다.
몇 가지 일반적인 아이디어가 있습니다.
FIFO : 최초의 최초의 대기열 인 최초의 캐시 데이터이며 먼저 제거되었습니다. 이 모델은 유명한 jQuery 프레임 워크 내에서 사용됩니다.
LRU : 이중 연결 목록 구조, 새로운 데이터가 저장 될 때마다 링크 된 목록의 헤더에 직접 배치됩니다. 매번 액세스 한 데이터는 링크 된 목록의 헤더로 전송됩니다. 이러한 방식으로 링크 된 목록의 끝에있는 데이터는 최근에 사용되지 않았으며 제거 될 것입니다.
2queues : FIFO+ LRU. FIFO는 주로 처음으로 저장된 데이터를 저장하고 LRU는 적어도 두 번 사용 된 핫스팟 데이터를 저장합니다. 이 알고리즘은 적대율이 높고 적응력이 강하며 복잡성이 낮습니다.
다른 제거 알고리즘이 많이 있지만 실제로는 더 많이 사용되는 두 가지 유형 만 있습니다. 알고리즘은 복잡하지 않고 구현하기 쉽고 높은 실행 효율성 및 캐시 적중률은 대부분의 경우에 허용됩니다. 결국, 캐시 알고리즘에는 CPU 소비가 필요합니다. 너무 복잡하다면 적중률이 향상되었지만 손실의 가치가 없습니다. 캐시에서 데이터를 가져 오면 원래 위치에서 가져 오는 것보다 시간이 더 걸립니다. 캐시 사용은 무엇입니까?
나는 특정 이론에 대해 이야기하지 않을 것입니다. 온라인이 있지만 이해하지 못합니다. 오늘은 Twoqueues 캐시 모델의 JavaScript 버전을 공유하겠습니다.
먼저 사용하는 방법에 대해 이야기 해 봅시다. 매우 간단합니다.
기본 사용법은 다음과 같습니다.
[/암호]
var tq = inittwoqueues (10);
tq.set ( "키", "값");
tq.get ( "키");
[/암호]
초기화 할 때는 캐시 용량 만 지정하십시오. FIFO+LRU가 내부적으로 구현되므로 실제 용량은 지정된 용량의 두 배입니다. 위의 예는 실제로 20을 저장할 수있는 10 (키 값 쌍)을 지정합니다.
용량 크기는 실제 응용 프로그램 시나리오에 따라 결정해야합니다. 너무 작 으면 적중률이 낮고 효율이 낮고 극도는 반대이며 직접 측정해야합니다.
개발 과정에서 캐시 효과를 검토하기 위해 캐시 풀을 개발 버전으로 초기화 할 수 있습니다.
코드 사본은 다음과 같습니다.
var tq = inittwoqueues (10, true);
tq.hitratio ();
끝에 매개 변수를 추가하고 사실입니다. 이러한 방식으로 초기화 된 캐시 풀은 적중률을 자동으로 계산하고 hitratio 방법을 통해 적중률을 얻을 수 있습니다. 이 매개 변수가 추가되지 않으면 Hitratio 메소드에 의해 얻은 적중률은 항상 0입니다.
통계 적중률은 확실히 리소스를 소비 할 것이므로 생산 환경에서 켜지는 것이 좋습니다.
코드를 공유 할 시간입니다.
코드 사본은 다음과 같습니다.
(기능 (수출) {
/**
* 상속을위한 순수한 클래스
* @constructor
*/
함수 fn () {}
fn.prototype = 제거. 프로로 타입;
/**
* 링크 된 목록을 기반으로하는 캐시 제거 알고리즘의 부모 클래스
* @param maxlength 캐시 용량
* @constructor
*/
함수 제거 (maxlength) {
this.container = {};
this.length = 0;
this.maxlength = maxlength || 30;
this.linkhead = this.buildnode ( "", "");
this.linkhead.head = true;
this.linktail = this.buildnode ( "", "");
this.linktail.tail = true;
this.linkhead.next = this.linktail;
this.linktail.prev = this.linkhead;
}
제거 .prototype.get = function (key) {
새 오류를 던지십시오 ( "이 방법은 재정의되어야합니다!");
};
제거 .prototype.set = function (키, 값) {
새 오류를 던지십시오 ( "이 방법은 재정의되어야합니다!");
};
/**
* 링크 된 목록에서 노드를 만듭니다
* @param 데이터 노드에 포함 된 데이터, 즉 캐시 된 데이터 값
* @param 키 노드의 고유 식별자, 즉 캐시 된 키
* @returns {{}}
*/
제거 .prototype.buildnode = function (data, key) {
var 노드 = {};
node.data = 데이터;
node.key = 키;
node.use = 0;
리턴 노드;
};
/**
* 링크 된 목록의 헤더에서 노드가 나타납니다.
* @returns {*}
*/
제거 .prototype.shift = function () {
var node = null;
if (! this.linkhead.next.tail) {
노드 = this.linkhead.next;
this.linkhead.next = node.next;
node.next.prev = this.linkhead;
this.container [node.key];
this.length--;
}
리턴 노드;
};
/**
* 링크 된 목록의 헤더에서 노드 삽입
* @param 노드 노드 객체
* @returns {*}
*/
제거 .prototype.unshift = function (노드) {
node.next = this.linkhead.next;
this.linkhead.next.prev = 노드;
this.linkhead.next = 노드;
node.prev = this.linkhead;
this.container [node.key] = 노드;
this.length ++;
리턴 노드;
};
/**
* 링크 된 목록 끝에서 노드 삽입
* @param 노드 노드 객체
* @returns {*}
*/
제거 .prototype.append = function (노드) {
this.linktail.prev.next = 노드;
node.prev = this.linktail.prev;
node.next = this.linktail;
this.linktail.prev = 노드;
this.container [node.key] = 노드;
this.length ++;
리턴 노드;
};
/**
* 링크 된 목록 끝에서 노드가 나타납니다.
* @returns {*}
*/
제거 .prototype.pop = function () {
var node = null;
if (! this.linktail.prev.head) {
노드 = this.linktail.prev;
node.prev.next = this.linktail;
this.linktail.prev = node.prev;
this.container [node.key];
this.length--;
}
리턴 노드;
};
/**
* 링크 된 목록에서 지정된 노드를 제거하십시오
* @param 노드 노드 객체
* @returns {*}
*/
제거 .prototype.remove = function (노드) {
node.prev.next = node.next;
node.next.prev = node.prev;
this.container [node.key];
this.length--;
리턴 노드;
};
/**
* 노드에 액세스 할 때 수행 해야하는 처리는 노드를 링크 된 목록의 헤더로 이동하는 것입니다.
* @param 노드
*/
제거 .prototype.use = function (노드) {
this.remove (노드);
this.unshift (노드);
};
/**
* LRU 캐시 제거 알고리즘 구현
* @constructor
*/
함수 lru () {
제거. Apply (이것, 인수);
}
lru.prototype = 새로운 fn ();
lru.prototype.get = function (key) {
var 노드 = 정의되지 않은;
노드 = this.container [키];
if (노드) {
this.use (노드);
}
리턴 노드;
};
lru.prototype.set = function (키, 값) {
var node = this.buildnode (값, 키);
if (this.length === this.maxlength) {
this.pop ();
}
this.unshift (노드);
};
/**
* FIFO 캐시 제거 알고리즘 구현
* @constructor
*/
함수 fifo () {
제거. Apply (이것, 인수);
}
fifo.prototype = new fn ();
fifo.prototype.get = function (key) {
var 노드 = 정의되지 않은;
노드 = this.container [키];
리턴 노드;
};
fifo.prototype.set = function (키, 값) {
var node = this.buildnode (값, 키);
if (this.length === this.maxlength) {
this.shift ();
}
this.append (노드);
};
/**
* LRU 및 FIFO 알고리즘 캡슐화는 새로운 2queues 캐시 제거 알고리즘이되었습니다.
* @param maxlength
* @constructor
*/
기능 에이전트 (maxlength) {
this.getCount = 0;
this.hitcount = 0;
this.lir = new Fifo (maxlength);
this.hir = new lru (maxlength);
}
agent.prototype.get = function (key) {
var 노드 = 정의되지 않은;
node = this.lir.get (키);
if (노드) {
node.use ++;
if (node.use> = 2) {
this.lir.remove (노드);
this.hir.set (node.key, node.data);
}
}또 다른{
node = this.hir.get (키);
}
리턴 노드;
};
agent.prototype.getx = function (key) {
var 노드 = 정의되지 않은;
this.getCount ++;
노드 = this.get (키);
if (노드) {
this.hitcount ++;
}
리턴 노드;
};
agent.prototype.set = function (키, 값) {
var node = null;
노드 = this.lir.container [key] || this.hir.container [키];
if (노드) {
node.data = 값;
}또 다른{
this.lir.set (키, 값);
}
};
/**
* 적중률을 얻으십시오
* @returns {*}
*/
agent.prototype.hitratio = function () {
var ret = this.getCount;
if (ret) {
ret = this.hitcount / this.getCount;
}
반품 반환;
};
/**
* 외부 인터페이스
* @param maxlength 캐시 용량
* @param dev 개발 환경이든 개발 환경은 적중률을 계산합니다. 그렇지 않으면 그렇지 않습니다.
* @returns {{get, set : function, hitratio : function}}
*/
Exports.inittwoqueues = function (maxlength, dev) {
var api = 새로운 에이전트 (maxlength);
반품 {
get : (function () {
if (dev) {
반환 기능 (키) {
var ret = api.getx (키);
Ret && ret.data를 반환합니다.
};
}또 다른{
반환 기능 (키) {
var ret = api.get (키);
Ret && ret.data를 반환합니다.
};
}
} ()),
set : function () {
API.SET.Apply (API, 인수);
},
hitratio : function () {
반환 api.hitratio.apply (API, Arguments);
}
};
};
}(이것));
마지막으로 캐시 알고리즘을 실제 애플리케이션 시나리오와 결합해야한다는 것을 다시 상기시켜 드리고자합니다. 보편적 인 알고리즘이 없으면 최고의 알고리즘이 최고입니다!