JavaScriptはTwoQuesキャッシュモデルを実現します.
39201 ワード
本論文ではTwoQuesキャッシュモデルを指し、データのメモリにおけるキャッシュモデルを指す.
どの言語でも、一部のデータをメモリに入れて、重複演算や読み込みを避ける必要があります.最も一般的なシーンはJQueryセレクタです.一部のDom元素の選択はとても時間がかかります.これらのデータをキャッシュしてほしいです.毎回呼び出して、Domツリーを遍歴する必要がないです.
預けておけばいいですが、量がありますよね.全部の履歴データをメモリに入れることはできません.今のメモリの容量はまだかなり気の毒です.メモリが大きいとしても、理論的にスレッドごとに割り当てられたメモリは制限があります.
では、どうやって効率的にデータをキャッシュすることができますか?これは廃棄アルゴリズムに関連しています.ごみデータを淘汰してこそ、有用なデータを維持することができます.
よく使われる考えは以下の通りです.
FIFO:先进国の列で、先にキャッシュしたデータは一番早く淘汰されました.有名なJQueryフレームの中でこのようなモデルが使われています.
LRU:ダブルチェーン構造で、新しいデータが入るたびに、直接チェーンの先に置きます.毎回訪問されるデータは、チェーンの頭にも移行します.そうすると、チェーンの最後のデータは最近使われていないもので、淘汰されます.
TwoQues:FIFO+LRU、FIFOは主に最初に入れたデータを保管しています.LRUには少なくとも二回使用したホットスポットデータが格納されています.このアルゴリズムは命中率が高く、適応性が強く、複雑度が低いです.
他の淘汰アルゴリズムはまだたくさんありますが、実際に使うものが多いのはこの二つです.彼ら自身のアルゴリズムは複雑ではないので、実現しやすく、実行効率が高く、キャッシュされた命中率も多くの場合に受け入れられます.キャッシュアルゴリズムもCPUを消費する必要があります.複雑すぎると命中率が高くなりますが、引き合わないです.考えてみてください.キャッシュからデータを取ると、元の位置から取るよりも時間がかかります.キャッシュはどうなりますか?
具体的な理論は多くなくて言いました.ネット上にはよく分かりません.今日はJavaScript版のTwoQuesキャッシュモデルがあります.
まず使い方を教えてください.簡単です.
基本的な使い方は以下の通りです.
容量の大きさは実際の応用シーンによって決まる必要があります.あまりにも小さい命中率は低く、あまりにも効率が高く、物が極端に反って、自分で測定する必要があります.
開発中にキャッシュの効果を審査するために、キャッシュを開発版に初期化することができます.
統計命中率は必ず資源を消耗しますので、生産環境ではオープンすることを勧めません.
コードを共有する時間です.
最後に、もう一度注意してください.キャッシュアルゴリズムは実際のアプリケーションシーンと結合する必要があります.万能アルゴリズムがなく、適切なものが一番いいです.
どの言語でも、一部のデータをメモリに入れて、重複演算や読み込みを避ける必要があります.最も一般的なシーンはJQueryセレクタです.一部のDom元素の選択はとても時間がかかります.これらのデータをキャッシュしてほしいです.毎回呼び出して、Domツリーを遍歴する必要がないです.
預けておけばいいですが、量がありますよね.全部の履歴データをメモリに入れることはできません.今のメモリの容量はまだかなり気の毒です.メモリが大きいとしても、理論的にスレッドごとに割り当てられたメモリは制限があります.
では、どうやって効率的にデータをキャッシュすることができますか?これは廃棄アルゴリズムに関連しています.ごみデータを淘汰してこそ、有用なデータを維持することができます.
よく使われる考えは以下の通りです.
FIFO:先进国の列で、先にキャッシュしたデータは一番早く淘汰されました.有名なJQueryフレームの中でこのようなモデルが使われています.
LRU:ダブルチェーン構造で、新しいデータが入るたびに、直接チェーンの先に置きます.毎回訪問されるデータは、チェーンの頭にも移行します.そうすると、チェーンの最後のデータは最近使われていないもので、淘汰されます.
TwoQues:FIFO+LRU、FIFOは主に最初に入れたデータを保管しています.LRUには少なくとも二回使用したホットスポットデータが格納されています.このアルゴリズムは命中率が高く、適応性が強く、複雑度が低いです.
他の淘汰アルゴリズムはまだたくさんありますが、実際に使うものが多いのはこの二つです.彼ら自身のアルゴリズムは複雑ではないので、実現しやすく、実行効率が高く、キャッシュされた命中率も多くの場合に受け入れられます.キャッシュアルゴリズムもCPUを消費する必要があります.複雑すぎると命中率が高くなりますが、引き合わないです.考えてみてください.キャッシュからデータを取ると、元の位置から取るよりも時間がかかります.キャッシュはどうなりますか?
具体的な理論は多くなくて言いました.ネット上にはよく分かりません.今日はJavaScript版のTwoQuesキャッシュモデルがあります.
まず使い方を教えてください.簡単です.
基本的な使い方は以下の通りです.
1 var tq = initTwoQueues(10);
2 tq.set("key", "value");
3 tq.get("key");容量の大きさは実際の応用シーンによって決まる必要があります.あまりにも小さい命中率は低く、あまりにも効率が高く、物が極端に反って、自分で測定する必要があります.
開発中にキャッシュの効果を審査するために、キャッシュを開発版に初期化することができます.
1 var tq = initTwoQueues(10, true);
2 tq.hitRatio();統計命中率は必ず資源を消耗しますので、生産環境ではオープンすることを勧めません.
コードを共有する時間です.
1 (function(exports){
2
3 /**
4 *
5 * @constructor
6 */
7 function Fn(){}
8 Fn.prototype = Elimination.prototype;
9
10 /**
11 *
12 * @param maxLength
13 * @constructor
14 */
15 function Elimination(maxLength){
16 this.container = {};
17 this.length = 0;
18 this.maxLength = maxLength || 30;
19 this.linkHead = this.buildNode("", "");
20 this.linkHead.head = true;
21 this.linkTail = this.buildNode("", "");
22 this.linkTail.tail = true;
23
24 this.linkHead.next = this.linkTail;
25 this.linkTail.prev = this.linkHead;
26 }
27
28 Elimination.prototype.get = function(key){
29 throw new Error("This method must be override!");
30 };
31
32 Elimination.prototype.set = function(key, value){
33 throw new Error("This method must be override!");
34 };
35
36 /**
37 *
38 * @param data ，
39 * @param key ，
40 * @returns {{}}
41 */
42 Elimination.prototype.buildNode = function(data, key){
43 var node = {};
44 node.data = data;
45 node.key = key;
46 node.use = 0;
47
48 return node;
49 };
50
51 /**
52 *
53 * @returns {*}
54 */
55 Elimination.prototype.shift = function(){
56 var node = null;
57 if(!this.linkHead.next.tail){
58 node = this.linkHead.next;
59 this.linkHead.next = node.next;
60 node.next.prev = this.linkHead;
61
62 delete this.container[node.key];
63 this.length--;
64 }
65
66 return node;
67 };
68
69 /**
70 *
71 * @param node
72 * @returns {*}
73 */
74 Elimination.prototype.unshift = function(node){
75 node.next = this.linkHead.next;
76 this.linkHead.next.prev = node;
77
78 this.linkHead.next = node;
79 node.prev = this.linkHead;
80
81 this.container[node.key] = node;
82 this.length++;
83
84 return node;
85 };
86
87 /**
88 *
89 * @param node
90 * @returns {*}
91 */
92 Elimination.prototype.append = function(node){
93
94 this.linkTail.prev.next = node;
95 node.prev = this.linkTail.prev;
96
97 node.next = this.linkTail;
98 this.linkTail.prev = node;
99
100 this.container[node.key] = node;
101 this.length++;
102
103 return node;
104 };
105
106 /**
107 *
108 * @returns {*}
109 */
110 Elimination.prototype.pop = function(){
111 var node = null;
112
113 if(!this.linkTail.prev.head){
114 node = this.linkTail.prev;
115 node.prev.next = this.linkTail;
116 this.linkTail.prev = node.prev;
117
118 delete this.container[node.key];
119 this.length--;
120 }
121
122 return node;
123 };
124
125 /**
126 *
127 * @param node
128 * @returns {*}
129 */
130 Elimination.prototype.remove = function(node){
131 node.prev.next = node.next;
132 node.next.prev = node.prev;
133
134 delete this.container[node.key];
135 this.length--;
136
137 return node;
138 };
139
140 /**
141 * ，
142 * @param node
143 */
144 Elimination.prototype.use = function(node){
145 this.remove(node);
146 this.unshift(node);
147 };
148
149
150 /**
151 * LRU
152 * @constructor
153 */
154 function LRU(){
155 Elimination.apply(this, arguments);
156 }
157 LRU.prototype = new Fn();
158
159 LRU.prototype.get = function(key){
160 var node = undefined;
161
162 node = this.container[key];
163
164 if(node){
165 this.use(node);
166 }
167
168 return node;
169 };
170
171 LRU.prototype.set = function(key, value){
172 var node = this.buildNode(value, key);
173
174 if(this.length === this.maxLength){
175 this.pop();
176 }
177
178 this.unshift(node);
179 };
180
181
182 /**
183 * FIFO
184 * @constructor
185 */
186 function FIFO(){
187 Elimination.apply(this, arguments);
188 }
189 FIFO.prototype = new Fn();
190
191 FIFO.prototype.get = function(key){
192 var node = undefined;
193
194 node = this.container[key];
195
196 return node;
197 };
198
199 FIFO.prototype.set = function(key, value){
200 var node = this.buildNode(value, key);
201
202 if(this.length === this.maxLength){
203 this.shift();
204 }
205
206 this.append(node);
207 };
208
209
210 /**
211 * LRU、FIFO ， twoqueues
212 * @param maxLength
213 * @constructor
214 */
215 function Agent(maxLength){
216 this.getCount = 0;
217 this.hitCount = 0;
218 this.lir = new FIFO(maxLength);
219 this.hir = new LRU(maxLength);
220 }
221
222 Agent.prototype.get = function(key){
223 var node = undefined;
224
225 node = this.lir.get(key);
226
227 if(node){
228 node.use++;
229 if(node.use >= 2){
230 this.lir.remove(node);
231 this.hir.set(node.key, node.data);
232 }
233 }else{
234 node = this.hir.get(key);
235 }
236
237 return node;
238 };
239
240 Agent.prototype.getx = function(key){
241 var node = undefined;
242
243 this.getCount++;
244
245 node = this.get(key);
246
247 if(node){
248 this.hitCount++;
249 }
250
251 return node;
252 };
253
254 Agent.prototype.set = function(key, value){
255 var node = null;
256
257 node = this.lir.container[key] || this.hir.container[key];
258
259 if(node){
260 node.data = value;
261 }else{
262 this.lir.set(key, value);
263 }
264 };
265
266 /**
267 *
268 * @returns {*}
269 */
270 Agent.prototype.hitRatio = function(){
271 var ret = this.getCount;
272
273 if(ret){
274 ret = this.hitCount / this.getCount;
275 }
276
277 return ret;
278 };
279
280 /**
281 *
282 * @param maxLength
283 * @param dev ， ，
284 * @returns {{get, set: Function, hitRatio: Function}}
285 */
286 exports.initTwoQueues = function(maxLength, dev){
287
288 var api = new Agent(maxLength);
289
290 return {
291 get: (function(){
292 if(dev){
293 return function(key){
294 var ret = api.getx(key);
295 return ret && ret.data;
296 };
297 }else{
298 return function(key){
299 var ret = api.get(key);
300 return ret && ret.data;
301 };
302 }
303 }()),
304 set: function(){
305 api.set.apply(api, arguments);
306 },
307 hitRatio: function(){
308 return api.hitRatio.apply(api, arguments);
309 }
310 };
311
312 };
313
314
315 }(this));最後に、もう一度注意してください.キャッシュアルゴリズムは実際のアプリケーションシーンと結合する必要があります.万能アルゴリズムがなく、適切なものが一番いいです.