[알고리즘] LRU (Least Recently Used) 알고리즘_ [1차] 캐시

[알고리즘] LRU (Least Recently Used) 알고리즘

 

페이지 교체 알고리즘 중 가장 대표적인 것이 LRU 알고리즘이다. 이 알고리즘을 파이썬으로 구현해보고 문제도 풀어보자 !

 

페이지 교체 알고리즘

 Page fault가 발생하여 새로운 페이지를 할당해야 할 때, Allocated page 중 어느 것과 교체할지를 결정하는 알고리즘이다. 각각 서비스에 맞게 사용하여야 한다.

 

LRU(Least Recently Used)

 Page fault가 발생했을 때, 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다. 이 것은 가장 오랫동안 사용되지 않은 페이지는 앞으로도 사용할 확률이 적다는 가정이 존재한다. 마치 locality !

 

기본 파이썬 코드

cacheSize = 3
reference = [4, 2, 3, 4, 5, 6, 5, 4, 7]
cache = []
for ref in reference:
  if not ref in cache:
    if len(cache) < cacheSize:
        cache.append(ref)
     else:
        cache.pop(0)
        cache.append(ref)
  else:
    cache.pop(cache.index(ref))
    cache.append(ref)

 

사실 list를 사용하여 추가의 경우 append로 마지막에 넣어주니 O(1)이지만,

삭제의 경우 O(n)의 시간이 들어 효율적이진 못한 풀이다.

Hash map + doublely linked list를 이용한다면 O(1)로 줄일 수 있을 것이다.

파이썬의 경우 아직 class 생성 문법을 다뤄본 경험이 없어, 다음에 js로 구현하는 것을 해봐야겠다.

 

 

프로그래머스 - [1차] 캐시

LRU 문제를 풀어보도록 하자.

 

https://programmers.co.kr/learn/courses/30/lessons/17680?language=python3 

코딩테스트 연습 - [1차] 캐시

 

풀이

 

def solution(cacheSize, cities):
    answer = 0
    cache = []
    for city in cities:
        city = city.lower()
        if city in cache:  # cache hit
            cache.remove(city)
            cache.append(city)
            answer+=1
            
        else: # cache miss
            if len(cache) < cacheSize:
                cache.append(city)
            elif len(cache) == cacheSize:
                cache.append(city)
                cache.pop(0)
            answer+=5
            
    return answer