LRU (Least Recently Used) 알고리즘
LRU(Least Recently Used) 알고리즘은 캐시 메모리 관리에서 가장 많이 사용되는 방법 중 하나입니다. 이 알고리즘의 기본 원리는 가장 오랫동안 사용되지 않은 데이터를 교체하는 것입니다. 즉, 캐시가 가득 찼을 때 가장 최근에 사용된 적이 없는 데이터를 삭제하여 새로운 데이터를 저장합니다.
LRU를 구현하기 위해서는 n의 크기를 가지는 DoublyLinkedList(or Queue)와 이를 추적하기 위한 n의 크기를 가지는 HashMap이 필요합니다.
LRU 알고리즘의 동작 과정
- 캐시의 크기가 정해져 있습니다.
- 데이터 요청이 들어오면 캐시에 해당 데이터가 있는지 확인합니다.
- 캐시 히트(Cache Hit): 요청한 데이터가 캐시에 있을 경우, 해당 데이터를 사용하고 가장 최근 사용한 데이터로 업데이트합니다.
- 캐시 미스(Cache Miss): 요청한 데이터가 캐시에 없을 경우, 새로운 데이터를 캐시에 추가하고, 만약 캐시가 가득 차 있다면 가장 오래된 데이터를 삭제합니다.
Java로 구현한 LRU 예시
아래의 코드는 LRU 캐시를 Java로 구현한 예시입니다. LinkedHashMap을 사용하여 가장 최근에 사용된 데이터를 쉽게 관리할 수 있습니다.
LinkedHashMap생성자:- capacity: 캐시의 크기
- loadFactor: 해시 테이블의 로드 팩터, 일반적으로 0.75
- accessOrder: true로 설정하면 최근 접근 순서로 정렬, false로 설정하면 삽입 순서로 정렬
또한 선입선출을 가진 queue를 사용하면 쉽게 구현할 수 있습니다.
LinkedHashMap를 사용한 LRU 구현
import java.util.LinkedHashMap;
import java.util.Map;
class LRUCache {
private final int capacity;
private final Map<Integer, Integer> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}
// 사용 예시
public class Main {
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(2);
lruCache.put(1, 1); // 캐시: {1=1}
lruCache.put(2, 2); // 캐시: {1=1, 2=2}
System.out.println(lruCache.get(1)); // 1 (캐시: {2=2, 1=1})
lruCache.put(3, 3); // 캐시: {1=1, 3=3}, 2가 제거됨
System.out.println(lruCache.get(2)); // -1 (캐시 미스)
}
}Queue 사용한 LRU 구현
import java.util.*;
class LRUCache {
private final int capacity;
private final Queue<Integer> cache;
private final Map<Integer, Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new LinkedList<>();
this.map = new HashMap<>();
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1; // 캐시 미스
}
// 캐시 히트: 리스트에서 해당 키를 제거하고 맨 앞에 추가
cache.remove(Integer.valueOf(key));
cache.add(key);
return map.get(key);
}
public void put(int key, int value) {
if (map.containsKey(key)) {
// 이미 존재하는 키: 리스트에서 제거하고 맨 앞에 추가
cache.remove(Integer.valueOf(key));
} else if (cache.size() >= capacity) {
// 캐시가 꽉 찬 경우, 가장 오래된 항목 제거
int oldestKey = cache.remove();
map.remove(oldestKey);
}
// 새로운 항목 추가
cache.add(key);
map.put(key, value);
}
}
// 사용 예시
public class Main {
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(2);
lruCache.put(1, 1); // 캐시: [1], {1=1}
lruCache.put(2, 2); // 캐시: [2, 1], {1=1, 2=2}
System.out.println(lruCache.get(1)); // 1 (캐시: [1, 2])
lruCache.put(3, 3); // 캐시: [3, 1], {1=1, 3=3} -> 2 제거됨
System.out.println(lruCache.get(2)); // -1 (캐시 미스)
}
}LinkedList와 LinkedHashMap의 차이
-
LinkedList:
- 사용된 항목을 앞쪽에 두고, 오래된 항목을 뒤쪽
- 캐시 히트 시 해당 항목 제거 후 맨 앞에 추가
- 캐시 미스시 새로운 항목을 추가, 캐시가 꽉 차면 마지막 항목 제거
- 탐색 성능
O(n)
-
LinkedHashMap:
- 삽입 순서에 따라 항목을 유지
accessOrder를 true로 설정, 히트가 발생 시 앞쪽으로 이동- 탐색 성능
O(1)
LFU (Least Frequently Used) 알고리즘
LFU(Least Frequently Used) 알고리즘은 데이터의 사용 빈도를 기반으로 캐시를 관리합니다. 이 알고리즘은 가장 적게 사용된 데이터를 교체하는 방식으로 동작합니다.
Queue로 구현가능하며, 각 캐시마다 참조횟수를 알아야하므로 각 캐시마다 카운터(counter)가 필요합니다.
LFU 알고리즘의 동작 과정
- 캐시의 크기가 정해져 있습니다.
- 데이터 요청이 들어오면 해당 데이터의 사용 빈도를 증가시킵니다.
- 캐시 히트: 요청한 데이터가 캐시에 있을 경우, 해당 데이터의 빈도를 증가시킵니다.
- 캐시 미스: 요청한 데이터가 캐시에 없을 경우, 새로운 데이터를 캐시에 추가합니다. 만약 캐시가 가득 차 있다면 가장 적게 사용된 데이터를 삭제합니다.
Java로 구현한 LFU 예시
아래의 코드는 LFU 캐시를 Java로 구현한 예시입니다. HashMap과 PriorityQueue를 사용하여 캐시의 빈도를 관리합니다.
import java.util.HashMap;
import java.util.PriorityQueue;
class Node {
int key, value, frequency; // frequency 참조 횟수
public Node(int key, int value) {
this.key = key;
this.value = value;
this.frequency = 1; // 초기 빈도는 1
}
}
class LFUCache {
private final int capacity;
private final HashMap<Integer, Node> cache;
private final HashMap<Integer, PriorityQueue<Node>> frequencyMap;
private int minFrequency;
public LFUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.frequencyMap = new HashMap<>();
this.minFrequency = 0;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
Node node = cache.get(key);
updateFrequency(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (cache.containsKey(key)) {
Node node = cache.get(key);
node.value = value;
updateFrequency(node);
} else {
if (cache.size() == capacity) {
Node toRemove = frequencyMap.get(minFrequency).poll();
cache.remove(toRemove.key);
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
minFrequency = 1;
frequencyMap.putIfAbsent(1, new PriorityQueue<>((a, b) -> a.key - b.key));
frequencyMap.get(1).offer(newNode);
}
}
private void updateFrequency(Node node) {
int freq = node.frequency; // 현재 빈도
frequencyMap.get(freq).remove(node); // 현재 빈도의 큐에서 제거
if (frequencyMap.get(freq).isEmpty()) {
frequencyMap.remove(freq); // 빈도가 0인 경우 제거
if (minFrequency == freq) {
minFrequency++; // 최소 빈도 업데이트
}
}
node.frequency++; // 참조 횟수 증가
frequencyMap.putIfAbsent(node.frequency, new PriorityQueue<>((a, b) -> a.key - b.key));
frequencyMap.get(node.frequency).offer(node); // 증가된 빈도로 큐에 추가
}
}
// 사용 예시
public class Main {
public static void main(String[] args) {
LFUCache lfuCache = new LFUCache(2);
lfuCache.put(1, 1); // 캐시: {1=1}
lfuCache.put(2, 2); // 캐시: {1=1, 2=2}
System.out.println(lfuCache.get(1)); // 1
lfuCache.put(3, 3); // 캐시: {3=3}, 2가 제거됨
System.out.println(lfuCache.get(2)); // -1 (캐시 미스)
}
}결론
LRU와 LFU 알고리즘은 캐시 메모리 관리를 위한 두 가지 주요 전략입니다. LRU는 가장 오래된 데이터를 제거하는 방식이며, LFU는 사용 빈도가 가장 낮은 데이터를 제거하는 방식입니다. 각각의 장단점이 있으며, 사용자의 요구사항에 따라 적절한 알고리즘을 선택하여 사용할 수 있습니다.
참고:https://hstory0208.tistory.com/142 https://velog.io/@zinna_1109/CS-LRU-%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-java-%EA%B5%AC%ED%98%84-%EB%B0%A9%EB%B2%95
