Mihai Surdeanu

Implementarea unui cache de tip LRU

Salutare tuturor! Începând de astăzi voi începe să public săptămânal un articol de programare, în limba română, care va încerca să trateze unui anumit topic și să fie cât se poate de practic.

Iubesc practica, chiar dacă știu că și teoria este necesară pentru a face lucrurile să meargă.

Să îi dăm drumul zic… Astăzi vom împlementa un simplu cache de tipul LRU. De ce la ce vine LRU? Least Recently Used. Cum funcționează un cache de acest tip? Forte simplu. Operația de find va aduce elementul din cache, dacă există, sau Optional.empty() dacă elementul nu există în cache. Pe lângă operația de get, cache-ul va expune și o operație de put, prin care se va putea actualiza valoarea unui element. Dacă elementul nu există deja în cache, atunci se va adăuga în acesta din urmă. În plus, un cache de acest gen trebuie să mai aibă și o capacitate maximă, pentru a evita problemele de genul – Out of memory. Dacă la adăugarea unui nou element se va depăși capacitatea, atunci elementul cel mai puțin utilizat va trebui să fie eliminat pentru a menține valoarea capacității.

Să recapitulăm:

  • LeastRecentlyUsedCache(int capacity) – prin constructor vom inițializa capacitatea maximă a cache-ului nostru.
  • Optional<String> find(String key) – metoda prin care se va putea căuta un element în cache. Vorbim de un getter, dar am numit intenționat metoda find pentru că returnează un Optional.
  • Optional<String> putAndReturn(String key, String value) – metoda prin care se va putea scrie o valoare nouă în cache. Metoda va returna valoarea suprascrisă încapsulată într-un Optional, dacă există, altfel Optional.empty().

Cerința este să se implementeze în Java un cache de acest tip și să se aibă în vedere faptul că operațiile de tipul find și put să aibă complexitatea O(1).

Înainte de a trece la implementare, să luăm și un exemplu. Este foarte important să aveți un pix și o foaie și să petreceți cel puțin 5 minute, pentru a analiza problema pe foaie. Nu vă grăbiți niciodată să treceți direct la implementare!

Exemplu:

LeastRecentlyUsedCache cache = new LeastRecentlyUsedCache(3);
cache.putAndReturn("ka", "va"); // cache-ul are 1 element după operație
cache.putAndReturn("kb", "vb"); // cache-ul are 2 elemente după operație
cache.putAndReturn("kc", "vc"); // cache-ul are 3 elemente după operație
cache.find("ka"); // returnează Optional.of("va");
cache.find("kb"); // returnează Optional.of("vb");
cache.putAndReturn("kd", "vd"); // cache-ul are 4 elemente după operație. Vom scoate un element din acesta, pe cel mai puțin utilizat și anume "kc".
cache.find("kc"); // returnează Optional.empty();
cache.putAndReturn("ke", "ve"); // cache-ul are 4 elemente după operație. Vom scoate un element din acesta, pe cel mai puțin utilizat și anume "ka".
cache.find("ka"); // returnează Optional.empty();

Să trecem la soluție. Sunt mai multe implementări, cea mai simplă bazându-se pe un LinkedHashMap. Vă invit să petreceți puțin timp pentru a citi documentația oficială. Partea de eviction aici este puțin tricky, de aceea, din documentație, va trebui să puneți accentul pe metoda removeEldestEntry.

Totul este straight forward după ce ați citit documentația:

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Optional;

public class LeastRecentlyUsedCache extends LinkedHashMap<String, String> {

    private final int capacity;

    public LeastRecentlyUsedCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public Optional<String> find(String key) {
        return Optional.ofNullable(get(key));
    }

    public Optional<String> putAndReturn(String key, String value) {
        return Optional.ofNullable(put(key, value));
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > capacity;
    }

}

Avem și un mic test:

import org.assertj.core.api.Assertions;
import org.junit.Test;

public class LeastRecentlyUsedCacheTest {

    @Test
    public void testExample() {
        // given
        LeastRecentlyUsedCache cache = new LeastRecentlyUsedCache(3);

        // when & then
        Assertions.assertThat(cache.putAndReturn("ka", "va")).isNotPresent();
        Assertions.assertThat(cache.putAndReturn("kb", "vb")).isNotPresent();
        Assertions.assertThat(cache.putAndReturn("kc", "vc")).isNotPresent();
        Assertions.assertThat(cache.find("ka")).isPresent();
        Assertions.assertThat(cache.find("kb")).isPresent();
        Assertions.assertThat(cache.putAndReturn("kd", "vd")).isNotPresent();
        Assertions.assertThat(cache.find("kc")).isNotPresent();
        Assertions.assertThat(cache.putAndReturn("ke", "ve")).isNotPresent();
        Assertions.assertThat(cache.find("ka")).isNotPresent();
    }

}

Temă de casă: Implementarea noastră suferă la capitolul încapsulare. De ce? Pentru că prin extinderea clasei LinkedHashMap, vor fi expuse by default și metodele get și put din clasa părinte. Dvs. aveți responsabilitatea să vă gândiți cum puteți “să ascundeți” aceste metode. Spor la treabă!

Mihai

Pasionat de IT. Pasionat de viață. Pasionat de tot ceea ce înseamnă a face o viață mai bună, plină de înțelegere, ajutor reciproc și iubire de aproape.

Adaugă comentariu

Arhive

Arhiva personală