알고리즘9

"성능이 어떻게 나오냐"를 이유를 가지고 얘기할 수 있다!

 

엔진에서 불가능한 수준의 힘이 나온다. => 급발진

ECU : 신호만 공급하는 전력도 얼마 안쓰는 전자회로 

 

"프로그램을 이렇게 짜면 빨라" 이유가 있어야 한다.

---

Tape Storage

비교적 간단한 그리드 알고리즘

테이프에 데이터를 저장한다.

(테이프: 데이터를 저장하는 1차원 장소로 사이즈가 다른 데이터 덩어리들을 저장한다.)

 

 

N개의 길이가 다른 데이터 아이템이 있다.

L: 사이즈

F: 몇번이나 자주 사용되느냐 (현실적으로 추정치)

 

추가,삭제 없이 한번에 저장되어 있다.

읽는 건 빠르지만 찾는 과정이 느리다.

* 한번 읽고나면 무조건 앞으로 돌아간다.

(이 조건이 없다면 굉장히 어려운 문제가 된다.)

-> 직전에 어디를 읽었는지와 상관이 없다.

 

어떤 순서로 데이터를 저장해야 성능이 좋을까?

 

직관적으로 알 수 있는 것:

F가 큰 게 앞에 있으면 좋다

L이 작은 게 앞에 있으면 좋다.

 

자주 쓰는게 길면? 정확한 기준이 뭐냐?

 

---

 정답

 

왜 하필 F(i) / L(i)인가?

 

저 순서대로 저장을 한다고 하자

딱 한군데라도 F(i) / L(i) <  F(i+1) / L(i+1) 이 있으면 정답이 아니다.

 

F(1) x L(1) : 첫 번째값 읽을확률x첫 번쨰값 읽는시간

F(2) x (L(1)+L(2)) : 두 번째값 읽을확률x두 번쨰값 읽는시간

F(2) x (L(1)+L(2)+L(3)) : 세 번째값 읽을확률x세 번쨰값 읽는시간

 

 

끝에 두 개 순서를 바꾼다면

 

마지막 줄에서 이 식 이용하면

1번식 - 2번식 > 0

1번식 > 2번식

 

=> 이런게 하나라도 있으므로 정답일 수 없다.

정답이려면 이런게 하나도 없어야 한다 => sorted