Optimal Caching & Shortest Paths in Graph

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Optimal Caching

k item을 수용할 수 있는 cache가 있다. Request가 왔을 때, cache에 있는 item이면 cache hit, 없으면 cache miss라 한다. Cache miss 시에 request한 item을 cache에 보관하기 위해 보관되어 있던 item을 eviction한다. 

 

이때, 목표는 Cache miss 횟수가 최소화 되도록하는 Eviction schedule을 찾는 것이다.

 

 

Farthest in Future

: 제일 오랫동안 request되지 않을 item을 evict시키는 방법

 

=> FF (Farthest in Future)은 optimal eviction schedule이다.

 

 

Reduced schedule : Cache miss가 생길 때에만 eviction을 수행하는 schedule

 

 

 

 

Eviction이 필요한 item에 대해 두 schedule의 eviction이 1:1 mapping이 되기 때문에 Unreduced schedule은 Reduced schedule로 transform이 가능하다.

 

 

 

Case 1 : d가 request하지 않을 건데 불필요하게 d가 load된 경우

-> 애초에 c를 evict하지 않고 쭉 가지고 있으면 됨

 

Case 2 : time $t'$에 d request하기 전에 d가 load된 경우

-> time $t'$에 c를 evict하면 됨

 

둘다 $S'$로 transform이 가능하다.

 

 

Pf ) FF가 Optimal임을 증명 (귀납법)

j item까지는 reduced schedule $S$와 $S_{FF}$의 eviction decision이 같다 가정하자. 그러면 j+1 item까지 $S_{FF}$\와 같은 eviction decision을 가지면서 $S$에서 miss가 더 발생하지 않는 reduced schedule $S'$가 존재함을 보이자.

 

j+1 번째인 d를 request할 때, $S$와 $S_{FF}$의 cache content는 같다.

다음 3가지 case로 나눌 수 있다.

 

Case 1 : d가 $S$와 $S_{FF}$ 둘다 존재한다.

-> 두 schedule 모두 reduced이므로 추가 eviction이 발생하지 않는다.

따라서 $S' = S_{FF}$

 

Case 2 : d가 cache에 존재하지 않고, $S$와 $S_{FF}$둘다 같은 element를 evict할 때

-> 동일한 자리에 d가 차지하게 되므로 $S' = S_{FF}$

 

Case 3 : d가 cache에 존재하지 않으면서, 다른 element를 evict할때

$S$는 f를 evict, $S_{FF}$는 e를 evict한다 하자. FF의 정의에 의해, f가 e에 비해 빨리 request된다.

 

 

 

j+1 request후의 상태는 위와 같다. ($S'$는 $S_{FF}$에서 j+1 request를 한 후)

이때, $S'$가 $S$보다 cache miss가 같거나 작다는 것을 보이면 된다. ($S$보다 나쁘지 않다)

 

j+1 request후, $S, S'$에 다른 action을 요구하는 j' request가 있고, g를 request한다고 하자.

 

Case 3a : g = e

FF정의에 의해 f가 e에 비해 빨리 request되기 때문에 g는 e가 될 수 없다.

 

Case 3b : g = f

S는 f가 존재하지 않는다. 그렇기 때문에 evict를 해야하는데,

1) e를 evict : $S$는 eviction하고 $S$와 $S'$와 같아진다.

2) e=e'인 e'를 evict : 그럼 $S$는 e, f를 가지고 있는 상태이다. 그러면 $S'$에서 아무 의미 없이 가지고 있던 e'를 evict하고 e를 가져옴으로써 $S$와 $S'$를 같게 만들어줄 수 있다.

이 때, $S'$는 unreduced schedule이 된다. 하지만 위에서 관찰한것과 같이 cache miss 개수에 영향을 주지 않고 reduced schedule로 transform할 수 있다.

 

Case 3c : g가 e, f 둘다 아닐 때

다른 action을 요구하는 g이기 때문에 $S$는 e를 무조건 evict해야한다. e가 아닌 것을 evict하면 $S'$에서도 같은 것을 evict하면 같은 action이 되어버리기 때문이다. $S$가 e를 evict하면 $S'$는 f를 evict하면 되기 때문에 $S$와 $S'$를 같게 만들어 줄 수 있다.

 

 

위의 모든 case에 대해 $S, S'$ 둘다 same cache로 돌아올 수 있다. 이 때, $S'$는 $S$에 비해 추가의 cache miss가 없었다. 그렇기 때문에, $S'$를 만든 $S_{FF}$전략은 $S$보다 같거나 좋은 상태이기 때문에 optimal로 볼 수 있다. 

 

 

 

Shortest Paths in a Graph

Directed graph에서 s부터 t까지의 최소 거리를 찾는 문제 (Cost의 합이 제일 작도록)

 

 

Dijkstra's algorithm

시작점 s에서 주위를 탐색한다. 주변에 다음을 만족하는 node v를 찾는다.

v를 S에 넣고, $d(v) = \pi(v)$로 설정한다.

 

 

 

 

 

Pf ) 귀납법으로 shortest path임을 증명하자.

node 개수가 1개일 때는 자명.

 

 

 

Dijkstra's algorithm에서는 v를 선택했고, s에서 v로 가는 더 짧은 path P가 존재한다 하자.

그리고 x-y는 S에서 바깥으로 나가는 최초의 edge라 하자. 그러면 아래의 부등식이 성립한다.

 

이를 통해 Dijkstra's algorithm을 통해 선택한 path가 더 짧다는 것을 보임으로써 모순이다.

이런식으로 넓혀나가면 귀납법으로 증명완료이다.

 

 

Dijkstra's algorithm은 데이터 구조에 따라 time complexity가 달라진다 (아래 표 참고)