[ALGORITHM] LRU 캐시

캐시 정의

• 빠른 검색과 조회를 위해 자주 사용되는 데이터나 값을 미리 복사해 놓는 임시 장소
• 주로 데이터 접근시 오래걸리거나 값을 다시 계산해야할 때 절약해야 하는 경우 사용

---

LRU (Least Recently Used) 캐시

https://www.topjavatutorial.com/java/java-programs/lru-cache-java/ 참고

• 최근에 가장 오래 사용하지 않은 페이지를 교체하는 기법
• 캐시에 공간이 부족시 가장 최근에 사용하지 않은 데이터(가장 오래된 데이터)를 제거
• 메모리 상에서 가장 오래된 데이터를 새로운 데이터로 갱신함

---

자바 구현 예시

LinkedList로 구현

public class LRUCache {

  public int size;
  public LinkedList<Integer> cache;

  public LRUCache(int size) {
    this.size = size;
    this.cache = new LinkedList<>();
  }

  public void query(int number) {
    if (cache.contains(number)) {
      cache.remove(number);
      cache.add(number);
    } else {
      if (this.size ==  cache.size()) {
        cache.removeLast();
      }
      cache.addFirst(number);
    }
  }
}

LinkedHashSet으로 구현

public class LRUCache {
 
  public int size;
  public Set<Integer> cache;

  public LRUCache(int size) {
    this.size = size;
    this.cache = new LinkedHashSet<>();
  }

  public void query(int number) {
    if (cache.contains(number)) {
      cache.remove(number);
      cache.add(number);
    } else {
      if (this.size == cache.size()) {
        int lastRemoveData = cache.iterator().next();
        cache.remove(lastRemoveData);
      }
      cache.add(number);
    }
  }
}