항목 26 : 자료 포맷과 효율성, 1부 : 간결함 ( 난이도 : 4 )

1 ) 표준 컨테이너 deque, list, set, vector가 데이터를 적재하기 위해, 얼마나 추가비용을 부담해야 하는가?

참조 : http://ikpil.com/817

2 ) 월드와이드 체스 서버를 만들고, 각 경기의 플레이를 저장한다고 하자. 플레이어의 이름이나 기타 부수적인 것을 저장하는것이 아닌, "플레이 자체"를 저장하는 것에만 초점을 맞추고, 이 데이터를 저장하기 위해 얼만큼의 메모리가 필요 할까?

전제로 반수씩 기록한다. 플레이어 정보(이름, 승패 등...)는 제외시킨다. 1 바이트당 8비트로 한다. 체스판은 세로(row)8줄 : 1 ~ 8 가로(col) 8줄 : a ~ h 이다. 유닛은 킹,퀸,루크,비숍,나이트,폰, 이 있다. 플레이어는 두명이다.

a. 반수 하나 당 128 바이트

이 정도면, 각 자리의 상태를 모두 기록할 수 있을 것이다. 각 자리의 상태를 2바이트씩, 총 128바이트면 그만이다.
 인간이 보기에도 편하게 만들 수 있다. 하지만 .. 반수로 100수까지 갈 수 있는 체스에선 한 경기당 12KB, .. 낭비가 무척 큰 단점이 있다.

b. 반수 하나 당 32 바이트

이 정도면, 각 자리(총 64자리)의 상태를 기록하되, 각 4비트에 누구의 어떤 유닛이 있는지 기록할 수 있다. 이 때부터 인간이 보기엔 힘들다. 이럴 꺼면, 더 최적화 시키는게 좋겠다.

c. 반수 하나 당 최소 4 바이트, 최대 8 바이트

자리수 기록 방식을 포기하고, 움직인 녀석만을 기록 하는 전략을 취하면 된다. 예를 들어 a1지역에 있는 유닛을, a2지역으로 이동 시킨다. 라고 하면, a1, a2 해서 총 4바이트에 기록 가능하고, 부수적으로 a1 에서 a2 지역으로 이동 시 a2 지역에 있는 어떤 유닛은 없어진다거나, a2로 가서 무엇으로 대체된다거나의 기록으로 최대 8바이트로 만들 수 있을 것이다.

d. 반수 하나 당 최소 2 바이트, 최대 4 바이트

a1, a2 표기법을 포기하고, 1 바이트로 표현을 한다. 가로줄 4비트, 세로줄 4비트, 로 한 수를 2바이트로 표현하고 마찬가지로 부수적인것까지 4바이트면 충분하다.

e. 반수 하나 당 12 비트

더 최적화 시킨다면, 가로줄은 8의 경우 수만 필요하므로 3비트면 충분하다. 그러면 가로 세로 6비트면 되기 때문에, 시작과 끝으로 12비트면 충분하다. 이 경우 문제는 .. 이동만 지정해 줄 뿐, 변경이나 특수한 환경에선 기록 될 수 없다.

총평

.. 이거 거저먹을려는 항목이 아닌가?