[알고리즘/파이썬(Python3)] 캐시 알고리즘 중 LRU 알고리즘

캐시 알고리즘은 최근 사용하거나 자주 사용하는 데이터 항목을 빠른 계산이 가능한 메모리 위치에 유지시키는 구조입니다.

정보를 제공하는 속도를 높이기 위해 새로운 데이터가 발생했을 때 캐시에서 가장 오레 전에 사용된 데이터를 제거하고 새로운 데이터를 삽입하는 알고리즘입니다.

 

페이지 교체 알고리즘이라고 하면 설명이 자세하게 나옵니다.

 

Page replacement algorithm - Wikipedia

 

그 중에서도 LRU (Least Recently Used Algorithm)은 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법입니다.

 

 

LRU (Least Recently Used Algorithm)

▷ 주기억장치에 적재되어 있는 페이지들에 대해
    이들이 참조된 시간을 기준으로 교체될 페이지를 선정하는 기법
▷ 한 프로세스에 할당된 페이지 프레임들 모두에 페이지들이 적재되어 있는 상황에서
    새로운 페이지가 적재되어야 할 때에는 현재 주기억장치에 적재되어 있는 페이지를 중 
    최근 가장 오랫동안 참조되지 않은 페이지를 교체한다.

페이지 교체 알고리즘 FIFO, LFU, LRU

 

 

코드 구현 설명

파이썬으로는 pop(또는 remove) & append 로 구현할 수 있습니다.

예를 들어 캐시사이즈는 2이고 cities에 담긴 도시명을 저장한다고 가정하겠습니다.

cacheSize = 3
cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "NewYork"]

 

cache는 이렇게 빈 상자를 두 개 가진 리스트라고 볼 수 있습니다.

먼저 "Jeju" 부터 시작합니다.

캐시에 Jeju가 없으니까 캐시에 Jeju를 추가해줍니다. - - - -  cache.append("Jeju")

 

그 다음 도시인 "Pangyo"도 캐시에 없으니 추가해줍니다. - - - - cache.append("Pangyo")

 

세 번째 도시인 "Seoul"도 캐시에 없으니 추가합니다. - - - - cache.append("Seoul")

 

여기까지 살펴봤을 때 append로 캐시를 구현하면 가장 최근에 사용한 아이템이 리스트의 가장 마지막에 놓이게 됩니다.

 

네 번째 도시인 "Jeju"는 cache에 있습니다.

지금은 "Jeju"가 가장 최근에 사용한 아이템이니 리스트의 가장 마지막에 놓이도록 해야합니다.

if "Jeju" in cache:
    cache.remove("Jeju")
    cache.append("Jeju")

로 "Jeju"를 가장 최근에 사용한 아이템 위치에 놓을 수 있습니다.

"Jeju"를 cache에서 제거하고

"Jeju"를 가장 최근 위치에 추가

 

 

다섯번 째 도시인 "NewYork"은 cache에 없습니다.

cache에 추가해줘야 하는데, cachSize를 다 소비했네요.

가장 오랫동안 참조되지 않은 "Pangyo"를 제거하고 "NewYork"을 가장 최근에 사용한 아이템 위치에 놓이도록 합니다.

여기서 알 수 있는게, 가장 오랫동안 참조되지 않은 아이템은 cache 리스트의 0번째 인덱스에 놓이게 된다는 것입니다.

if "NewYork" not in cache:
    if len(cache) >= cacheSIze:
        cache.pop(0)
        cache.append("NewYork")

"Pangyo"를 없애 cache를 비우고

"NewYork"을 추가

 

최종 코드 및 결과 출력

지금까지 내용을 코드로 완성한 뒤 출력하면 아래와 같습니다.

cacheSize = 3
cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "NewYork"]
cache=[]

for city in cities:
    if city in cache:
        cache.remove(city)
        cache.append(city)
    else:
        if len(cache) >= cacheSize:
            cache.pop(0)
        cache.append(city)
        
print (cache)

cache를 프린트하면 그림에서 설명했던 순서대로 담겨있는 것을 확인할 수 있습니다.

 

 

캐시 알고리즘 LRU 를 활용한 코딩테스트 문제 확인하러가기↓↓↓↓↓↓

[프로그래머스/2단계/파이썬(Python3)] 캐시