[Greedy Algorithm] Tape Storage

Problem Definition

1차원으로 된 테이브에 내가 원하는 것을 찾으러 가는 것이 굉장히 오래걸림

• N Data Items, Parameters \(L_i\), \(F_i\)
• \(L_i\) : Size of data = Length on Tape
• \(F_i\) : Frequency of Usage

 

Read and Write Data on a Tape

• Write once, everything
• Read many times
• Each read starts from the Beginning of Tape

>> 어떤 순서로 배치하면 좋을까?

idea) 큰게 앞에 있으면 뒤에를 읽으러 갈 때마다 큰거를 읽으면서 가야한다. 즉, 큰게 앞에 있으면 좋지 않다

자주 쓰는게 앞에 있어야한다. 

 

Algorithm 

• Just Store the data in the decreasing order of \(F_i\) / \(L_i\)
• Larger \(F_i\) -> Better to be in Front of Tape
• Smaller \(L_i\) -> Better to b ein Front of Tape

 

Corectness

Asuume \(F_i\) / \(L_i\) < \(F_{i+1}\)/ \(L_{i+1}\)

we can prove that this is not optimal

기댓값 = \(F_1\) x \(L_1\) + \(F_2\) x (\(L_1 + L_2\)) ... +\(F_i\) x (\(L_1 + L_2 + ... L_i\)) + \(F_{i+1}\) x (\(L_1 + L_2 + .. L_i + L_{i+1}\))

읽는데에 거리는 시간에 대한 기댓값이다. 

첫번째것은 F만큼 L의 길이를 읽고 두번째 것은 첫번째 것과 두번째 것을 합친 길이를 두번째 빈도만큼 읽는다.

i <-> i+1 교환 후 기댓값 = ... \(F_{i+1}\) x (\(L_1 + L_2 ... L_{i-1} + L_{i+1}\)) + \(F_i\) x (\(L_1 + L_2...L_{i+1} + L_i\))

 

 

원래 기댓값에 i<-> i+1한 값을 빼준다. 

= \(F_{i+1}\) x \(L_i\) - \(F_i\) x \(L_{i+1}\) = \(L_iL\(i+1\) (\frac{F_{i+1}}{L_{i+1}} - \frac{F_i}{L_i}) > 0\)

바꾸면 시간이 줄어든다. 

기댓값을 적어보니 현재 식이 \(F_i\)/\(L_i\) 라서 사용한다.