Versi JavaScript TwoQueues caching model_Pengetahuan asas

Model caching TwoQueues yang dirujuk dalam artikel ini merujuk kepada model caching data dalam ingatan.

Tidak kira apa bahasa, anda mungkin perlu meletakkan beberapa data dalam ingatan untuk mengelakkan operasi dan pembacaan berulang. Senario yang paling biasa ialah pemilih JQuery Pemilihan beberapa elemen Dom sangat memakan masa. Kami berharap untuk menyimpan data ini tanpa perlu melintasi semula pepohon Dom setiap kali ia dipanggil.

Simpan sahaja, tetapi mesti ada jumlahnya! Anda tidak boleh meletakkan semua data sejarah dalam ingatan Lagipun, kapasiti memori semasa masih agak menyedihkan Walaupun memori cukup besar, memori yang diperuntukkan kepada setiap utas adalah terhad.

Jadi persoalannya, bagaimana kita boleh menyimpan data yang benar-benar berguna dengan cekap? Ini melibatkan algoritma penghapusan, yang perlu menghapuskan data sampah untuk mengekalkan data yang berguna.

Idea yang lebih biasa digunakan adalah seperti berikut:

FIFO: Ia adalah baris gilir masuk dahulu, data cache pertama adalah yang pertama dihapuskan Model ini digunakan dalam rangka kerja JQuery yang terkenal.

LRU: Struktur senarai terpaut berganda Setiap kali data baharu disimpan, ia diletakkan terus di kepala senarai terpaut, setiap kali data itu diakses, ia juga dipindahkan ke kepala senarai terpaut . Dengan cara ini, data di penghujung senarai terpaut adalah yang paling terkini Data yang belum digunakan akan dihapuskan.

TwoQueues: FIFO LRU, FIFO terutamanya menyimpan data yang disimpan untuk kali pertama, dan LRU menyimpan data hotspot yang telah digunakan sekurang-kurangnya dua kali Algoritma ini mempunyai kadar pukulan yang tinggi, kebolehsuaian yang kuat dan kerumitan yang rendah.

Terdapat banyak algoritma penyingkiran lain, tetapi kedua-dua algoritma ini adalah yang paling biasa digunakan. Kerana algoritma mereka tidak kompleks, mudah untuk dilaksanakan, mempunyai kecekapan pelaksanaan yang tinggi, dan kadar hit cache boleh diterima dalam kebanyakan situasi. Lagipun, algoritma caching juga menggunakan CPU Jika ia terlalu rumit, walaupun kadar pukulan akan dipertingkatkan, keuntungan tidak akan sepadan dengan kerugian. Cuba bayangkan, jika mendapatkan semula data dari cache mengambil masa lebih lama daripada mendapatkannya dari lokasi asal, apakah guna caching?

Saya tidak akan menerangkan secara terperinci tentang teori tertentu Terdapat banyak di Internet, tetapi saya tidak begitu memahaminya dengan anda hari ini ialah versi JavaScript model cache TwoQueues.

Mari kita bincangkan tentang cara menggunakannya dahulu, ia sangat mudah.

Penggunaan asas adalah seperti berikut:

[/kod]
var tq = initTwoQueues(10);
tq.set("kunci", "nilai");
tq.get("kunci");
[/kod]

Apabila memulakan, hanya nyatakan kapasiti cache. Perlu diingatkan bahawa disebabkan oleh pelaksanaan FIFO LRU dalaman, kapasiti sebenar adalah dua kali ganda kapasiti yang ditentukan Contoh di atas menentukan 10 (pasangan kunci-nilai), tetapi 20 sebenarnya boleh disimpan.

Saiz kapasiti perlu ditentukan mengikut senario aplikasi sebenar Jika terlalu kecil, kadar pukulan akan rendah, jika terlalu besar, kecekapan akan rendah.

Semasa proses pembangunan, untuk menyemak kesan cache, anda boleh memulakan kumpulan cache kepada versi pembangunan:

Salin kod Kod adalah seperti berikut:

var tq = initTwoQueues(10, benar);
tq.hitRatio();

Cuma tambahkan parameter pada penghujungnya, jadikan ia benar. Kumpulan cache yang dimulakan dengan cara ini akan mengira kadar hit secara automatik dan kadar hit boleh diperoleh melalui kaedah hitRatio. Jika parameter ini tidak ditambahkan, nisbah hit yang diperolehi oleh kaedah hitRatio akan sentiasa 0.
Kadar pukulan statistik pasti akan menggunakan sumber, jadi tidak disyorkan untuk menghidupkannya dalam persekitaran pengeluaran.
Masa untuk berkongsi kod:

Salin kod Kod adalah seperti berikut:

 (fungsi(eksport){
     /**
* Kelas tulen untuk warisan
* @pembina
'*/
     fungsi Fn(){}
     Fn.prototype = Penghapusan.prototaip;
     /**
* Kelas induk bagi algoritma penghapusan cache berasaskan senarai terpaut
* @param maxLength kapasiti cache
* @pembina
'*/
     fungsi Penghapusan(maxLength){
         this.container = {};
         ini.panjang = 0;
         this.maxLength = maxLength || 30;
         this.linkHead = this.buildNode("", "");
         this.linkHead.head = benar;
         this.linkTail = this.buildNode("", "");
         this.linkTail.tail = benar;
         this.linkHead.next = this.linkTail;
         this.linkTail.prev = this.linkHead;
     }
     Elimination.prototype.get = function(key){
         throw new Error("Kaedah ini mesti ditindih!");
     };
     Elimination.prototype.set = fungsi(kunci, nilai){
         throw new Error("Kaedah ini mesti ditindih!");
     };
     /**
*Buat nod dalam senarai terpaut
* @param data Data yang terkandung dalam nod, iaitu nilai data cache
* @param key Pengecam unik nod, iaitu, kunci cache
* @kembali {{}}
'*/
     Elimination.prototype.buildNode = fungsi(data, kunci){
         nod var = {};
         node.data = data;
         node.key = kunci;
         node.use = 0;
         kembalikan nod;
     };
     /**
* Pop nod daripada kepala senarai terpaut
* @kembali {*}
'*/
     Elimination.prototype.shift = function(){
         var nod = null;
         jika(!this.linkHead.next.tail){
             nod = this.linkHead.next;
             this.linkHead.next = node.next;
             node.next.prev = this.linkHead;
             padamkan this.container[node.key];
             ini.panjang--;
         }
         kembalikan nod;
     };
     /**
* Masukkan nod daripada kepala senarai terpaut
* Objek nod nod @param
* @kembali {*}
'*/
     Elimination.prototype.unshift = fungsi(nod){
         node.next = this.linkHead.next;
         this.linkHead.next.prev = nod;
         this.linkHead.next = nod;
         node.prev = this.linkHead;
         this.container[node.key] = nod;
         ini.panjang ;
         kembalikan nod;
     };
     /**
      * 从链表尾插入一个节点
      * @param nod 节点对象
      * @kembali {*}
      */
     Elimination.prototype.append = fungsi(nod){
         this.linkTail.prev.next = nod;
         node.prev = this.linkTail.prev;
         node.next = this.linkTail;
         this.linkTail.prev = nod;
         this.container[node.key] = nod;
         ini.panjang ;
         kembalikan nod;
     };
     /**
* Pop nod dari hujung senarai terpaut
* @kembali {*}
'*/
     Elimination.prototype.pop = function(){
         var nod = null;
         jika(!this.linkTail.prev.head){
             nod = this.linkTail.prev;
             node.prev.next = this.linkTail;
             this.linkTail.prev = node.prev;
             padamkan this.container[node.key];
             ini.panjang--;
         }
         kembalikan nod;
     };
     /**
*Alih keluar nod yang ditentukan daripada senarai terpaut
* Objek nod nod @param
* @kembali {*}
'*/
     Elimination.prototype.remove = fungsi(nod){
         node.prev.next = node.next;
         node.next.prev = node.prev;
         padamkan this.container[node.key];
         ini.panjang--;
         kembalikan nod;
     };
     /**
* Pemprosesan yang perlu dilakukan apabila nod diakses, khususnya mengalihkan nod ke kepala senarai terpaut
* @param nod
'*/
     Elimination.prototype.use = fungsi(nod){
         this.remove(nod);
         this.unshift(nod);
     };
 
     /**
* Pelaksanaan algoritma penghapusan cache LRU
* @pembina
'*/
     fungsi LRU(){
         Elimination.apply(this, arguments);
     }
     LRU.prototype = Fn();
     LRU.prototype.get = function(key){
         nod var = tidak ditentukan;
         nod = this.container[key];
         jika(nod){
             this.use(nod);
         }
         kembalikan nod;
     };
     LRU.prototype.set = fungsi(kunci, nilai){
         var node = this.buildNode(nilai, kunci);
         if(this.length === this.maxLength){
             this.pop();
         }
         this.unshift(nod);
     };
 
     /**
* Pelaksanaan algoritma penghapusan cache FIFO
* @pembina
'*/
     fungsi FIFO(){
         Elimination.apply(this, arguments);
     }
     FIFO.prototype = Fn();
     FIFO.prototype.get = fungsi(kunci){
         nod var = tidak ditentukan;
         nod = this.container[key];
         kembalikan nod;
     };
     FIFO.prototype.set = fungsi(kunci, nilai){
         var node = this.buildNode(nilai, kunci);
         if(this.length === this.maxLength){
             this.shift();
         }
         this.append(nod);
     };
 
     /**
* Enkapsulasi algoritma LRU dan FIFO, menjadi algoritma penghapusan cache dua gilir baharu
* @param maxLength
* @pembina
'*/
     fungsi Ejen(MaxLength){
         this.getCount = 0;
         this.hitCount = 0;
         this.lir = FIFO baharu(Panjang maksimum);
         this.hir = LRU baharu(maxLength);
     }
     Agent.prototype.get = function(key){
         nod var = tidak ditentukan;
         nod = this.lir.get(key);
         jika(nod){
             node.use ;
             if(node.use >= 2){
                 this.lir.remove(nod);
                 this.hir.set(node.key, node.data);
             }
         }lain{
             nod = this.hir.get(key);
         }
         kembalikan nod;
     };
     Agent.prototype.getx = function(key){
         nod var = tidak ditentukan;
         this.getCount ;
         nod = this.get(key);
         jika(nod){
             this.hitCount ;
         }
         kembalikan nod;
     };
     Agent.prototype.set = fungsi(kunci, nilai){
         var nod = null;
         nod = this.lir.container[key] || this.hir.container[key];
         jika(nod){
             node.data = nilai;
         }lain{
             this.lir.set(kunci, nilai);
         }
     };
     /**
* Dapatkan kadar hit
* @kembali {*}
'*/
     Agent.prototype.hitRatio = function(){
         var ret = this.getCount;
         jika(kembali){
             ret = this.hitCount / this.getCount;
         }
         pulang ret;
     };
     /**
      * 对外接口
* @param maxLength kapasiti cache
* @param dev Sama ada persekitaran pembangunan, persekitaran pembangunan akan mengira kadar hit, jika tidak, ia tidak akan
* @returns {{get, set: Function, hitNisbah: Function}}
*/
exports.initTwoQueues = fungsi(maxLength, dev){
        var api = Ejen baharu(Panjang maksimum);
          kembali {
                 dapatkan: (function(){
Jika(dev){
Kembalikan fungsi(kunci){
                        var ret = api.getx(key);
                                           pulangan && ret.data;
                       };
                       }lain{
Kembalikan fungsi(kunci){
                        var ret = api.get(key);
                                           pulangan && ret.data;
                       };
                 }
             }()),
               set: function(){
api.set.apply(api, arguments);
             },
hitNisbah: function(){
                          kembalikan api.hitRatio.apply(api, argumen);
            }
          };
};

}(ini));

Akhir sekali, saya ingin mengingatkan anda sekali lagi bahawa algoritma caching perlu digabungkan dengan senario aplikasi sebenar Tiada algoritma universal, dan yang sesuai adalah yang terbaik.