Muka menggunakan lru cache javascript

LRU adalah singkatan dari cache yang Paling Baru Digunakan. Cache digunakan di mana-mana, mari kita coba menerapkannya di Javascript

Di sini, kami memiliki cache ukuran 4. Sebagai contoh, awalnya dapat memiliki 4 elemen sebagai 4, 3, 2, 1. Sekarang, jika elemen baru (pertimbangkan 5) ditambahkan ke cache, itu menjadi elemen terbaru di cache. Oleh karena itu, kami menempatkannya di awal

Namun, jika kami melakukan ini, kami juga melebihi ukuran cache. Jadi kita harus menghapus elemen dari cache. Oleh karena itu, kami menghapus elemen 1. Dengan kata lain, item yang terakhir digunakan atau diakses dalam cache

Singkatnya, inilah yang kami maksud dengan LRU Cache

2 – Implementasi Cache LRU

Untuk mengimplementasikan LRU Cache, ada beberapa aturan umum yang harus kita ikuti

• Penyisipan elemen baru di LRU Cache harus dilakukan dengan kompleksitas waktu O(1). Dengan kata lain, waktu yang konstan
• Juga, pengambilan elemen dari Cache harus dengan kompleksitas waktu O(1)
• Saat kami mengambil item dari Cache, itu harus menjadi item yang terakhir digunakan dalam daftar. Dengan kata lain, itu harus di atas daftar

Jadi semua struktur data apa yang bisa kita gunakan untuk implementasi seperti itu?

Untuk memulainya kita bisa menggunakan List. Pilihan ideal di sini adalah Daftar Tertaut Ganda. Menggunakan daftar tertaut ganda akan memungkinkan kami menghapus elemen dari cache dalam kompleksitas waktu O(1) yang sangat penting bagi kami

Kami juga membutuhkan cara untuk mengakses elemen dalam kompleksitas waktu O(1). Untuk melakukannya, kita memerlukan struktur data Peta. Dalam Javascript, kita dapat mencapainya dengan menggunakan Objek Javascript

Beberapa aturan yang bisa kita gunakan untuk membuatnya bekerja adalah sebagai berikut

• Sisipkan elemen baru di bagian atas Doubly Linked List
• Pada setiap pembacaan atau penyisipan ke cache, elemen yang dibaca atau disisipkan dipindahkan ke kepala Daftar Berantai
• Jika batas cache terlampaui saat menyisipkan, hapus elemen di bagian belakang Daftar Tertaut
• Menyimpan kunci dan nilai relasi dalam sebuah objek. Ini memungkinkan pengambilan dalam kompleksitas waktu O(1).

3 – Langkah Implementasi Cache LRU

Setelah menetapkan aturan dasar, sekarang mari kita mulai penerapannya

3. 1 – Kelas Node

Kelas simpul menyimpan elemen dalam Daftar Tertaut

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

Karena kita bekerja dengan Doubly Linked List, setiap simpul akan mengarah ke simpul berikutnya dan juga simpul sebelumnya. Jika Anda ingin membaca lebih lanjut tentang itu, saya memiliki posting rinci tentang Implementasi Daftar Tertaut di Javascript

3. 2 – Kelas Cache LRU

Ini adalah bagian utama dari implementasi kami. Pada dasarnya, di sinilah kita akan menentukan perilaku Cache LRU kita

________satu_______

Kami memiliki elemen kepala dan ekor. Kemudian, kami memiliki atribut size untuk menyimpan ukuran cache saat ini. Juga, properti maxSize untuk menyimpan ukuran maksimum cache. Terakhir, kita memiliki objek cache. Kami menginisialisasi ke objek javascript kosong di konstruktor

3. 3 – Fungsi Elemen Put

Fungsi pertama yang harus kita terapkan adalah memasukkan item baru ke dalam cache kita. Di bawah ini adalah implementasi untuk hal yang sama

put(key, value) {
        let newNode

        // if the key not present in cache
        if (this.cache[key] === undefined) newNode = new Node(key, value);

        //if we have an empty list
        if(this.size === 0) {
            this.head = newNode;
            this.tail = newNode;
            this.size++;
            this.cache[key] = newNode;
            return this;
        }

        if (this.size === this.maxSize) {
            //remove from cache
            delete this.cache[this.tail.key]

            //set new tail
            this.tail = this.tail.prev;
            this.tail.next = null;
            this.size--;
        }

        //add an item to the head
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    
        //add to cache
        this.cache[key] = newNode; 
        return this;
        
}

Pada dasarnya, kami memeriksa apakah item dengan kunci yang diberikan sudah ada. Jika tidak, kami memasukkannya ke dalam daftar dan objek cache

Juga, jika itu adalah elemen pertama dalam cache, kami membuatnya menjadi kepala dan ekor dari daftar. Jika tidak, kami menjadikan simpul baru sebagai kepala daftar

Terakhir, jika kami mencapai ukuran maksimum daftar, kami menghapus item di bagian belakang daftar

3. 4 – Fungsi Dapatkan Elemen

Fungsi kedua adalah untuk mendapatkan elemen dari cache. Sesuai kebutuhan kami, ini juga harus terjadi dalam kompleksitas waktu O(1). Di bawah ini adalah implementasi untuk hal yang sama

get(key) {
        if (!this.cache[key]){
            return undefined
        }

        let foundNode = this.cache[key];
        
        if(foundNode === this.head) return foundNode;

        let previous = foundNode.prev;
        let next = foundNode.next;

        if (foundNode === this.tail){
            previous.next = null;
            this.tail = previous;
        }else{
            previous.next = next;
            next.prev = previous;
        }

        this.head.prev = foundNode;
        foundNode.next = this.head;
        foundNode.prev = null;
        this.head = foundNode;

        return foundNode;      
}

Kami menggunakan objek cache untuk menemukan elemen dengan kunci input. Karena ini adalah objek, kita dapat melakukan operasi dalam kompleksitas waktu yang konstan. Sekarang, yang terpenting adalah menjadikan elemen yang diakses sebagai elemen pertama dalam daftar. Dengan kata lain, kami ingin menjadikannya elemen yang paling baru digunakan

Jika sudah menjadi elemen pertama, kita cukup mengembalikannya. Jika bukan itu masalahnya, maka kita harus menghapus elemen dari daftar dan menempatkannya sebagai kepala baru. Saat menghapus, kita harus menghubungkan simpul elemen sebelumnya dengan simpul elemen berikutnya

Kesimpulan

Dengan ini, pada dasarnya kita sudah selesai. Implementasi LRU Cache kita sudah selesai. Kita dapat mengujinya dengan memasukkan dan mengakses beberapa elemen