Bir yazılım mühendisi olarak seyahatlerinizde, olası her veri yapısının parlama şansı bulduğu durumlarla karşılaşmanız muhtemeldir. Özellikle biri diğerleri kadar spot ışığı almaz, ancak belirli durumlarda (daha fazla değilse) aynı derecede faydalı olabilir. Söz konusu veri yapısı LRU Önbelleğidir .

LRU Önbelleği nedir?

Bir LRU Önbelleği veya En Son Kullanılan Önbellek , bilgileri en son eklendiği veya erişildiği sırayla depolayan bir veri yapısıdır.

Popüler bir benzetme, dolaptaki bir elbise askısıdır: giysiler giyilip asıldığında, bunlar rafın sağ tarafına gider. Zaman geçtikçe, rafın sol tarafına bakarak hangi giysinin daha uzun süre giyilmediğini kolayca anlayabilirsiniz.

Neden bir tane kullanmak isteyeyim?

Bilgileri depolamak için diğer veri yapılarına kıyasla bir LRU Önbelleği kullanmanın temel avantajı, ek işlevsellik biçiminde gelir.

Bilgisayar bilimi terimlerinde bir Önbellek , bellekte hızlı bir şekilde erişilebilen bir konumda depolanan, son zamanlarda kullanılan verilerin bir bloğu olarak düşünülebilir ve bu, aynı veriler tekrar tekrar çekildiğinde daha hızlı performans sağlar.

Bir LRU Önbelleği düşünürsek, bilgi için bir veritabanında arama yapan kullanıcıların olduğu bir uygulamada faydalı olabilir. Normalde, bir kullanıcı bir şeyi her aradığında, uygulama veritabanına bir istekle ping atar ve bunu yapmak için çok zaman alır. Bununla birlikte, en son (veya en sık) aranan öğeleri bir LRU önbelleğinde saklarsak, aranan öğenin önbellekte bulunup bulunmadığını hızlı bir şekilde kontrol edebilir ve eğer öyleyse, önemli ölçüde daha kısa sürede geri alabiliriz. zaman! Süper kullanışlı.

Kulağa harika geliyor, nasıl inşa ederiz?

Sorduğuna sevindim Geleneksel olarak LRU Önbellekleri, öğelerin hızlı bir şekilde aranmasını ve en son kullanılan ve en az kullanılan öğelerin sabit O (1) süresinde geri alınmasını sağlamak için Karma Haritası ile Çift Bağlantılı Liste birleştirilerek oluşturulur.

Bununla birlikte, küçük ölçekli bir projede bir LRU Önbelleğini sıfırdan hızlı bir şekilde uygulamak ilginizi çekiyorsa, bir JavaScript Sınıfı ve bir Map () nesnesinden başka bir şey kullanılmadan , çalışma zamanını geri alma maliyetiyle oluşturulabilir.

En Az / En Son Kullanılan işlevselliği, uygulamada veri yapısının temel yönü olan aynı kalacaktır. Bir LRU Önbelleğinin bu sürümünü nasıl oluşturacağınızı öğrenmekle ilgileniyorsanız, okumaya devam edin!

 

1. Sınıfı ve Yapıcıyı Oluşturun

LRU Önbelleğimizi bir JavaScript ES6 sınıfı kullanarak oluşturacağız, örneğin:

class LRUCache {

}

Bu sınıf içinde, bir LRU Önbelleğinin her örneğinin aynı yapıyı sürdürmesi için bir kurucu ayarlayacağız. Önbelleğimiz, alandan tasarruf etmek ve yapıyı düzenli tutmak için en son kullanılan öğeyi depodan çıkarmadan önce önbelleğimizin büyüyebileceği maksimum boyutu ayarlayacak bir kapasiteyi argüman olarak alacaktır.

Bu kurucuyu, bir JavaScript Harita nesnesi kullanarak önbelleğin kendisini oluşturmak için de kullanacağız:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  } 

}

Burada bir Harita nesnesi kullanmamızın nedeni, JavaScript Haritalarının anahtarların ve değerlerin eklendiği sırayı korumasıdır . Bu bizim için işin çoğunu yapıyor!

2. Önbelleğin Get and Put yöntemlerini oluşturun

Şimdi, sınıf içinde iki hayati fonksiyonumuzu uygulayacağız: Get ve Put , bir değer alacak ve sırasıyla önbelleğe bir anahtar / değer çifti ekleyecek.

Get ile başlayalım :

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  // Implementing Get method
  get(key) {
    if (!this.cache.has(key)) return "Key not found";

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

}

Biraz önce yukarıda yaptığımız şeyi inceleyelim.

  • Haritamızda anahtarın olup olmadığını kontrol ederiz. Aksi takdirde, kullanıcıyı bilgilendiren bir mesaj döndürürüz (bu, başarısız bir alımı temsil eden herhangi bir dönüş değeri olabilir.)
  • Sonra bir "val" değişkeni tanımlıyoruz, bu anahtarla ilişkili değeri alıyoruz ve onu değişkene atıyoruz.
  • Bu anahtar / değer çiftini önbelleğimizden silip yeniden ayarlıyoruz . Haritamız bir şeyleri eklediğimiz sırayı koruduğundan, bu, geri alınan anahtar / değer çiftimizi ön (en son kullanılan) noktaya geri koyar.
  • Bu yöntemin çağrıldığı her yerde programımızda kullanılacak değeri döndürüyoruz.

Ve Get yönteminin hepsi bu kadar!

Şimdi, Put yöntemimizi uygulayacağız:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  // Implementing Put method
  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

}

Bunu adımlara ayıralım:

  • İlk satır, anahtarın haritada mevcut olup olmadığını kontrol eder ve varsa onu siler; .delete () çağrısı varsa anahtar / değer çiftini siler VEYA tanımsız döndürür ve yoksa devam eder.
  • Önbelleğimiz şu anda maksimum kapasitesindeyse ( cache.size === this.capacity ), en son kullanılan anahtar / değer çiftimizi this.cache.keys().next().value bir yineleyici nesnesi kullanarak Map'in ilk anahtarını alıp argüman olarak ileterek sileriz this.cache.delete() . Daha sonra, Put yöntemine iletilen argümanları kullanarak önbellekte yeni bir anahtar / değer çifti belirledik.
  • Şu anda maksimum kapasitede değilsek, yeni anahtar / değer çiftini normal olarak eklememiz yeterlidir.

Ve Set yöntemimiz var!

3. getLeastRecent ve getMostRecent yöntemlerini uygulayın

Bu noktada bir LRU Önbelleğinin temel işlevini oluşturduk, ancak eksiksiz bir veri yapısına sahip olmak için atılması gereken bir adım var. En Son Kullanılan (LRU) veya En Son Kullanılan (MRU) değerlerini almak isteyebiliriz!

Bunu yapmak için, Haritamızı bir diziye dönüştüreceğiz, ardından sırasıyla dizinin ilk (LRU) ve son (MRU) değerlerini alacağız:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

  // Implement LRU/MRU retrieval methods
  getLeastRecent() {
    return Array.from(this.cache)[0];
  }

  getMostRecent() {
    return Array.from(this.cache)[this.cache.size - 1];
  }

}

Ve işte başlıyoruz! İsterseniz, en az kullanılan ikinci, en son kullanılan üçüncü, vb. Bulmak için aynı Haritadan Dizi konseptini kullanabilirsiniz.

Bu bizim LRU Önbelleğimiz!

Şimdiye kadar okuduysanız, zaman ayırıp gönderime göz attığınız için çok teşekkürler!

Veri yapılarını öğrenmeye ve anlamaya çalışanlarınız veya bunları JavaScript'te uygulamaya çalışanlarınız için umarım faydalı olmuştur.