Tape Storage

Problem definition

N data items, parameters Li, Fi

  • Li: size of data = length on tape; 테이프에서 얼마나 차지하는가
  • Fi: frequency of usage; 얼마나 사용되는가

Read and write data on a tape.

  • Write everything at once; 한 번에 모든걸 적는다
  • Read many times
  • each read starts from the beginning of the tape; 한 번 읽으면 무조건 맨 앞으로 돌아간다

직관적으로 생각해보면

  1. F가 큰 것이 tape의 앞에 오면 좋을 것 같다.
  2. L이 작은 것이 tape의 앞에 오면 좋을 것 같다.
    • 작은 것이 앞에 있을 수록 뒤에 것을 읽기 위해 건너가는 시간이 줄어들기 때문이다.

tape_storage

그런데 L이 작은데 F가 큰 경우나, L이 큰데 F가 작은 경우는 어떻게 할까? 정확한 기준이 뭘까?

Algorithm

Just store the data in the decreasing order of Fi/Li

  • Larger Fi -> better to be in the front of the tape
  • Smaller Li -> better to be in the front of the tape
  • But why Fi/Li? What about (Fi/Li)^, (Fi-Li), …?

Correctness

  • Assume Fi/Li < (Fi+1)/(Li+1)
  • We can prove this is not optimal

우리가 위의 알고리즘에서 주장하는 바는 (F1/L1) >= (F2/L2) >= (F3/L3) >= ...이다. 이를 귀류법으로 증명하기 위해 모든 i에 대해 Fi/Li < (Fi+1)/(Li+1)가 성립한다고 가정해보자. 그러면 어떤 i에 대해 Fi/Li < (Fi+1)/(Li+1)가 성립하지 않음을 보이기만 하면 된다.

F를 확률로 생각하면 전체 tape를 읽는데 걸리는 시간의 기댓값은 F1*L1 + F2*(L1+L2) + F3*(L1+L2+L3) + .. + FN*(L1+...+LN) 이다.

위에서 가정한 대로 전체 tape를 읽는데 걸리는 시간의 기댓값을 구하면 다음과 같다. 이 값을 식1이라고 하자.

F1*L1 + F2*(L1+L2) + F3*(L1+L2+L3) + ..  
+ Fi(L1 + L2+... + Li)
+ Fi+1(L1 + L2+ ... + Li+1)
+ FN*(L1+...+LN)

그리고 동일한 tape에서 i와 i+1번째 data의 순서를 바꾼 다음, tape를 다 읽는데 걸리는 시간의 기댓값을 식2라 하면 식2는 아래와 같다.

F1*L1 + F2*(L1+L2) + F3*(L1+L2+L3) + ..  
+ Fi+1(L1 + L2+ ... + Li-1 + Li+1)
+ Fi(L1 + L2+... + Li-1 + Li+1 + Li)
+ FN*(L1+...+LN)

그럼 이제 식1에서 식2를 빼 보자. 그러면

{Fi(L1 + L2+... + Li) + Fi+1(L1 + L2+ ... + Li+1)}
-
{Fi+1(L1 + L2+ ... + Li-1 + Li+1) + Fi(L1 + L2+... + Li-1 + Li+1 + Li}
= Fi+1*Li - FiLi+1
= LiLi+1 * (Fi+1/Li+1 - Fi/Li)

를 얻는다. Li, Li+1 모두 양수이고, 모든 i에 대해 Fi/Li < (Fi+1)/(Li+1)가 성립한다고 가정했으므로 Fi+1/Li+1 - Fi/Li > 0 이다. 따라서 식1라 식2보다 크다는 것을 알 수 있다.

식1의 값(가정대로 했을 때의 걸리는 시간의 기댓값)보다 더 적게 걸리는 시간(식2)이 존재하므로 Fi/Li < (Fi+1)/(Li+1) 이라는 가정은 틀린 가정이다. 따라서 모든 i에 대해 Fi/Li >= (Fi+1)/(Li+1)가 성립한다.