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

LRU 알고리즘은 페이지 교체 알고리즘입니다. 페이지 부재가 발생했을 경우 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘입니다.

 

간단하게 그림으로 설명을 하자면

사이즈가 4인 배열에서 새로운 값을 넣으려고 하면

가장 오래된 값을 제거하고 새로운 값을 넣습니다. 가장 기본적인 개념입니다. 코드로 더 자세하게 알아보도록 하겠습니다

 

 

cache_size = 5
company_list = ['apple', 'samsung', 'dell', 'lg', 'dell', 'lg', 'dell', 'lenovo', 'asus', 'lenovo', 'apple']
cache = []

for company in company_list:
    if company in cache:
        cache.remove(company)
        cache.insert(len(company_list) - 1, company)
    else:
        if len(cache) >= cache_size:
            cache.pop(0)

        cache.append(company)

print(cache)

파이썬으로 작성한 LRU 알고리즘입니다.

 

해당 배열에 찾을 내용이 있다면 가장 최근으로 변경하고, 없다면 가장 오래된 요소를 삭제한 후 값을 넣습니다.

 

['apple']
['apple', 'samsung']
['apple', 'samsung', 'dell']
['apple', 'samsung', 'dell', 'lg']
['apple', 'samsung', 'lg', 'dell']
['apple', 'samsung', 'dell', 'lg']
['apple', 'samsung', 'lg', 'dell']
['apple', 'samsung', 'lg', 'dell', 'lenovo']
['samsung', 'lg', 'dell', 'lenovo', 'asus']
['samsung', 'lg', 'dell', 'asus', 'lenovo']
['lg', 'dell', 'asus', 'lenovo', 'apple']
['lg', 'dell', 'asus', 'lenovo', 'apple']

 

위와 같이 배열이 바뀝니다.