LRU

LRU 알고리즘은 정해진 size만큼 cache가 가득 차고, cache에 없는 페이지가 들어왔을 때 가장 오래된 페이지를 제거하는 알고리즘

운영체제에서 어떤 페이지로 교체할지 결정하는 페이징 기법 중 하나다.

Page-hit : 현재 페이지(삽입하려는 페이지)가 메모리에 이미 있을 때

왼쪽에 있을수록 최근에 사용한 페이지다.

다음 두가지를 고려해야한다.

 

1. 삽입하려는 페이지가 이미 cache에 있다.

이 경우 기존에 있던 페이지를 삭제하고 최신 페이지로 만들어준다.

• 기존 페이지를 삭제한다.
• 가장 왼쪽에 신규 페이지를 추가한다.

 

2. 삽입하려는 페이지가 cache에 없다.

• cache에 페이지를 추가한다.
• 정해진 사이즈만큼 캐시가 가득 찼을 경우에는 캐시에서 가장 마지막 페이지를 제거 후 신규 페이지를 추가

 

 

📌 파이썬으로 구현한 LRU 알고리즘

# '[1차] 캐시' 문제를 풀었던 코드 중 일부
from collections import deque

hashSet = set()  # 중복 체크
doublyQueue = deque()

def LRUCache(cacheSize, page):
    global hashSet
    global doublyQueue
    ans = 1

    if page not in hashSet:  # set에 없으면(cache miss)
        ans=5
        if cacheSize == len(doublyQueue): 	 # cacheSize만큼 가득차면
            last = doublyQueue.pop()        
            hashSet.discard(last)
    else:       # cache hit
        if doublyQueue :
            doublyQueue.remove(page)  

    doublyQueue.appendleft(page)  # 가장 왼쪽에 추가
    hashSet.add(page)

    return ans

 

나처럼 set을 굳이 쓰지 않아도 됨

파이썬의 in이 deque에서도 쓸 수 있으니까

 

 

class Solution {
    public static LinkedHashSet<String> set;

    public int LRU(int cacheSize, String city){
        int cnt=5;			// cache miss
        if(set.contains(city)){   // cache hit
            cnt=1;
            set.remove(city);
        }

        set.add(city);      // 오른쪽으로 갈수록 최신
        if(set.size() > cacheSize){     // 가득 찼을 때
            String first=set.iterator().next();
            set.remove(first);
        }

        return cnt;
    }

자바로 구현할 시 HashSet & deque를 사용하거나 LinkedHashSet으로 풀면된다.

 

 

 

참고👇

https://www.geeksforgeeks.org/lru-cache-implementation/

LRU Cache Implementation - GeeksforGeeks

 

https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)