Model cache Twoqueues yang disebutkan dalam artikel ini mengacu pada model cache data dalam memori.
Tidak peduli bahasa apa, Anda mungkin perlu memasukkan beberapa data dalam memori untuk menghindari operasi dan membaca yang berulang. Skenario yang paling umum adalah pemilih jQuery. Pemilihan beberapa elemen DOM sangat memakan waktu. Kami berharap dapat menyimpan data ini tanpa harus menebus kembali pohon DOM setiap kali kami menelepon.
Simpan, tetapi harus ada kuantitas! Anda tidak dapat menempatkan semua data historis dalam memori. Bagaimanapun, kapasitas memori saat ini masih cukup menyedihkan. Bahkan jika memori cukup besar, memori yang dialokasikan oleh masing -masing utas secara teori masih terbatas.
Jadi pertanyaannya adalah, bagaimana kita bisa menyimpan data yang benar -benar berguna secara efisien? Ini melibatkan algoritma eliminasi, dan data sampah perlu dihilangkan untuk mempertahankan data yang bermanfaat.
Ada beberapa ide umum:
FIFO: Ini adalah antrian pertama di-pertama, data cache pertama, dan dieliminasi terlebih dahulu. Model ini digunakan dalam kerangka jQuery yang terkenal.
LRU: Struktur daftar yang terkait ganda, setiap kali data baru disimpan, ditempatkan langsung di header daftar tertaut; Data yang diakses setiap kali juga ditransfer ke header daftar yang ditautkan. Dengan cara ini, data di akhir daftar tertaut adalah sesuatu yang belum digunakan baru -baru ini dan akan dihilangkan.
Twoqueues: FIFO+ LRU. FIFO terutama menyimpan data yang disimpan untuk pertama kalinya, dan LRU menyimpan data hot spot yang telah digunakan setidaknya dua kali. Algoritma ini memiliki tingkat hit yang tinggi, kemampuan beradaptasi yang kuat dan kompleksitas yang rendah.
Ada banyak algoritma eliminasi lainnya, tetapi hanya ada dua jenis yang lebih banyak digunakan dalam praktik. Karena algoritma mereka tidak kompleks, mudah diimplementasikan, efisiensi eksekusi yang tinggi, dan laju hit cache dapat diterima di sebagian besar kesempatan. Bagaimanapun, algoritma cache juga membutuhkan konsumsi CPU. Jika terlalu rumit, meskipun tingkat hit telah ditingkatkan, itu tidak sepadan dengan kerugiannya. Bayangkan saja, jika Anda mengambil data dari cache, dibutuhkan lebih banyak waktu daripada mengambil dari lokasi asli. Apa gunanya cache?
Saya tidak akan berbicara tentang teori khusus. Ada beberapa online, tetapi saya tidak banyak memahaminya. Hari ini saya akan berbagi dengan Anda versi JavaScript dari Twoqueues Cache Model.
Mari kita bicara tentang cara menggunakannya terlebih dahulu, ini sangat sederhana.
Metode penggunaan dasar adalah sebagai berikut:
[/kode]
var tq = inittwoqueues (10);
tq.set ("kunci", "nilai");
tq.get ("kunci");
[/kode]
Saat menginisialisasi, cukup tentukan kapasitas cache. Perlu dicatat bahwa karena FIFO+LRU diimplementasikan secara internal, kapasitas aktual adalah dua kali kapasitas yang ditentukan. Contoh di atas menentukan 10 (pasangan nilai kunci), yang sebenarnya dapat menyimpan 20.
Ukuran kapasitas perlu ditentukan sesuai dengan skenario aplikasi yang sebenarnya. Jika terlalu kecil, laju hit rendah, efisiensinya rendah, dan ekstremnya sebaliknya, dan Anda perlu mengukurnya sendiri.
Selama proses pengembangan, untuk meninjau efek cache, kumpulan cache dapat diinisialisasi ke dalam versi pengembangan:
Salinan kode adalah sebagai berikut:
var tq = inittwoqueues (10, true);
tq.hitratio ();
Cukup tambahkan parameter ke akhir dan benar. Kumpulan cache yang diinisialisasi dengan cara ini akan secara otomatis menghitung tingkat hit, dan laju hit dapat diperoleh melalui metode Hitratio. Jika parameter ini tidak ditambahkan, laju hit yang diperoleh dengan metode HitRatio selalu 0.
Tingkat hit statistik pasti akan mengkonsumsi sumber daya, sehingga tidak disarankan untuk menghidupkan di lingkungan produksi.
Saatnya membagikan kode:
Salinan kode adalah sebagai berikut:
(fungsi (ekspor) {
/**
* Kelas murni untuk warisan
* @constructor
*/
function fn () {}
Fn.prototype = elimination.prototype;
/**
* Kelas induk algoritma eliminasi cache berdasarkan daftar tertaut
* Kapasitas cache @param maxlength
* @constructor
*/
eliminasi fungsi (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;
}
Elimination.prototype.get = function (key) {
Lemparkan kesalahan baru ("Metode ini harus ditimpa!");
};
Elimination.prototype.set = function (tombol, value) {
Lemparkan kesalahan baru ("Metode ini harus ditimpa!");
};
/**
* Buat node di daftar tertaut
* @param Data Data yang terkandung dalam node, yaitu, nilai data yang di -cache
* Kunci @param Pengidentifikasi unik dari node, yaitu, kunci yang di -cache
* @returns {{}}
*/
Elimination.prototype.buildnode = fungsi (data, kunci) {
var node = {};
node.data = data;
node.key = key;
node.use = 0;
return node;
};
/**
* Node muncul dari header daftar tertaut
* @returns {*}
*/
Elimination.prototype.shift = function () {
var node = null;
if (! this.linkhead.next.tail) {
node = this.linkhead.next;
this.linkhead.next = node.next;
node.next.prev = this.linkhead;
hapus this.container [node.key];
this.length--;
}
return node;
};
/**
* Masukkan simpul dari header daftar tertaut
* Objek simpul simpul @param
* @returns {*}
*/
Elimination.prototype.unshift = function (node) {
node.next = this.linkhead.next;
this.linkhead.next.prev = node;
this.linkhead.next = node;
node.prev = this.linkhead;
this.container [node.key] = node;
this.length ++;
return node;
};
/**
* Masukkan simpul dari ujung daftar yang ditautkan
* Objek simpul simpul @param
* @returns {*}
*/
Elimination.prototype.append = function (node) {
this.linktail.prev.next = node;
node.prev = this.linktail.prev;
node.next = this.linktail;
this.linktail.prev = node;
this.container [node.key] = node;
this.length ++;
return node;
};
/**
* Sebuah simpul muncul dari ujung daftar yang ditautkan
* @returns {*}
*/
Elimination.prototype.pop = function () {
var node = null;
if (! this.linktail.prev.head) {
node = this.linktail.prev;
node.prev.next = this.linktail;
this.linktail.prev = node.prev;
hapus this.container [node.key];
this.length--;
}
return node;
};
/**
* Hapus simpul yang ditentukan dari daftar tertaut
* Objek simpul simpul @param
* @returns {*}
*/
Elimination.prototype.remove = function (node) {
node.prev.next = node.next;
node.next.prev = node.prev;
hapus this.container [node.key];
this.length--;
return node;
};
/**
* Pemrosesan yang harus dilakukan ketika sebuah simpul diakses adalah untuk memindahkan node ke header daftar yang ditautkan
* @param node
*/
Elimination.prototype.use = function (node) {
this.remove (node);
this.unshift (node);
};
/**
* Implementasi algoritma eliminasi cache LRU
* @constructor
*/
fungsi lru () {
Eliminasi.Apply (ini, argumen);
}
Lru.prototype = fn baru ();
Lru.prototype.get = function (key) {
var node = tidak terdefinisi;
node = this.container [key];
if (node) {
this.use (node);
}
return node;
};
Lru.prototype.set = fungsi (tombol, nilai) {
var node = this.buildnode (nilai, kunci);
if (this.length === this.maxlength) {
this.pop ();
}
this.unshift (node);
};
/**
* Implementasi Algoritma Eliminasi Cache FIFO
* @constructor
*/
fungsi fifo () {
Eliminasi.Apply (ini, argumen);
}
Fifo.prototype = fn baru ();
Fifo.prototype.get = function (key) {
var node = tidak terdefinisi;
node = this.container [key];
return node;
};
Fifo.prototype.set = function (tombol, value) {
var node = this.buildnode (nilai, kunci);
if (this.length === this.maxlength) {
this.shift ();
}
this.append (node);
};
/**
* Engoritma algoritma LRU dan FIFO telah menjadi algoritma eliminasi cache Twoqueues yang baru
* @param maxlength
* @constructor
*/
agen fungsi (maxlength) {
this.getCount = 0;
this.hitcount = 0;
this.lir = fifo baru (maxlength);
this.hirs = LRU baru (maxlength);
}
Agent.prototype.get = function (key) {
var node = tidak terdefinisi;
node = this.lir.get (key);
if (node) {
node.use ++;
if (node.use> = 2) {
this.lir.remove (node);
this.hir.set (node.key, node.data);
}
}kalau tidak{
node = this.hir.get (key);
}
return node;
};
Agent.prototype.getx = function (key) {
var node = tidak terdefinisi;
this.getCount ++;
node = this.get (key);
if (node) {
this.hitcount ++;
}
return node;
};
Agent.prototype.set = function (key, value) {
var node = null;
node = this.lir.container [Key] || this.hir.container [Key];
if (node) {
node.data = nilai;
}kalau tidak{
this.lir.set (kunci, nilai);
}
};
/**
* Dapatkan tarif hit
* @returns {*}
*/
Agent.prototype.hitratio = function () {
var ret = this.getCount;
if (ret) {
ret = this.hitcount / this.getCount;
}
kembali kembali;
};
/**
* Antarmuka eksternal
* Kapasitas cache @param maxlength
* @param dev apakah itu lingkungan pengembangan, lingkungan pengembangan akan menghitung tingkat hit, jika tidak itu tidak akan
* @returns {{get, atur: function, hitratio: function}}
*/
exports.inittwoqueues = function (maxlength, dev) {
var API = agen baru (maxlength);
kembali {
get: (function () {
if (dev) {
return function (key) {
var ret = api.getx (key);
return ret && ret.data;
};
}kalau tidak{
return function (key) {
var ret = api.get (key);
return ret && ret.data;
};
}
} ()),
set: function () {
API.SET.Apply (API, Argumen);
},
HitRatio: function () {
return api.hitratio.Apply (API, argumen);
}
};
};
}(ini));
Akhirnya, saya ingin mengingatkan Anda lagi bahwa algoritma cache perlu dikombinasikan dengan skenario aplikasi yang sebenarnya. Tanpa algoritma universal, yang terbaik adalah yang terbaik!