2. LRU
1. LRU 캐시 동작 방식 및 파이썬 실습 코드
가장 먼저, 캐시는 데이터 값을 미리 저장해 놓는 임시 저장소이다. 데이터를 미리 저장해 놓으면 계산이나 접근 시간 없이 빠르게 다시 요청되는 데이터에 접근할 수 있다.
Cache 알고리즘 중에서 가장 유명한 알고리즘으로, Least Recently Used의 약어이다. (즉, 가장 최근에 쓰이지 않은, 오래된 데이터를 제거해서 캐시 메모리를 확보하는 방식)
캐시 메모리와 같은 컴퓨터 자원은 한정적이기에, 제한된 용량 내에서 데이터를 빠르게 접근할 수 있어야 한다. 이를 위해 여러 알고리즘이 존재하는데, LRU는 앞서 말한 것처럼 가장 최근에 쓰이지 않은 데이터부터 제거해서 새로운 데이처로 교체하는 방식이다.
일반적으로 LRU 알고리즘 구현은 Linked List를 이용한 Queue, ArrayList, Map 등을 사용한다고 한다.
(코틀린으로 구현할 때는 ArrayList를 썼는데...맞게 구현한건지 모르겠어서 코드는 못 올렸다..)
대신 파이썬으로 간단히 구현해보았다.
Queue를 사용함! 생각보다는 굉장히 간단한데, cache에 있으면 cache를 update하고 cache에 없으면 새로 넣어준다. 단, 이때 cache 크기가 넘어가면 가장 오랜기간 참조하지 않은, 0번째 원소를 제거한다. (popleft 이용)
from collections import deque
cache_size=5
cache=deque([])
people=['서인국', '김선호', '이제훈', '김수현', '김수현', '서인국', '김남길', '이제훈']
for person in people:
#이번 사람이 cache에 있으면, cache의 맨 뒤로 이동
if person in cache:
cache.remove(person)
cache.append(person)
#없으면, cache에 넣되 cache가 가득 찬 상태면 가장 왼쪽 원소 제거
else:
if len(cache)>=cache_size:
cache.popleft()
cache.append(person)
print(cache)[실행 결과]
2. HashMap과 LRU 캐시
HashMap은 Key, Value를 저장하는 Map 구현체 중 하나이다. 특징은 Key를 Hashing하여 빠르게 처리해, 입력과 삭제의 시간복잡도가 O(1)인 자료구조이다.
자료구조에 빠르게 저장, 삭제한단 점에서 LRU 캐시랑 비슷하다는 생각이 들었다.. https://hee96-story.tistory.com/47 분의 코드를 보면, HashMap으로 노드 탐색 속도를 개선해 LRU 캐시 알고리즘을 구현하였다.
노드 제거 시, prev node가 next node를 가리키고 next가 prev를 가리키면 current node는 사라진다.
노드를 새로 삽입할 경우에는, 캐시 사이즈가 주어진 용량에 비해 넘친다면 가장 오래된 원소인 tail.prev 를 제거하고 head.next에 새로운 원소를 추가한다. (즉, 새로 추가된 원소는 head 근처에, 오래된 원소는 tail 근처에 존재한다.)
Reference
https://hwiyong.tistory.com/398
https://sabarada.tistory.com/57